The 100 prisoners: from no chance to almost one in three
A hundred prisoners are numbered 1 to 100. In a room are 100 boxes, and the numbers 1 to 100 have been shuffled into them, one in each. One at a time, each prisoner goes in alone and may open 50 boxes. If every prisoner finds their own number, all of them go free; if even one fails, none do. They cannot talk once it starts, but they can agree a plan beforehand.
If each one opens 50 boxes at random, they each have an even chance, and all 100 succeed with odds of about 7.9 × 10-31 — no chance at all. There is a plan that frees them 31.2% of the time.
The plan: follow the loop
Each box has a number on its lid, 1 to 100 in order, and a different number hidden inside. A prisoner first opens the box whose lid shows their own number. Whatever number is inside, they next open the box with that number on its lid, and so on, following the chain. If the number inside is ever their own, they have found it.
Here is a small version with ten boxes, written out. Lids 1 to 10 hold 4, 9, 6, 7, 2, 10, 1, 3, 5, 8. Prisoner 3 opens box 3: box 3 holds 6, then box 6 holds 10, then box 10 holds 8, then box 8 holds 3. Their own number, on the 4th box. Notice where it was: the box holding a 3 pointed straight back to box 3, where they started. That always happens, because the number that sends you back to your first box is your own. So every chain is a loop, and a prisoner finds their number exactly when the loop they start on is short enough to walk round. In this example the loops are 1-4-7, 2-9-5 and 3-6-10-8, none longer than 5, so all ten would go free.
With 100 boxes, everyone goes free exactly when no loop is longer than 50. The plan does not change any one prisoner’s chance: the loop a given prisoner starts on is equally likely to be any length from 1 to 100, so each still finds their number exactly half the time. What it changes is that their failures come together. Either there is a long loop and everyone on it fails at once, or there is not and everyone succeeds — so the prisoners are no longer a hundred separate coin flips, but one.
Try it
Over many shuffles, how often 100 prisoners following the loops all go free
31.2%
against 7.9 × 10-31 if each opens 50 at random.
Where 31.2% comes from
A shuffle of 100 boxes can have at most one loop longer than 50, because two of them would need more boxes than there are. And the chance that a random shuffle has a loop of some particular length longer than half is exactly one over that length: 1/51 for a loop of 51, 1/52 for 52, and so on up to 1/100 for one loop through everything. Those can’t happen together, so the chance of a fatal loop is their sum, 68.8%, and the prisoners go free the other 31.2% of the time.
Why a loop of length k has a 1-in-k chance
Count the shuffles that contain one particular long loop length, say k. Pick which k boxes are on the loop; there are k − 1 choices for where the first one points, k − 2 for the next, and so on round the loop; and the boxes left over can be shuffled any way at all. Multiply those counts and divide by the number of possible shuffles (100 × 99 × … × 1, written 100!), and almost everything cancels: what is left is exactly 1/k. A long loop is rarer the longer it is, but only in proportion — a loop of 51 is 1/51, a loop of 100 is 1/100 — and those fractions add up to 68.8% for one group of 100.
More prisoners, barely worse
With 10 prisoners each opening 5 boxes, the loop plan wins 35.4% of the time. With 100 it is 31.2%. It keeps falling as the group grows, but never below 30.7% — that is 1 − ln 2 — however many prisoners there are. Random guessing, by contrast, halves with every extra prisoner. And no plan does better than following the loops: Curtin and Warshauer prove it is the best possible.
Questions people ask
- What is the 100 prisoners problem?
- 100 numbered prisoners must each find their own number by opening 50 of 100 boxes, with no communication once they start. If all of them succeed, all go free. Guessing at random gives them a chance of about 7.9 × 10^-31; following the loop strategy gives 31.2%.
- What is the strategy for the 100 prisoners problem?
- Each prisoner opens the box with their own number on it, then the box numbered with whatever they found inside, and keeps following that chain. Everyone succeeds exactly when no loop in the arrangement is longer than 50, which happens 31.2% of the time.
Check it yourself
The success rates are exact fractions, computed from scratch and checked against these before they ship.
100 Prisoners Problem — Wolfram MathWorld — the readable one
The loop strategy, the success rate of 0.3118278206 for 100 prisoners and the limit of 1 − ln 2 = 0.3068528194, all reproduced here to ten places. It traces the puzzle to Gál and Miltersen (2003).
The Locker Puzzle — Eugene Curtin and Max Warshauer, The Mathematical Intelligencer, 2006 — the proof (a journal paper, which may need a subscription)
The worked example of 10 players winning 893/2520 of the time, reproduced here exactly; the figure for 100; the proof that the rate never falls below 1 − ln 2; and the proof that no strategy does better.
This page’s dataset — Odds The Law
The success rate for every even group from 2 to 100 prisoners.
Try next
How the site works out its numbers is on the methodology page.