The Road Not Taken...
Suppose you have 2 4 identical toothpicks and arrange them so that they form an outline of a 3 by 3 grid of 9 identical squares.
Starting at the lower left corner, we can trace out 2 0 distinct paths to the top right corner by going either up or to the right, one toothpick at a time. (Each of these paths involve precisely 6 toothpicks.)
If we remove one of the 2 4 toothpicks at random, what is the expected number of these 2 0 distinct paths that will remain intact?
The answer is 15.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
Label the 24 toothpicks 1 to 24, and label the 20 paths 1 to 20.
Draw up a table with 24 rows and 20 columns. If path j remains intact after toothpick i is removed, put a 1 in the cell (i,j). If not, put a 0.
The expected number which we seek is equal to the expected number of 1s in a row, which is equal to the total number of 1s in the entire table divided by 24.
Now consider each column in the table. Let's say we consider column j. There will be a 0 in row i if toothpick i is on path j, if not there will be a 1. Since each path consists of exactly 6 toothpicks, there must be exactly 24 - 6 = 18 '1's in each column.
Hence, the table has 1 8 × 2 0 = 3 6 0 '1's, and the expected number we seek is 3 6 0 / 2 4 = 1 5 .
For each of the 2 4 toothpicks we must assign a value that represents the number of the 2 0 distinct paths that make use of that specific toothpick. For example, the two toothpicks connected at the lower left corner will each be on half of the 2 0 paths, so can each be assigned a value of 1 0 . This value represents the number of paths lost if that particular toothpick is removed.
There are various ways of determining the values we need to assign each toothpick, but regardless, we will end up with 4 toothpicks with a value of 1 , 4 with a value of 3 , 4 with a value of 4 , 4 with a value of 1 0 and 8 with a value of 6 . (I'll try and outline my method of determining these values later when I have time.)
Now each of the toothpicks has a 2 4 1 probability of being picked at random, so the expected number of "lost" paths is
( 2 4 1 ) ( 4 ∗ 1 + 4 ∗ 3 + 4 ∗ 4 + 4 ∗ 1 0 + 8 ∗ 6 ) = 2 4 1 2 0 = 5 .
Thus the expected number of paths that remain intact is 2 0 − 5 = 1 5 .
This is how I did it, but I have to admit that Jon Haussmann's solution is far more elegant. You can save a tiny bit of time by only computing the number of paths for half of the toothpicks, since the system is symmetric.
Log in to reply
Yes, I used the fact that the system was symmetric as well; I should have mentioned that but I typed up my solution in a hurry so it wasn't as informative as I would have liked. Jon's solution is indeed elegant, (and correct); I had initially thought of that approach but I wasn't certain at the time that it was valid, (it just seemed too simple :) ), so I took the longer approach just to be sure that my method couldn't be challenged, (even though the two methods yield the same answer). I'm glad that he posted his solution, in any event.
Nice problem Brian!
Log in to reply
Thanks, Satyen. The next question I might pose is to find the expected number of distinct paths remaining intact after removing 2 toothpicks at random, (generalized to k toothpicks at random, 1 ≤ k ≤ 1 8 ), but I need to figure out the answer first. That would probably be a level 5 problem. :)
Each path from the lower-left corner to the upper-right corner consists of 6 segments, so the total number of segments over all 20 paths is 6 ⋅ 2 0 = 1 2 0 . There are 24 segments, so on average, there are 1 2 0 / 2 4 = 5 paths passing through a segment. Therefore, after a segment is removed, on average, 2 0 − 5 = 1 5 of the paths are still intact.