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/(101) 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 20041229 20:03:47 