Each of 100 prisoners gets only 50 tries to find their number among 100 boxes. Searching at random, all of them succeed with probability 7.9·10⁻³¹, which is practically never. But there is a simple strategy that wins almost a third of the time. Check it with a game, a simulation and four explanations.
The computer scientists Anna Gál and Peter Bro Miltersen first studied the problem in 2003. It looks hopeless: each prisoner finds their number with probability 1/2 whatever they do. Yet together they can win almost a third of the time.
A prison holds 100 prisoners numbered 1 to 100. A room holds 100 boxes with the same numbers on their lids.
The warden puts one slip with a prisoner's number in each box. The slips are shuffled at random, and each number is in exactly one box.
The prisoners enter the room one at a time. Each may open 50 boxes to look for their own number. Then they leave, and the room is put back as it was.
If every one of the 100 prisoners finds their number, all go free. If even one fails, all stay in prison. They may agree on a plan in advance, but cannot communicate once it starts.
"Each one succeeds with chance 1/2, so together it's (1/2)¹⁰⁰. That's zero"
For random search that's true. But the prisoners can agree on a strategy that links their results: either they all succeed together, or many fail at once. Then the overall chance is 31.2%.
The slips are placed at random, and the warden doesn't know the plan. What happens if he does is in round 5.
Suppose the prisoners pick the best possible strategy. What is the probability that all 100 go free? Lock in your answer before reading on.
Let's shrink the prison: 20 prisoners, 20 boxes, each opens 10. You are one of the prisoners. Look for your number with the loop strategy or open any boxes you like. Then run all 20 prisoners and see whether they go free.
The computer shuffles 100 numbers into boxes thousands of times and finds the longest loop in each arrangement. The prisoners win when it is at most 50 long. The bars are the simulation; the line is the exact formula.
Each prisoner opens half of the boxes. More prisoners means slightly lower odds, but they never fall below 1 − ln 2 ≈ 30.69%. Even a million prisoners win almost a third of the time.
The strategy doesn't change any single prisoner's chance: it stays 1/2. It changes how those chances are linked to each other.
Exactly one arrow leaves each box and exactly one enters it, because each number is in exactly one box. So the arrows always close up into loops. Mathematicians call them the cycles of the permutation.
You start at the box with your number. It sits on some loop, and you walk along it. The last box of the loop points back to yours, so it holds your number. You always find your number when the loop closes. The only question is whether 50 tries are enough.
So the prisoners win if the arrangement has no loop longer than 50. There can be at most one long loop: two loops of 51 don't fit into 100 boxes.
With either strategy, 50 prisoners fail on average. But with the loop strategy the failures bunch up in the same arrangements: everyone on a long loop fails together. When the prisoners lose, about 73 of them fail on average. In exchange, in 31% of arrangements nobody fails.
For k from 51 to 100, the chance that the arrangement has a loop of length exactly k is 1/k. These events don't overlap, since there's only one long loop. So the chance of losing is 1/51 + 1/52 + … + 1/100 ≈ 68.8%.
Here Hn = 1 + 1/2 + … + 1/n is a harmonic number. To build a loop of length k, choose k boxes, join them in a circle in (k − 1)! ways, and arrange the rest any way you like. This strategy is the best possible: no other plan gives better odds.
What if the prisoners may open more or fewer boxes? And what should they do if the warden knows their plan and places the numbers on purpose?
The warden has learned about the loop strategy. He places the numbers so that all 100 boxes form one big loop. Then no prisoner finds their number in 50 tries.
100 prisoners. Press "Check": 10,000 simulated arrangements show the exact formula is right.
| Tries each | All free (exact) |
|---|
Anna Gál and Peter Bro Miltersen described the problem in a paper on data structures at the ICALP 2003 conference. Their version used coloured strips of paper, not prisoners. Their Aarhus University colleague Sven Skyum pointed them to the loop strategy.
Eugene Curtin and Max Warshauer proved that the loop strategy is optimal: no other plan gives the prisoners better odds. The proof appeared in The Mathematical Intelligencer in a paper called "The locker puzzle".
The Veritasium channel brought the puzzle to a wide audience. The video called it a riddle that seems impossible even once you know the answer.
100 numbers can be placed in 100 boxes in 100! ways. That number has 158 digits. In about 31% of them the longest loop is at most 50.
When the loop strategy fails, about 73 prisoners fail on average: everyone on the long loop. With random search about 50 fail, but almost never zero.
However many prisoners there are, if each opens half of the boxes, the chance that all go free never drops below 1 − ln 2 ≈ 30.69%. For 100 prisoners it's 31.18%; for 1,000 it's 30.74%.
Share your own explanation, an objection or a variant of the puzzle. Commenting needs a GitHub account.
I keep adding new puzzles, new ways to explain them and write-ups of the discussions they start. Leave your email and I'll write when something new is out. No spam, one-click unsubscribe.
The sign-up form will appear here soon.