Published 13 September 2026

100 prisoners and boxes

One hundred prisoners face one hundred labeled boxes. A uniformly random permutation places each prisoner’s number in exactly one box. Each prisoner enters alone and may open at most fifty boxes. The group succeeds only if everyone finds their own number. They can agree on a strategy beforehand but cannot communicate, mark boxes, or rearrange contents during the attempts.

Opening an independently chosen random half of the boxes gives each prisoner success probability one half. The chance that all those independent choices work is 2⁻¹⁰⁰≈7.89×10⁻³¹. The cycle strategy keeps the individual success probability at one half while dramatically changing the dependence between successes. Review joint events and independence and permutations.

Let the numbers tell you where to go

Prisoner i begins with box i. If it contains j, the next box is j; continue until finding i or exhausting the budget. A permutation splits into disjoint cycles, so this route follows the unique cycle containing i. The prisoner finds their own number when that cycle closes.

For six boxes containing [3,1,2,5,4,6], the cycles are 1→3→2→1, 4→5→4, and 6→6. Every cycle has length at most three, so all six prisoners succeed with three openings each. Prisoner 1 opens boxes 1,3,2 and finds slips 3,2,1. A cycle of length four would make every member of that cycle fail under the same budget.

The important event is therefore that the longest cycle has length at most N/2. Individual successes are highly dependent: everyone in a given cycle succeeds or fails together. Multiplying their marginal probabilities would discard exactly the dependence the strategy exploits.

Count the bad cycles

For a specified length k, choose its k labels, arrange them into a cycle in (k−1)! ways, and permute the remaining labels in (N−k)! ways. Dividing by N! gives expected number of k-cycles:

When k>N/2, there can be at most one such cycle. Its expected count then equals its occurrence probability. Events for different lengths greater than N/2 are mutually exclusive, because two such cycles cannot fit in N labels. Hence, for even N:

For N=4 the value is 1−1/3−1/4=5/12, corresponding to ten of the twenty-four permutations. For N=100 it is approximately 0.311828, or 31.18%. As even N grows, the sum approaches ln 2, so success approaches 1−ln 2≈30.69%.

For a fixed prisoner, their cycle length is uniform on 1,…,N: count cycles containing that label to get (N−1)! permutations for each possible length. Exactly half of those lengths fit. The improved group probability comes from coordination, not an improved individual marginal chance.

Which assumptions carry the result?

The probability is over uniform permutations, not over the single permutation on screen. An adversary who knows the labels and deliberately chooses a long cycle can defeat this fixed strategy. Likewise, permitting communication, moving slips, or changing the opening budget defines another problem.

The short failure formula above uses the half-box budget. With a substantially smaller budget, several over-budget cycles can coexist, so simply adding their expected counts would overcount failure. This experiment varies even N while keeping the budget exactly N/2.

Sources

Richard Stanley’s algebraic-combinatorics notes, section 12.1 present the cycle strategy and its probability calculation. The six-box walk and four-box enumeration above make the mechanism directly inspectable.