Overview
This is the rare puzzle whose answer looks impossible. Independent random guessing gives each prisoner a 50% chance, so all of them succeeding should be astronomically unlikely — yet a strategy pushes it to about 31%, and stays there no matter how many prisoners you add.
How to solve The Prisoners and the Boxes
- Each prisoner starts at the box carrying their own number, reads the slip, and moves to the box that slip names.
- Because the slips are a permutation, this chain is a cycle that must eventually return to the starting box — and the slip that closes the cycle is your own number.
- So you succeed exactly when your cycle is no longer than the number of boxes you may open, and EVERYONE succeeds exactly when the permutation's longest cycle is at most n/2.
The key insight
The strategy makes the prisoners' fates maximally correlated instead of independent. They no longer need 100 lucky coin flips — they need one lucky permutation, and long cycles are rare: P(no cycle > n) = 1 − ln 2 ≈ 30.7%.
Variations & echoes
- It is provably optimal: no strategy beats 1 − ln 2 for large n.
- If the prisoners may first swap the contents of two boxes, they can break the one long cycle and win over 99% of the time.
Frequently asked questions
How can correlating outcomes possibly help?
Because the prisoners only care about ALL succeeding. Independent 50% chances multiply to nothing; the strategy makes the group win or lose together on a single, fairly likely condition.