A hundred prisoners. A hundred boxes, each hiding one number. Open fifty; if any one of you fails to find their own, all hundred die. Guessing, you are already dead. There is a plan that gives you almost a one-in-three chance — and nothing does better.
The warden offers a last game. In a room sit a hundred boxes in a row, and inside them — shuffled blindly — are a hundred slips numbered 1 to 100, one to a box. One by one, each prisoner enters alone, opens any fifty boxes, looks, and leaves everything exactly as it was, touching nothing, telling no one what they saw. If every prisoner finds the slip bearing their own number, all hundred go free. If even one comes up empty, all hundred are executed. They may plot beforehand, but once the game starts there is no signal, no mark, no communication of any kind.
Reach for the arithmetic and it looks hopeless. A single prisoner opening fifty of a hundred boxes finds their number with probability exactly one half. A hundred prisoners, each needing to succeed independently, all clear the bar with probability (1/2)100 — about 1 in 1030, one in a nonillion. You could run this execution every second since the Big Bang and never once watch the room walk free. Any sane prisoner concludes the game is a formality.
It is not. There is a strategy — provably the best one — under which the whole room survives almost a third of the time: 31.18%. The prisoners agree on it in the yard beforehand; not one bit of information passes between them during the game; the warden may shuffle the boxes as adversarially as he likes. And still, better than one room in four lives. The gap between 10-30 and 0.31 is one of the most violent surprises in all of probability, and every claim on this page is computed in front of you and was proven three independent ways before it was printed.
Here is a room — a hundred boxes, the slips inside hidden. Pick a prisoner and watch them play. Under guess, they open fifty boxes at random. Under the loop, they do one strange thing: start at the box bearing your own number, read the slip inside, go to the box with that number, and repeat — following the chain wherever it leads, up to fifty opens. Then judge the whole room.
Following the loop, a prisoner is walking a cycle of the shuffle, and the cycle always returns to its own start — to the box holding their number. They fail only if that cycle is longer than fifty. So the room lives or dies on a single question: is the longest loop in this shuffle at most fifty?
Run the loop strategy on a few prisoners and something clicks: each one traces a closed loop that ends precisely back where it began. That is not luck. The shuffled boxes define a permutation — box b contains slip σ(b) — and a permutation decomposes into disjoint cycles. Starting at box p and following slips, prisoner p walks exactly the cycle containing p, and the slip numbered p sits in the box that closes that loop. They find it on the step equal to the length of their cycle — no sooner, no later.
Every prisoner is on the one loop that ends at their own number. The only way to fail is for that loop to run longer than fifty boxes.
So the entire fate of the room collapses to the cycle structure of a single random shuffle. Everyone survives if and only if every cycle has length at most fifty. And here is the lever the whole strategy pulls: in a hundred boxes there can be at most one cycle longer than fifty — two such would need more than a hundred boxes between them. The prisoners are not betting that all the loops are short. They are betting against the existence of that single over-long loop. Deal rooms below and watch the cycle spectrum; the killer, when it comes, is always alone.
The spectrum shares this page's current room with Instrument I — deal here and the grid above re-shuffles too. A bar turns red only when it crosses the fifty line: the lone loop that dooms all hundred.
Claims are cheap; this one you can watch earn itself. Below, the room is run over and over — a fresh random shuffle each time, every prisoner playing it out box by box (the very same engine that drives the grid above). The loop strategy's survival rate climbs and settles onto the exact value 0.3118. The guessing strategy's rate sits, flat, at zero — and stays there, because to see it succeed once you would need to run not ten thousand rooms but a nonillion.
Guessing has never once survived here, and never will in any run you have the patience for. That flat red bar is the nonillion, drawn to scale.
The number is not mysterious; it is a short sum. A random shuffle of 2k boxes has a loop of length exactly L with probability precisely 1/L whenever L > k (a small, exact counting fact — and these long-loop events can't overlap). So the chance of some over-long loop is just
P(doomed) = 1/51 + 1/52 + ⋯ + 1/100 = H100 − H50 ≈ 0.6882
and the room survives with probability 1 − 0.6882 = 0.3118. As the room grows, that tail sum slides toward ln 2, so the survival probability approaches a clean constant: 1 − ln 2 ≈ 0.3069. A thousand prisoners, a million, a billion — give each of them half the boxes and the room still walks free almost a third of the time. Dial it yourself.
| Guessing this room | 8.0 × 10⁻³¹ |
|---|---|
| The loop strategy | 0.311828 |
| Improvement factor | 3.9 × 10²⁹ × |
At the half-the-boxes allowance the curve passes through the famous ≈0.31. Notice how cruel the cliff is just below it, and how the survival climbs only slowly above it: even letting each prisoner open ninety of the hundred boxes leaves a real chance of death.
Nothing supernatural happens; no information crosses the room. What the prisoners do is correlate their failures. Guessing, each prisoner's fate is an independent coin — and a hundred independent coins almost never all land heads. The loop strategy throws away that independence on purpose: it ties every prisoner's success to the same hidden object, the cycle structure of one shuffle. Now they nearly all win together or nearly all lose together. The total probability of any single prisoner failing is unchanged — still one half — but the failures are herded into the same rare rooms, so the good rooms are good for everyone at once. You cannot raise any individual's odds; you can choose how those odds are braided together.
And remarkably, no cleverer plan exists. Curtin and Warshauer proved in 2006 that the cycle-following strategy is optimal — no strategy, however baroque, beats 1 − (H100 − H50). The loop is not just a good idea. It is the best idea there is.
You can't change anyone's odds. You can only decide whether the room rises and falls together.
This is why the result keeps surfacing far from puzzle books — in the design of pointer-chasing data structures (where it was born), in coding theory, in any place where many small bets can be made to share a common cause — insurance, redundant disks, why a diversified portfolio and a synchronized crash are two faces of one coin. The deepest lesson of the hundred prisoners is not about loops at all. It is that independence is a choice — and sometimes the way to survive a hopeless game is to agree, in advance, to live or die as one.
A lighter companion to this page — the same puzzle told as a three-minute story, without the instruments — lives in the Field Notes as "One in a Nonillion, or One in Three."
Every probability on this page is computed live in your browser, and each was proven three independent ways offline before it was printed, in /research/hundred-prisoners/ (22/22 checks pass):
Provenance, checked. The problem was introduced by Anna Gál and Peter Bro Miltersen in "The cell probe complexity of succinct data structures" (ICALP 2003, pp. 332–344) — born not as a prisoner puzzle but as a data-structure lower-bound game about strips of paper, with finding the cycle-following strategy left as an exercise. By the commonly cited account, Miltersen had conjectured that independent players could do no better than the trivial bound, and his Aarhus colleague Sven Skyum pointed out that a coordinated strategy does far better (we could not locate a first-person primary source for this anecdote, so it is reported as the standard account, not established fact). The familiar prisoner/box framing came from later popularizers — Christoph Pöppe (Spektrum der Wissenschaft, 2006) and Peter Winkler, whose "Names in Boxes" puzzle appears in The College Mathematics Journal 37(4) (2006) and his book Mathematical Mind-Benders (2007). The optimality of cycle-following — that no strategy beats it — was proven by Eugene Curtin and Max Warshauer, "The locker puzzle," The Mathematical Intelligencer 28(1):28–31 (2006), via Foata's transition lemma. Accessible popular treatments worth a look: Veritasium (2022), Stand-up Maths (2019), and the DataGenetics write-up (2014).
Honest limits: the prisoners must agree the strategy beforehand and share a fixed labelling of the boxes; the result is for a uniformly random arrangement (a maximally adversarial warden who knows the strategy can do no better than chance against this plan — the per-prisoner success rate is one half no matter what he does). "1 in a nonillion" is (1/2)100 ≈ 7.89 × 10⁻³¹ rounded; "31 in 100" is 0.31183 rounded. The 1 − ln 2 figure is the large-room limit, not the n=100 value.