The 100 prisoners problem, also called the locker puzzle (Curtin and Warshauer 2006), is a probability puzzle in which 100 numbered prisoners must each find their own number among 100 closed boxes. The numbers 1 through 100 are placed uniformly at random, one per box. Each prisoner may inspect at most 50 boxes, the boxes are closed again afterward, and the prisoners may agree on a strategy beforehand but cannot communicate during the searches. All prisoners survive only if every prisoner finds his or her number. Despite the similar name, this permutation puzzle is distinct from the game-theoretic prisoner's dilemma.
If each prisoner independently chooses 50 boxes, the probability that all succeed is 
. A much better strategy views the placement as a permutation. Prisoner 
first opens box 
, then opens the box whose number is found inside, and continues
following that permutation cycle. Every prisoner
succeeds iff the permutation
has no permutation cycle longer than 50.
There can be at most one permutation cycle of length greater than 50, and a random permutation
has a permutation cycle of length 
with probability 
for 
. Therefore the success probability,
whose decimal expansion is OEIS A399699, is
 |
where 
is a harmonic number. More generally, with 
prisoners who may each open 
boxes, the probability approaches
(OEIS A244009) as 
(Curtin and Warshauer 2006).
