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
re: solution (spoiler) by Hugo)
The results I got for 100,000 trials (I didn't count the tosses) are:
1 0
2 11144
3 11049
4 11198
5 11073
6 11020
7 11089
8 11141
9 11115
10 11171
with the program:
DIM answer(10)
FOR trial = 1 TO 100000
tr = tr + 1
REDIM visited(10)
visited(1) = 1
visitCt = 1
posn = 1
DO
dir = (INT(2 * RND(1))  .5) * 2
posn = posn + dir
IF posn < 1 THEN posn = posn + 10
IF posn > 10 THEN posn = posn  10
IF visited(posn) = 0 THEN
visited(posn) = 1
visitCt = visitCt + 1
END IF
LOOP UNTIL visitCt = 10
answer(posn) = answer(posn) + 1
NEXT
FOR i = 1 TO 10
PRINT i, answer(i)
NEXT
PRINT

Posted by Charlie
on 20050102 17:33:23 