100 Prisoners, 50 Boxes Each, and a Strategy That Survives 31% of the Time

Independent guessing gives the prisoners 7.9 x 10^-31. Following the slip you just found gives them 0.311828, and the gap is thirty orders of magnitude from a rule you can state in one sentence. The strategy never raises anyone's individual chance above one half; it only makes the failures coincide, which is the whole lesson.

A hundred prisoners are numbered 1 to 100. In a room stand a hundred closed boxes, and inside them, in some order nobody knows, are slips carrying the same hundred numbers. One at a time, each prisoner enters, opens any fifty boxes of their choosing, and looks for their own number. Then the boxes are shut and the room is restored.

They may agree on a plan beforehand. Once the first one walks in, no signal of any kind is possible. If every single prisoner finds their number, all go free. If one fails, all hundred are executed.

The obvious verdict is that this is theatre. Fifty boxes out of a hundred is a coin flip each, so a hundred coin flips have to come up heads:

\left(\tfrac12\right)^{100} \;\approx\; 7.9 \times 10^{-31}.

(1)

There is a strategy that gets them to $31.18\%$ . Not a slightly better number. Thirty orders of magnitude better, from a rule you can explain in one sentence.

Follow the slip you just found

Prisoner $i$ opens box $i$ first. Inside is a slip with some number on it. Open that box next. Read the slip, open that box, and keep going for up to fifty openings.

That is the whole plan. No one chooses anything, no one needs to remember anything, and yet it works.

A permutation is a handful of loops

The slips define a permutation $\sigma$ : box $b$ contains the number $\sigma(b)$ . Chasing slips from box $i$ walks the sequence $i,\ \sigma(i),\ \sigma^2(i),\ \dots$ , and since a permutation of a finite set is invertible, that walk cannot wander off or branch. It comes back to where it started. Every permutation splits into disjoint cycles, and the walk traces the one containing $i$ .

The number the prisoner wants is $i$ itself, and the box holding it is the box that points back to the start, the last stop on the loop. So prisoner $i$ succeeds exactly when their cycle has length at most fifty. No approximation is involved.

The criterion, in full

Everyone survives if and only if the permutation has no cycle longer than 50. One fifty-one-cycle and every prisoner on it fails together; everyone else was never at risk. A hundred separate questions collapsed into one question about one object.

Fig. 1 — The same game, two draws. Only the largest block matters, and a single crossing kills the whole row.

Counting the permutations that kill them

A permutation of 100 elements can hold at most one cycle longer than 50, since two would need more than a hundred elements between them. Long cycles are therefore mutually exclusive, and the failure probability is a plain sum with no inclusion-exclusion to untangle.

Count the permutations with a cycle of length exactly $k > 50$ : choose which $k$ elements sit on it, arrange them into a cycle in $(k-1)!$ ways, and permute the remaining $100-k$ freely.

\binom{100}{k}\,(k-1)!\,(100-k)! \;=\; \frac{100!}{k}, \qquad\text{so}\qquad P(\text{longest} = k) = \frac1k.

The factorials cancel completely, which is the small miracle that makes this problem quotable. Summing over the fatal lengths:

P(\text{all survive}) \;=\; 1 - \sum_{k=51}^{100}\frac1k \;=\; 1 - \left(H_{100} - H_{50}\right) \;=\; 0.311828\ldots

(2)

Roughly one run in three. The prisoners are still likely to die, and the interviewer is not asking you to be optimistic. They are asking whether you notice that $31\%$ and $10^{-30}$ can describe the same hundred people.

Why the number barely depends on the hundred

Replace 100 by $2n$ and the allowance by $n$ . The same argument gives $1 - (H_{2n} - H_n)$ , and since $H_m = \ln m + \gamma + O(1/m)$ , the constants and the $\gamma$ cancel:

\lim_{n \to \infty}\; 1 - \left(H_{2n} - H_n\right) \;=\; 1 - \ln 2 \;=\; 0.306853\ldots

(3)

A million prisoners opening half a million boxes each survive with probability $30.7\%$ , essentially the same as a hundred. The ratio of what you are allowed to what exists is the only input, and everything else washes out.

What the strategy actually bought

This is the part worth carrying out of the room, and it is not the arithmetic.

Under the cycle rule, ask how likely a single named prisoner is to find their number. The cycle containing a fixed element is equally likely to have any length from 1 to 100, each with probability $1/100$ , so the answer is fifty hundredths:

P(\text{prisoner } i \text{ succeeds}) \;=\; \sum_{k=1}^{50}\frac{1}{100} \;=\; \frac12.

(4)

Exactly the same $1/2$ as random guessing. The strategy does not make anybody luckier, and no strategy could. What it changes is how the failures are arranged. Independent flips scatter them, so at least one lands almost surely. The cycle rule welds all hundred outcomes to a single feature of a single permutation, and welded outcomes either all hold or all break.

A portfolio person has met this already, wearing the other sign. Identical marginals, different dependence, and the distribution of the total moves enormously while every individual probability stays put. It is why a thousand independent bets behave so unlike a thousand correlated ones, and why a tranche can be rated on marginal default rates and still be worthless. Correlation was never a detail of the model. Here it is worth a factor of $10^{30}$ .

Sources and further reading

A. Gál and P. B. Miltersen, “The cell probe complexity of succinct data structures”, ICALP 2003 — where the puzzle first appears, as a lemma inside a data-structure lower bound
E. Curtin and M. Warshauer, “The locker puzzle”, The Mathematical Intelligencer 28 (2006), 28–31 — the proof that no strategy beats 1 − ln 2 in the limit
100 prisoners problem — the statement, the cycle argument and the usual variants
Random permutation statistics — where the 1/k law for the longest cycle comes from