The 100 Prisoners Puzzle

Definition The 100 prisoners problem is a probability puzzle with fixed rules. There are 100 people, numbered 1 to 100, and a room with 100 boxes, also numbered 1 to 100. Each box holds one slip of paper, the slips carry the numbers 1 to 100, and every number is in exactly one box. The slips are placed by a uniformly random permutation, so each of the $100!$ possible arrangements is equally likely, and the arrangement does not depend on the group’s plan. Before the first person enters, the group may agree on a strategy, and after that its members cannot communicate in any way. The people enter the room one at a time. Each may open at most 50 boxes, one after another, choosing each box after seeing what the earlier ones held. Each person then leaves the room exactly as it was found, with every box closed, every slip in its own box and no marks left behind. The group wins only if every one of the 100 people opens the box that holds their own number. If each person opens 50 boxes chosen at random, independently of everyone else, the group wins with probability $(1/2)^{100}$. With the cycle-following strategy described below, the group wins with probability

about 31.18 percent. This formula is exact for 100 people who may each open 50 boxes. The number $1 - \ln 2 \approx 0.3069$ that is often quoted is the limit of the same calculation for larger and larger groups in which each person may open half of the boxes, not the answer for 100 people.

Definition A permutation of the numbers 1 to $n$ is a rule $\pi$ that assigns to each number $b$ from 1 to $n$ a number $\pi(b)$ from 1 to $n$, in such a way that each number is assigned exactly once. In the puzzle, $\pi(b)$ is the number on the slip in box $b$. There are

permutations of $n$ numbers. A permutation is uniformly random when each of the $n!$ permutations has the same probability $1/n!$. Then each box holds each number with probability $1/n$, but the boxes are not independent of one another, because no number can appear in two boxes.

Definition Let $\pi$ be a permutation of the numbers 1 to $n$, and start at a number $b$. Applying $\pi$ again and again gives the sequence $b, \pi(b), \pi(\pi(b)), \ldots$, and since there are only $n$ numbers, some number must eventually repeat. The first number to repeat is $b$ itself, because $\pi$ never sends two different numbers to the same number. If the sequence first returns to $b$ after $k$ steps, the $k$ different numbers it visits form the cycle containing $b$, and $k$ is the length of that cycle. Every number lies in exactly one cycle, so the cycles split the numbers 1 to $n$ into separate groups whose lengths add up to $n$. A cycle is written in parentheses in the order it is followed, so $(1\ 4\ 2)$ means that 1 goes to 4, 4 goes to 2 and 2 goes back to 1. For any length $k$ with $n/2 < k \le n$, a uniformly random permutation of $n$ numbers has a cycle of length $k$ with probability exactly $1/k$. To count these permutations, choose the $k$ numbers of the cycle in $\binom{n}{k}$ ways, link them into a cycle in $(k - 1)!$ ways, and arrange the other $n - k$ numbers in any of $(n - k)!$ ways. The factor $(k - 1)!$ appears because the $k$ chosen numbers can be listed in $k!$ orders and each cycle appears $k$ times among them, once for each starting number. A permutation cannot have two cycles longer than $n/2$, since together they would need more than $n$ numbers, so no permutation is counted twice, and the count is

Dividing by the $n!$ equally likely permutations gives $1/k$.

Definition In the cycle-following strategy for the 100 prisoners problem, person $i$ first opens box $i$. Whenever the slip shows a number $j$ other than $i$, the next box that person opens is box $j$, and the search ends when the slip with $i$ appears or after 50 boxes. The boxes opened are $i, \pi(i), \pi(\pi(i))$ and so on, which is the cycle containing $i$, followed from box $i$. The slip with number $i$ lies in the last box of that cycle, the one that leads back to box $i$, so person $i$ finds it on opening number $k$, where $k$ is the length of the cycle containing $i$. Hence person $i$ succeeds exactly when that cycle has length at most 50, and the whole group wins exactly when every cycle of $\pi$ has length at most 50. The group loses exactly when there is a cycle of some length $k$ from 51 to 100. No two of these 50 cases can happen together, because two such cycles would need more than 100 numbers, and each has probability $1/k$, so

Each person alone still succeeds with probability exactly $1/2$, because the cycle containing person $i$ is equally likely to have any length from 1 to 100. For each length $k$, the other $k - 1$ members of that cycle can be chosen and placed after $i$ in $\binom{99}{k-1}(k - 1)!$ ways and the remaining numbers arranged in $(100 - k)!$ ways, which multiply to $99!$, one hundredth of all permutations. With $2n$ people who may each open $n$ boxes, the same argument gives the winning probability

which is $1/2$ for two people and decreases as $n$ grows, approaching $1 - \ln 2 \approx 0.3069$ without ever reaching it. The calculation needs every rule of the puzzle and the uniformly random arrangement. If whoever fills the boxes knows the strategy and wants it to fail, putting all 100 numbers in one cycle defeats it every time. The group can protect itself by agreeing on a uniformly random permutation $\sigma$, chosen independently of the arrangement and kept secret from whoever fills the boxes. Person $i$ then starts at box $\sigma(i)$ and, after finding a number $j$ other than $i$, opens box $\sigma(j)$ next. For every arrangement of the slips, the group then wins with the same probability, about $0.3118$.