Consider N holes arranged in a circle on a wooden board. A marble is placed in one of them. You toss a fair coin to determine if you should move the marble one hole clockwise or one hole counterclockwise. You keep doing this until the marble has been in each hole at least once.

What is the probability that each of the N holes turns out to be the last hole visited by the marble? Number the holes 1 through N, clockwise starting with the hole in which the marble starts. Obviously the probability for hole 1 is zero, since it already has the marble and there are other holes to visit still.

(In reply to solution (spoiler) by Charlie)

After reading Charlie's solution, which I +/- fully understand and agree with, I found the answer counterintuitive and wrote (with my limited programming skills) a test program.
I used 10 marbles, numbered 1 to 9 clockwise and found following propabilities

80000 tosses gave 1807 solutions, so 44.27 tosses/solution.
1 = 249  13 %
2 = 185  10 %
3 = 181  10 %
4 = 165    9 %
5 = 191  10 %
6 = 187  10 %
7 = 183  10 %
8 = 206  11 %
9 = 260  14 %
With 1/(10-1) being 11 %, most come close enough to see that Charlie's sloution is indeed correct. 

The 13 and 14 % could be created by the Rnd function I used, so I did another test on 200000 tosses, giving 4610 solutions, or 43.38 tosses/solution (+/- as above). These are the results.
1 = 675  14 %
2 = 434    9 %
3 = 491  10 %
4 = 456    9 %
5 = 477  10 %
6 = 425    9 %
7 = 503  10 %
8 = 468  10 %
9 = 681  14 %
Which again is close to the 11 %, but where come the 14 % at the edges from.  I don't think it is an error in the  program except maybe the use of the Rnd function.    

Posted by Hugo on 2004-12-29 20:03:47