100 Prisoners and the Boxes

Problem. 100 prisoners are numbered 1 to 100. In a room are 100 closed boxes, each containing one prisoner’s number in random order. Each prisoner may open 50 boxes, must find their own number, and may not communicate afterwards or rearrange anything. All must succeed or all are executed.

They may agree on a strategy beforehand. What is the best strategy, and its success probability?

The naive answer

If each prisoner opens 50 boxes at random, each succeeds with probability $\frac{1}{2}$, and all 100 succeed with probability

$2^{-100}\approx 8\cdot 10^{-31}.$

Effectively zero.

The optimal strategy — cycle following

Prisoner $i$ opens box $i$. If it contains number $j$, they next open box $j$. Repeat.

Success probability: $\approx 31.18\%$.

Why it works

The box arrangement is a random permutation $\sigma$. Prisoner $i$ walks the cycle of $\sigma$ containing $i$, and their own number sits at the end of that cycle — the box that points back to $i$.

So prisoner $i$ succeeds iff their cycle has length $\le 50$.

All prisoners succeed iff the permutation has no cycle longer than 50. Every prisoner’s fate is determined by the same event, which is exactly why the strategy beats independence so dramatically: it makes the failures maximally correlated.

The probability

The probability that a random permutation of $2n$ elements has a cycle of length $\ell >n$ is $\frac{1}{\ell }$ (such a cycle is unique, and the count works out exactly). So

$\mathrm{Pr}[\text{failure}]={\sum }_{\ell =n+1}^{2n}\frac{1}{\ell }=H_{2n}-H_n\to \ln 2\approx 0.693,$

$\mathrm{Pr}[\text{success}]=1-(H_{100}-H_{50})\approx 1-0.6882=0.3118.$

And the limit as $n\to \infty$ is $1-\ln 2\approx 30.7\%$ — independent of the number of prisoners.

double successProbability(int n) {                 // n prisoners, n/2 openings
    double fail = 0;
    for (int l = n / 2 + 1; l <= n; l++) fail += 1.0 / l;
    return 1.0 - fail;
}

Optimality

Curtin and Warshauer (2006) proved this strategy is optimal — no strategy does better. The result is not merely a clever improvement; it is the best possible.

The general principle: correlate the failures

With independent strategies, $\mathrm{Pr}[\text{all succeed}]=\prod p_i$, which decays exponentially. The cycle strategy makes all outcomes depend on one event, so the product collapses to a single probability.

This is a genuinely transferable idea:

Setting	Correlation trick
100 prisoners	everyone follows the same permutation structure
Hat-guessing puzzles	agree on a parity convention
Distributed consensus	shared randomness
Derandomisation	replace independent bits with pairwise-independent ones
Coupon collector variants	coordinate the sampling

Hat puzzles are the closest relative: $n$ people wear coloured hats, see everyone else’s but not their own, and guess simultaneously. Agreeing on a parity convention lets $n-1$ of them always be correct, versus $n/2$ expected with independent guessing.

Permutation cycle facts

The analysis rests on standard facts about random permutations, worth knowing on their own:

Quantity	Value
Expected number of cycles	$H_n\approx \ln n$
Expected number of fixed points	1
$\mathrm{Pr}[\text{longest cycle}>n/2]$	$\ln 2\approx 0.693$
Expected length of the longest cycle	$\approx 0.6243n$ (the Golomb-Dickman constant)
$\mathrm{Pr}[\text{no fixed point}]$	$\to 1/e$ — see derangements
Expected length of the cycle containing element 1	$(n+1)/2$
Number of permutations with $k$ cycles	Stirling numbers of the first kind

Where cycle-following appears in algorithms

The same “follow the permutation” idea is a real technique:

• In-place permutation application — apply $\sigma$ to an array with $O(1)$ extra space by walking cycles;
• Cycle sort — the minimum number of swaps to sort is $n-(\text{number of cycles})$;
• Permutation parity — computable from the cycle count: $(-1{)}^{n-c}$;
• Permutation powers — ${\sigma }^k$ is computed per cycle by rotation;
• Cycle detection in functional graphs.

Why it is worth knowing

It is the most striking demonstration that structure beats independence: from $10^{-30}$ to $0.31$ with no additional information, purely by coordinating how the search is done. It is also a rare puzzle whose optimal solution has a short proof and a clean closed-form answer.

See also: Probability · Derangements · Cycle Detection