HardProbability

The 100 Prisoners Problem

Jane StreetTwo Sigma

100 prisoners’ numbers are placed randomly in 100 boxes, one per box. Each prisoner may open at most 50 boxes, looking for their own number; all must succeed or all die, and they cannot communicate once the search begins. With the optimal strategy (each prisoner starts at their own box and follows the number found to the next box), what is the probability that every prisoner finds their number? Answer to two decimals.

Approach

Following the chain from your own box always stays inside one cycle.

You succeed iff no cycle is longer than 50.

Answer

Show the final answer

The answer is 0.31. Sign in free for the full worked solution and to check your own answer.

Related problems

More in Probability.