A puzzle that sounds impossible at first reading: 100 prisoners are numbered $1$ through $100$. There are $100$ sealed boxes in a room, each containing one of the numbers $1$ through $100$, randomly assigned (each used exactly once). Each prisoner enters the room one at a time, opens at most $50$ boxes, and must find the box containing their own number. If even one prisoner fails, all $100$ are executed. The prisoners may agree on a strategy beforehand but may not communicate once the procession starts.

Random guessing gives each prisoner a $50/100 = 1/2$ chance of finding their number, so the probability of all succeeding is $(1/2)^{100} \approx 8 \times 10^{-31}$. Effectively zero.

A specific strategy succeeds with probability $\approx 31.18\%$.

The strategy

Number the boxes $1$ through $100$. Prisoner $i$ first opens box $i$. They read the number inside, say $j_1$. Next they open box $j_1$, read $j_2$, then box $j_2$, and so on, until they either find their own number $i$ or have opened $50$ boxes.

That is the entire strategy.

Where the success rate comes from

The contents of the boxes define a permutation $\pi$ of $\{1, \ldots, 100\}$, where $\pi(i)$ is the number in box $i$. Prisoner $i$, following the strategy, traverses the cycle of $\pi$ that contains $i$:

where $k$ is the length of that cycle. Prisoner $i$ finds their own number at step $k$, which fits in the $50$-box budget iff $k \le 50$.

Because every prisoner uses the same strategy, all prisoners succeed iff every cycle of $\pi$ has length at most $50$. The fate of all $100$ prisoners is determined by a single property of one random permutation: whether its longest cycle exceeds $50$.

The probability

For a uniformly random permutation of $\{1, \ldots, n\}$, the probability that there is at least one cycle of length exactly $\ell$ is $1/\ell$ when $\ell > n/2$. The counting argument: the number of permutations of $\{1, \ldots, n\}$ that contain a fixed $\ell$-element subset arranged as a single cycle is $(\ell - 1)! \cdot (n - \ell)!$. The number of such $\ell$-subsets is $\binom{n}{\ell}$. Multiplying and dividing by $n!$ gives $1/\ell$.

When $\ell > n/2$, at most one cycle of that length can exist (two would overflow the permutation). So the events “permutation has a cycle of length $\ell$” for distinct $\ell > n/2$ are disjoint, and

where $L$ is the length of the longest cycle and $H_m = 1 + 1/2 + \cdots + 1/m$ is the $m$-th harmonic number. As $n \to \infty$ with $k = n/2$, this approaches $\ln 2 \approx 0.6931$, so

For $n = 100$ specifically, the exact value is $1 - (H_{100} - H_{50}) \approx 0.3118$.

The strategy converts the prisoners’ problem from $(1/2)^{100}$ chaos into a single $31\%$ check on the cycle structure of a random permutation.

Press new trial to draw a random permutation. The grid below shows what each prisoner would find inside each box. Boxes are colored by which cycle of the permutation they belong to. The cycle outlined in red is the longest one. The trial succeeds if and only if no cycle exceeds $50$. Press + 1000 trials to accumulate statistics.

A note on optimality: this is also (asymptotically) the best possible strategy. No strategy can succeed with probability much above $1 - \ln 2$ in the large-$n$ limit (Curtin and Warshauer, 2006). The cycle-following strategy is essentially as good as the prisoners can do.

References

• Anna Gál, Peter Bro Miltersen. The cell probe complexity of succinct data structures. Theoretical Computer Science, 379(3):405-417, 2007. (Where the puzzle first appears in the literature.)
• Eugene Curtin, Max Warshauer. The locker puzzle. The Mathematical Intelligencer, 28(1):28-31, 2006.
• Philippe Flajolet, Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009. Chapter II covers the cycle structure of random permutations in detail.