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
Coin Toss — Two HeadsEasyRoll Until All Six FacesMediumDrunk PassengerMediumBayes — Disease TestMediumBroken Stick TriangleMediumHat CheckMedium
More in Probability.