The 100 Prisoners and the Boxes
An extension of the topic of permutations, cycles, and probability. 100 prisoners each search for their own number among 100 boxes (with 50 tries each). At random, the chance that all succeed is (1/2)^100 ≈ 0. But the “follow the permutation cycle” strategy gives ~31%! Success depends on the length of the longest cycle of the permutation (≤50). Solution: Gál and Miltersen, 2003.
I’ll give you the length of the longest cycle of the permutation — judge whether, with the cycle strategy, EVERYONE survives (each opens ≤ 50 boxes).
What is the puzzle?
100 prisoners, each with a number 1–100, must find their number in one of 100 boxes — opening at most 50 of them. EVERYONE must succeed to survive; once they start they cannot communicate. The numbers are placed in the boxes in a fixed (unknown to the prisoners) way — a permutation. Intuition says the situation is hopeless.
The random strategy — practically zero:
If everyone opened 50 boxes at random, a single prisoner’s chance would be , and the chance of all one hundred at once:
This number is so small it is practically zero — less likely than hitting one specific atom in the Universe.
The cycle strategy — a brilliant idea:
Each prisoner starts from the box with their own number, checks the number found inside, moves to the box with that number, and repeats — “following the permutation cycle”. The key observation: the arrangement of numbers is a permutation, which decomposes into cycles. A prisoner finds their number in ≤ 50 steps exactly when the cycle containing their number has length ≤ 50.
Why does it work? (the invariant)
Everyone succeeds if and only if the permutation has no cycle longer than 50. The probability of that for a random permutation of 100 elements is:
As much as ≈ 31%! A clever, coordinated strategy — despite the lack of communication — turns the odds from “practically zero” into “almost one third”. In our example permutation the longest cycle has length 47 (≤ 50), so everyone survives.
History of the puzzle
The “100 prisoners and the boxes” is one of the most famous and surprising mathematical puzzles. It was formulated and solved by Anna Gál and Peter Bro Miltersen in 2003. It astonishes precisely because the result defies intuition — it is hard to believe that coordination without communication can raise the odds so drastically.
Why this matters for your exam:
This is a model example of how thinking about the structure of a problem (here: permutation cycles) beats naive counting. It extends the topic of permutations, their cycles, and probability — a universal trick: instead of counting “how many possibilities”, ask what success exactly depends on (here: the length of the longest cycle).
Remember: the random strategy gives , while the cycle strategy gives as much as — the success of all occurs exactly when the longest cycle of the permutation has length ≤ 50.
Theory & formulas
The cycle strategy
Each prisoner starts from the box with their own number and follows the number they find (tracing the permutation's cycle), opening up to boxes.
Condition for success
Everyone finds their own number if and only if the longest cycle of the permutation has length .
Probability
instead of with random searching.
Notation: cycle length, .
Frequently asked questions
›Does a clever strategy give the prisoners a real chance?
Yes — the cycle strategy gives a ~31% chance, instead of practically zero with random searching.
›What is the cycle strategy?
Each one starts from the box with their own number and follows the permutation's cycle, opening the box whose number they just found.
›What does the success of all the prisoners depend on?
On whether the longest cycle of the permutation has length ≤50 — the probability of that is ~1−ln2 ≈ 31%.
Teaching? Embed this experiment on your site.
Free widget — paste it on your school site, blog or notes. It links to the full version.