The 100 prisoners problem
100 prisoners numbered 1 to 100 face a room with 100 drawers, into which the numbers 1 to 100 have been placed in random order. One at a time, each prisoner enters, opens at most 50 drawers looking for their own number, and leaves the room exactly as it was, with no communication afterwards. All are freed if every prisoner finds their own number, otherwise all are executed. They may agree on a strategy in advance. Find a strategy that succeeds with probability above 30%, and compute its exact success probability.
History and references
Solved in 2003 by Anna Gál and Peter Bro Miltersen.
Anna Gál and Peter Bro Miltersen introduced the problem in 2003. If everyone searches at random, each prisoner succeeds with probability 1/2 independently and the group survives with probability . The good strategy is for each prisoner to open the drawer with their own number, then the drawer labeled by the number found there, and so on, following the cycle of the permutation that contains their number. Everyone then succeeds exactly when the permutation has no cycle longer than 50, which happens with probability , where is the th harmonic number. As the number of prisoners grows this tends to . Eugene Curtin and Max Warshauer proved in 2006 that no strategy does better.
References
Solutions 0
Sign in or create an account to publish a solution