100 prisoners are numbered 1 to 100. A room holds 100 boxes in a row, each containing one of the numbers in random order. Each prisoner may open 50 boxes to find his own number, and all must succeed. No communication is allowed once the search starts. What is the best success probability?

100 prisoners are numbered 1 to 100. A room holds 100 boxes in a row, each containing one of the numbers in random order. Each prisoner may open 50 boxes to find his own number, and all must succeed. No communication is allowed once the search starts. What is the best success probability?

Approach: Read the box contents as a permutation and have each prisoner start at the box with his own index, then follow the number he finds to the next box.

0.3118. Each prisoner opens the box labelled with his own number, then the box labelled by the number he finds, and repeats. This walks the cycle of the random permutation containing his index, and he succeeds within 50 openings exactly when that cycle has length at most 50. So the group wins precisely when the permutation has no cycle longer than 50, and there can be at most one such cycle. The number of permutations of 100 with a cycle of length L > 50 is C(100,L) * (L-1)! * (100-L)!, which is 100!/L, so the failure probability is sum_{L=51}^{100} 1/L = H_100 - H_50 in harmonic numbers. Success is 1 - 0.6882 = 0.3118, near 1 - ln 2. Independent random searching gives only 2^{-100}.

Follow-up: If the prisoners may open 60 boxes each instead of 50, what is the success probability?

Key concepts: cycle following strategy, random permutation, harmonic numbers.