One swap saves every prisoner

In the hundred prisoners problem, a hundred numbered slips are shuffled into a hundred numbered boxes, and each prisoner in turn may open fifty boxes looking for their own number. All must succeed or all are executed. The plan that beats the odds is to follow the cycles of the shuffle: each opens the box bearing their own number, then the box whose number they found there, and so on. A prisoner succeeds exactly when the cycle through their own box has at most fifty boxes, so everyone succeeds exactly when the shuffle has no cycle longer than fifty, which happens with probability $1 - (\tfrac{1}{51} + \cdots + \tfrac{1}{100}) = 0.3118$.

That essay ended by naming a variant: let one person see the whole room before the prisoners start, and allow them to swap the contents of two boxes. One swap is enough to make the prisoners certain to win. This essay computes what that swap does, what it is worth when each prisoner may open fewer boxes, and why, without a helper, the prisoners’ failures arrive in a way that no relaxation of the rules can soften.

What a swap does to the cycles #

A shuffle of boxes is a permutation, and following the slips from box to box traces its cycles. Swapping the contents of two boxes changes exactly two arrows: the box $a$ that pointed to $a'$ now points to $b'$, and the box $b$ that pointed to $b'$ now points to $a'$. If $a$ and $b$ are on different cycles, the change joins the two into one. If they are on the same cycle, it cuts that cycle into two, and the lengths of the pieces depend on how far apart $a$ and $b$ sit along it.

This is the same fact that gives every permutation its sign: a transposition changes the number of cycles by exactly one, so it changes the parity of the permutation. Here the parity is irrelevant and the lengths are everything. In the hero’s shuffle the longest cycle has 61 boxes and the others 16, 16 and 7. Following it, all 61 prisoners whose numbers lie on it would open fifty boxes without reaching their own slip. Swap the contents of two boxes 30 steps apart along that cycle, and it becomes a cycle of 30 and a cycle of 31. Every cycle is now at most fifty long, and every prisoner succeeds.

A shuffle of a hundred boxes can have at most one cycle longer than fifty, since two would need more than a hundred boxes between them. So the helper never needs more than one swap. They find the long cycle, if there is one, and cut it in half; the prisoners, who need not know whether a swap was made, follow exactly the plan they would have followed anyway. The chance that a swap is needed at all is $0.6882$.

Failures come all at once #

Without a helper, the prisoners following the cycles succeed or fail by whole cycles. Everyone on a cycle of at most fifty boxes succeeds; everyone on a longer cycle fails.

So the number who fail is either nought or the length of the one long cycle. The chance that a random shuffle has a cycle of a particular length $L$ greater than half is exactly $1/L$ — the count of shuffles with such a cycle is $\binom{100}{L}(L-1)!\,(100-L)!$, which is $100!/L$ — and those events are disjoint for different $L$ above fifty. The figure is therefore a spike at nought and a gently falling shelf from 51 to 100, with nothing in between.

That has a consequence for a natural relaxation. Suppose the rules were softened, so that the prisoners win if at most ten of them fail, or thirty, or fifty. Under the cycle plan, every one of those rules is won exactly as often as the strict rule, 31.18% of the time, because there is no shuffle in which between one and fifty prisoners fail. The plan that is best for “all must succeed” spends its failures in large blocks, and the same correlation that makes the all-or-nothing chance so high makes partial success impossible. As in the hat game, where wrong guesses are made to arrive together, the average is untouched — fifty prisoners fail on average under this plan, as under any plan, since each prisoner’s own chance is one half — and only its distribution has been rearranged.

Fewer boxes, more swaps #

If each prisoner may open only $k$ boxes, the cycle plan succeeds exactly when no cycle is longer than $k$, and a helper must cut every cycle that is. A cycle of length $L$ must be cut into pieces of at most $k$, which takes $\lceil L/k \rceil - 1$ cuts, one swap each. So the fewest swaps the helper needs is

$$S = \sum_{\text{cycles}} \left(\left\lceil \frac{L}{k} \right\rceil - 1\right).$$

No cleverer sequence of swaps does better. A swap changes the number of cycles by one, and the target shuffle must have at least $\sum \lceil L/k\rceil$ cycles if each of the original cycles is to end up in pieces of at most $k$; a swap that joins two cycles moves the wrong way and has to be undone by a later one. The argument is short, but it is the kind of claim that is worth testing, and the test is below.

