Trace: • strings
wiki:donuts:springsummer2014:answers:strings
Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
|
wiki:donuts:springsummer2014:answers:strings [2014/06/26 23:10] jmb438 created |
wiki:donuts:springsummer2014:answers:strings [2014/06/26 23:38] (current) jmb438 |
||
|---|---|---|---|
| Line 6: | Line 6: | ||
| To find the distribution, we could enumerate all possible outcomes. However, this can be quite tedious. To simplify this, lets look at a few cases. | To find the distribution, we could enumerate all possible outcomes. However, this can be quite tedious. To simplify this, lets look at a few cases. | ||
| - | First, we will number the holes in each row from 1 - 10. Now if we run the strings so that they go from hole 1 to hole 1, hole 2 to hole 2 and so on, there will be no crossings. If we run the strings from 1 to 10, 2 to 9 and so on, we will have the maximum number of crossings (every strings crosses every other strings). We will call the maximum number of crossings //N//. | + | First, we will number the holes in each row from 1 - 10. If we run the strings so that they go from hole 1 to hole 1, hole 2 to hole 2 and so on, there will be no crossings. If we run the strings from 1 to 10, 2 to 9 and so on, we will have the maximum number of crossings (each string crossing every other string). We will call the maximum number of crossings //N//. |
| - | Let us define an 'inverse' operation where we simply invert the indices of one row: 1 becomes 10, 2 becomes 9 and so on. Notice the maximum crossings configuration is the inverse of the no crossing configuration. | + | Let us define an 'inverse' operation where we simply invert the indices of one row (hole 1 becomes 10, 2 becomes 9, etc) while rearranging the strings so that they go to the same numbered hole. Notice that the maximum crossing configuration is the inverse of the no crossing configuration. |
| - | Now suppose we have have 1 -> 2 and 2-> 1, and the rest match(3->3, 4->4 and so on). This gives us one crossing. The inverse of this configuration will have //N - 1// crossings. This can be seen in the example below. | + | Now suppose we have have 1 -> 2 and 2-> 1, and the rest match(3->3, 4->4 and so on). This gives us one crossing. The inverse of this configuration will have //N - 1// crossings. This can be seen in the simplified three-string example below. |
| {{:donutquestions:strings2.png?200|}} | {{:donutquestions:strings2.png?200|}} | ||
| Line 18: | Line 18: | ||
| The question remains: what is //N//? | The question remains: what is //N//? | ||
| - | To get this, we simply count the number of crossings for the maximum crossing configuration. We begin by counting the crossings involving the string going between holes 1 and 10. This string crosses every other giving us 9 crossings. Next, we move on to the string between 2 and 9. We've already counted the first string, so we will ignore that string. This give 8 more crossings (see below). Continuing this process, we see that we end up with //9 + 8 + 7 + ... + 1 + 0 = 45 = N// crossings. | + | To get this, we simply count the number of crossings for the maximum crossing configuration. We begin by counting the crossings involving the string going between holes 1 and 10. This string crosses every other giving us 9 crossings. Next, we move on to the string between 2 and 9. We've already counted the first string, so we will ignore it. This give 8 more crossings (see below). Continuing this process, we see that we end up with //9 + 8 + 7 + ... + 1 + 0 = 45 = N// crossings. |
| {{:donutquestions:strings1.png?300|}} | {{:donutquestions:strings1.png?300|}} | ||
| Here is another way to find //N//. Think of each crossing as a pair of strings. How many different ways can we choose a pair of strings out of 10 total strings? This is a simple combination: 10 choose 2. This also gives us a more general solution to this problem. The maximum number of crossings for any number of holes //h// is //N = h! / (2!(h-2)!) = h(h-1) / 2//. (Admittedly, this isn't any different that adding 9+8+7+...+1. It's just a less tedious way to think of the problem.) | Here is another way to find //N//. Think of each crossing as a pair of strings. How many different ways can we choose a pair of strings out of 10 total strings? This is a simple combination: 10 choose 2. This also gives us a more general solution to this problem. The maximum number of crossings for any number of holes //h// is //N = h! / (2!(h-2)!) = h(h-1) / 2//. (Admittedly, this isn't any different that adding 9+8+7+...+1. It's just a less tedious way to think of the problem.) | ||
| + | |||
| + | So, now we have //N// for our 10 string problem //N = 10(10-1)/2 = 45// and we know that the expected number of crossings is //N / 2// giving us //45 / 2 = 22.5 //. | ||
wiki/donuts/springsummer2014/answers/strings.1403845808.txt.gz · Last modified: 2014/06/26 23:10 by jmb438