Trace: • strings
wiki:donuts:springsummer2014:answers:strings
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
wiki:donuts:springsummer2014:answers:strings [2014/06/26 23:27] jmb438 |
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 (each string crossing every other string). 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 (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. | 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. | ||
| 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|}} | ||
wiki/donuts/springsummer2014/answers/strings.1403846873.txt.gz · Last modified: 2014/06/26 23:27 by jmb438