The distribution of $S$ for a random shuffle comes from the exponential formula, the same device that counts permutations with no fixed point: give each cycle of length $L$ the weight $y^{\lceil L/k\rceil - 1}$, and the probability generating function $a_n(y)$ for shuffles of $n$ boxes satisfies

$$a_n(y) = \frac{1}{n}\sum_{L=1}^{n} y^{\lceil L/k\rceil - 1}\, a_{n-L}(y), \qquad a_0 = 1.$$

Each coefficient of $a_{100}(y)$ is the exact chance of needing that many swaps. At $k = 50$ it is 0.3118 for none and 0.6882 for one. At $k = 34$ the helper needs one or two swaps nearly always, with mean 1.452; at $k = 25$ the mean is 2.346 and at $k = 20$ it is 3.228. The means have a simpler form than the distributions: a random shuffle of $n$ has on average $1/L$ cycles of length $L$, for every $L$, so the average number of swaps is $\sum_L (\lceil L/k\rceil - 1)/L$, a sum of harmonic tails.

What each swap is worth #

Allowing the helper $s$ swaps turns the question into the chance that $S \le s$, read from the same distributions. With no swap it is the familiar curve, 0.3118 at fifty boxes and falling fast below. One swap lifts the whole curve and makes fifty boxes certain. Two swaps make 34 boxes certain, and three make 25 certain. In general, with $s$ swaps a hundred prisoners are sure to win as soon as each may open $\lceil 100/(s + 1)\rceil$ boxes. The reason is a count: every cycle that needs $c$ cuts has more than $ck$ boxes, so the cuts needed add up to less than $100/k$, and with $k = \lceil 100/(s+1)\rceil$ that is less than $s + 1$.

One box fewer, and certainty is lost: with one swap and 49 boxes the chance is 0.980, with two swaps and 33 boxes 0.990, with three swaps and 24 boxes 0.955. Each of those losses is a shuffle like a single cycle of all hundred boxes, which with $k = 49$ needs two cuts and receives one. The swaps buy certainty in steps that shrink: the first takes the prisoners from 0.31 to certainty at fifty boxes, and each later one lowers the boxes needed by a smaller amount, since the boxes needed fall like $100/(s+1)$.

Every shuffle of seven, searched #

The claim that cutting is optimal was checked exhaustively at seven boxes. All 5,040 shuffles were listed, and for each $k$ from 1 to 6 the shuffles already satisfying the limit were marked at distance nought; a breadth-first search then spread outwards, one swap at a time, until every shuffle had its distance — the fewest swaps that reach a shuffle with every cycle at most $k$. In every one of the $6 \times 5{,}040 = 30{,}240$ cases the searched distance equals the formula. The table also shows the extremes: with $k = 1$ the target is the identity, and the 720 single cycles of all seven boxes need six swaps, the most possible, which is the classical fact that sorting a permutation takes $n$ minus its number of cycles transpositions; with $k = 6$ only the 720 seven-cycles need anything, and they need one.

The search runs outwards from the good shuffles rather than inwards from each bad one because a swap is its own inverse: the shuffles one swap away from a good one are exactly the shuffles one swap can repair. It is the same technique that found the far end of the sliding puzzle, with the puzzle’s slides replaced by swaps.

Twenty thousand rooms #

A simulation of the whole procedure confirms that nothing in the plan depends on luck once the helper acts. In 20,000 rooms the longest cycle exceeded fifty in 13,760, close to the exact 0.6882, and its length above fifty followed the $1/L$ shelf. Without help the prisoners won 0.3120 of the rooms. In each room with a long cycle the helper swapped the contents of the first box of the long cycle and the box halfway round, and then all hundred prisoners were simulated following their chains, each allowed fifty openings. Every prisoner found their number in every room.

Short cycles are independent, the long one is alone #

The two halves of these computations behave differently, and the difference is the reason the helper’s job is so simple. The short cycles of a random shuffle behave almost independently of one another: the number of cycles of length $L$, for any fixed $L$, is close to a Poisson count with mean $1/L$, and the counts for different small lengths are close to independent. The case $L = 1$ is the number of prisoners who find their own number in their own box, which is Poisson with mean one in the limit, and a Poisson law of the same kind appears in a card game almost nobody wins, where forbidden matches are counted the same way.

