Thank you for visiting this site. This article covers the puzzle acclaimed as the masterpiece of modern logic puzzles: “the 100 prisoners problem.”
One hundred prisoners are numbered 1 through 100, and in another room stand 100 boxes. Inside the boxes are slips numbered 1–100, one per box, in random order. The prisoners enter one at a time, and each must open at most 50 boxes and find the slip bearing their own number. If even one fails, all are executed. No communication after entering; no moving the boxes. If everyone opens boxes at random, the survival probability is one-half to the hundredth power — a hopeless figure with 30 zeros after the decimal point. Yet with one particular way of opening boxes, survival leaps to about 31%.
What Is the 100 Prisoners Problem?
The 100 prisoners problem is a probability puzzle with a structure that strains belief: you cannot raise any individual’s success probability, yet you can dramatically raise the whole team’s. The rules, in order:
- 100 prisoners, numbered 1–100
- In a separate room, 100 boxes, each containing one slip numbered 1–100, placed at random
- Prisoners enter one at a time and may open up to 50 boxes; finding your own numbered slip counts as success
- Opened boxes are closed again exactly as found. Nothing may be moved or marked
- Earlier and later prisoners cannot communicate at all. One strategy meeting is allowed, before anyone enters
- Everyone goes free only if all 100 succeed
Each prisoner opens only 50 of 100 boxes, so no cleverness can push any individual’s success probability above 50%. Multiply that across 100 people and survival is effectively zero. Everyone reaches this conclusion — which is exactly why the answer lands with such force.
The Youngest Classic, Born in 2003
The puzzle’s history is unusually recent for a logic puzzle, with a clear paper trail. In 2003, the Danish computer scientist Peter Bro Miltersen presented the prototype in a paper co-authored with Anna Gál. It arose from theoretical computer science — research probing the limits of data structures.
Delightfully, Miltersen himself is said to have initially believed “no good strategy exists.” The strategy later found by his colleague Sven Skyum was brilliant beyond the experts’ expectations, and in 2006 the mathematicians Curtin and Warshauer supplied the proof that no better strategy exists — it is optimal.
The puzzle then became a new standard of the mathematical puzzle world, and when a popular science video channel covered it in 2022, it exploded into general fame. A problem that claimed the seat of “modern classic” within twenty years of its birth — a rare thing.
The Answer: Follow the Numbers, Starting from Your Own Box
The strategy is almost anticlimactically simple.
First open the box bearing your own number. Then open the box whose number is written on the slip inside. Then the box named by that slip. Repeat, up to 50 times.
Prisoner 28, say, opens box 28 first. If it holds slip 52, next comes box 52. If that holds slip 7, next is box 7. Each slip names the next box to open — that is the entire rule.
At first glance it seems no better than random. But a decisive property hides inside. Following the box-to-slip correspondence, you must eventually arrive at the slip bearing your own starting number. The journey that began at box 28 ends the instant a box yields slip 28. Getting lost is impossible. The only question is whether the journey ends within 50 steps.
The Cycle Mathematics Behind the 31%
The correspondence between boxes and slips is what mathematics calls a “permutation.” And every permutation decomposes into loops (cycles). If box 28 → box 52 → box 7 → back to box 28, those three boxes form a loop of length 3. The world of 100 boxes splits exactly into a collection of such loops.
A prisoner’s journey is nothing other than one full lap of the loop containing their own number. If the loop’s length is 50 or less, every prisoner on it reaches their slip within 50 steps. If even one loop of length 51 or more exists, every prisoner on that loop fails.
Everyone’s fate thus condenses into a single question: “Does a random permutation contain a loop longer than 50?”
A loop of length 51+ can exist at most once (51+51 exceeds 100). The probability of a big loop of exact length k works out to “1/k,” so the failure probability is the sum of 1/51 through 1/100 — about 69%. Hence success probability: about 31%. Scale up the number of prisoners and the value only creeps down to about 30.7%. Whether 100 prisoners or a million, the survival rate holds near 30%.
Check it on a small case: 4 prisoners, 4 boxes, 2 openings each. Failure happens with a loop of length 3 (probability 1/3) or length 4 (probability 1/4) — together 7/12 — so success is 5/12, about 42%. Random opening gives all-succeed odds of 1/16 (about 6%). Even in a world of four, the strategy’s power shows plainly.
Individual Fates Unchanged — Only How Fates Overlap Changes
Now recall the opening’s “50% wall.” In fact, even with the cycle strategy, each individual prisoner’s success probability remains exactly 50%. The probability that your own loop has length 50 or less computes to precisely one-half. The wall stands unbreached, to the millimeter.
So what changed? The way successes and failures overlap. Under random strategy, 100 fates are independent events, so all-success essentially never occurs. Under the cycle strategy, prisoners on the same loop either all succeed or all fail — 100 fates are bundled into a handful of loops. No long loop: everyone lives. One long loop: many sink together. By herding failures into the total-wipeout corner and consolidating successes into “everyone survives,” only the all-success probability shoots upward.
The principle is identical to Ebert’s hat game from this series’ hat puzzle article: “you cannot change individual odds, but you can design the correlation of wins and losses.” The idea extends to how insurance works by pooling many policyholders’ risks, and to adjusting the co-movement of assets in a portfolio — one of the secret arts of the world of probability.
Why Start from Your Own Numbered Box?
Because starting there guarantees the loop you are tracing terminates at your own slip. The journey ends just before the loop closes back on its start — at the box whose slip bears the starting number. If your start is your own number, that final slip is exactly the one you seek. Start from an arbitrary box and you risk circling forever around a loop that doesn’t contain your slip — the guarantee evaporates.
What If the Warden Arranges the Slips Maliciously?
Sharp question — now that the strategy is famous, a warden who deliberately builds a loop of length 51+ wipes everyone out. But there is a countermeasure. The prisoners agree in advance on a shared “relabeling table” for box numbers, and everyone traces through that relabeling. Compose the warden’s arrangement with the prisoners’ own random permutation and the result is again a random permutation — the 31% comes back. Washing out the adversary’s malice with your own randomness: a move straight out of cryptography.
What If You Can Open 60 Boxes, or 30?
The success probability becomes “the chance no loop exceeds that number.” With 60 boxes it rises to about 49%; with 70, about 64%. Fall below half, though, and multiple long loops become possible at once — the arithmetic grows complicated and the success rate plunges. The setting of exactly half — 50 boxes — is the exquisite calibration that maximizes surprise: it looks hopeless, and one-third survive. For comparison, under random opening even 60 boxes gives all-success odds of 0.6 to the 100th power — still effectively zero.
Related Logic Puzzles
See “the hat puzzle,” sharing the principle of designing how wins and losses overlap; “the secretary problem,” likewise maximizing odds through strategy; and the classic collapse of probabilistic intuition, “the Monty Hall problem.”
Summary
This article covered “the 100 prisoners problem.”
No one can break the 50% wall, yet the all-survive probability leaps from nearly 0% to 31%. If the reveal still leaves you feeling tricked by a fox, I suspect it is because we carry the habit of thinking about probability only one person at a time. What this puzzle teaches is that probability offers design space not just in “size” but in “how outcomes overlap.”
Start at your own box; follow the slips. The way this simple rule re-bundles 100 fates into a few loops is, no matter how many times I think it through, nothing short of magnificent. When I first learned the answer, I doubted it for quite a while — and crushing that doubt by hand on small cases is part of the fun. Do try the 4-prisoner version yourself.
To return to the full list of logic and probability puzzles, follow the link below.
Thank you for reading. We hope to see you in the next article.
📚 Series: Logic & Probability Puzzles (10/11)
