Radio Astronomy Systems Research Group

The average number of crossings is 22.5.

If we want to find the average number of crossings, we should model the number of crossings as a random variable. We can find the distribution and then calculate the expected value to give us our answer.

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. 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.

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.

Now if we were to continue this, we will see that for any configuration with k crossings, there is an inverse configuration with N - k crossings. This gives us our distribution. We will have 1 way to get 0 crossings and 1 way to get N crossings. We have 9 ways to get 1 crossings, and 9 ways to get N - 1 crossings. We can see that our distribution will be symmetric, and that the point of symmetry will be at N / 2. This gives us our expected number of crossings.

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 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.

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 .