The long cycles behave nothing like that. Two cycles longer than half cannot coexist, so their counts are as far from independent as counts can be, and the chance of one of length $L$ is exactly $1/L$ rather than approximately. The helper deals only with the long cycles, which is why one swap suffices at half the boxes; with fewer boxes each, the helper has to deal with cycles longer than $k$, of which there can be several, but never more than $100/k$ of them, and the exact distribution of $S$ has to account for all of their sizes at once. The exponential formula does that bookkeeping exactly: it builds a random shuffle as a set of cycles, weighting each cycle by $1/L$, and the weight $y^{\lceil L/k\rceil - 1}$ simply counts the cuts each one will need.

The swap changes something else as well. After the helper’s cut the shuffle is no longer uniformly random, and the prisoners’ plan does not need it to be: the plan’s success depends only on the cycle lengths, and the cut has made every one of them small. The helper is using the same freedom the warden would use against the prisoners, a deliberate choice of shuffle, in the prisoners’ favour, and the asymmetry between the two is that the warden must defeat a plan the prisoners randomise, while the helper only has to repair one cycle that chance produced.

Why one look is worth so much #

The prisoners’ trouble was never a lack of information about their own box; it was that the shuffle’s long cycle, if it exists, defeats all of them at once. A helper who sees the room needs to know only one thing, where the long cycle is, and one swap removes it. The value of that look is the jump from 0.3118 to 1, and it is so large because the failures it prevents are concentrated, all in one cycle, rather than spread over many independent prisoners.

The structure behind it is the structure of a random permutation’s cycles. The longest cycle of a random shuffle of $n$ occupies a fraction of the boxes whose distribution settles, as $n$ grows, to a fixed law; the chance that it exceeds half is $\ln 2$ in the limit, and the same law governs the largest prime factor of a random integer. A swap that halves that one cycle turns a problem about the largest piece of a random partition into a certainty, and the further swaps, for fewer boxes, act on the few next-largest pieces in the same way.

What the pictures cannot show #

The helper’s swap is worked out for prisoners who all follow the cycle plan, which needs the boxes and the prisoners’ numbers to be matched up in advance; a warden who relabels the boxes is handled by the shared random relabelling of the original problem and is not drawn. The exhaustive check stops at seven boxes, where every shuffle can be listed; the formula for the fewest swaps is proved for every size by the counting argument, and the distributions at a hundred are exact sums rather than samples. The simulation tests the plan, not the formula, and at twenty thousand rooms it cannot see a failure rare enough to occur less often than once in tens of thousands, which is why the argument rather than the simulation carries the claim that every room is won.

Swaps counted, the variant quoted #

Computed here: the hero’s shuffle and its split; the distribution of failures under the cycle plan, from the counts $100!/L$; the exact distributions of the fewest swaps for a hundred boxes and $k = 50, 34, 25, 20$ by the exponential formula, with their means; the chance of winning with up to three swaps for every $k$, and the points of certainty at $\lceil 100/(s+1)\rceil$ with the chances one box below; the breadth-first search over all 5,040 shuffles of seven for each $k$; and 20,000 simulated rooms with and without the helper.

Quoted: the original problem and its cycle plan, from Anna Gál and Peter Bro Miltersen’s work on data structures and the later puzzle literature; the one-swap variant as a known variation; the limit $\ln 2$ and its connection with prime factors.

Still open: help that sees less #

The helper here sees everything and needs to change almost nothing. What can a helper achieve who sees only part of the room, or who may only swap boxes they have opened? If the helper opens boxes the same way a prisoner does, following cycles, they can find a long cycle only by walking it, and how many openings and how many swaps then guarantee success is a question with partial answers. The opposite relaxation — prisoners allowed to fail in limited numbers, with no helper — is open in a different way: the cycle plan is useless for it, as the failure distribution shows, and what the best plan looks like when, say, ten failures are tolerated is not known in general. The cycle plan maximises the chance that everyone succeeds precisely by sacrificing every intermediate outcome, and a plan for a softer goal has to give some of that back.

Cutting the one long cycle #

Following the cycles makes the prisoners’ fate a single fact about the shuffle, whether it has a cycle longer than they may open, and a helper who sees the room can change that fact with one swap per cut: $\sum(\lceil L/k\rceil - 1)$ swaps, never fewer. At fifty boxes that is never more than one, and the prisoners’ 0.3118 becomes certainty; at 34, 25 and 20 boxes a helper needs on average 1.452, 2.346 and 3.228 swaps, and $s$ swaps make $\lceil 100/(s+1)\rceil$ boxes always enough. Without a helper, the failures come all at once: none with probability 0.3118, and otherwise at least 51.