One Hundred Prisoners and One Hundred Boxes

The naive baseline. If each prisoner opens 50 boxes at random, each succeeds with probability $\tfrac12$, and all succeed with probability $2^{-100} \approx 10^{-30}$.

The strategy. Prisoner $k$ opens box $k$ first. Whatever number is on the slip inside, they open that box next, and keep following the slips, up to 50 boxes.

Step 1: The slips form loops. Draw an arrow from each box to the box named by the slip inside it. Every box has exactly one arrow going out (its own slip) and exactly one coming in (exactly one slip names it). So the arrows split the boxes into closed loops.

Step 2: Why this helps. Prisoner $k$ starts at box $k$ and walks around the loop that contains box $k$. Slip $k$ is in the box whose arrow points back to box $k$, which is the last box of the loop. So prisoner $k$ finds their slip after exactly as many boxes as the loop has. That means:

• prisoner $k$ succeeds exactly when the loop through box $k$ has at most $50$ boxes;
• everyone succeeds exactly when no loop has more than $50$ boxes.

Step 3: Count the arrangements with a long loop. All $100!$ ways of putting the slips in the boxes are equally likely. Fix a length $\ell$ between $51$ and $100$. Every arrangement with a loop of exactly $\ell$ boxes can be built in three steps:

1. Choose which $\ell$ boxes are in the long loop: $\binom{100}{\ell}$ ways. This is just picking a set of $\ell$ boxes out of $100$; the order comes in the next step.
2. Join those $\ell$ boxes into one loop: $(\ell - 1)!$ ways. Start from the smallest box in the set. The other $\ell - 1$ boxes can follow it in any order, and each order is a different loop. Once the loop is fixed, so are the slips in these boxes: each box holds the number of the next box.
3. Fill the other $100 - \ell$ boxes with the other $100 - \ell$ slips in any way: $(100 - \ell)!$ ways.

No arrangement is counted twice, because two loops longer than $50$ would need more than $100$ boxes. Multiplying, and using $\ell! = \ell \cdot (\ell - 1)!$:

Dividing by the $100!$ arrangements in total:

Check on a small case: with $4$ boxes and a loop of $3$, the steps give $\binom43 \cdot 2! \cdot 1! = 8$, and $4!/3 = 8$.

Step 4: The probability. At most one loop can be longer than $50$, so these events for different $\ell$ never happen together, and we can add them:

Answer:

just over 31%.

With more prisoners, $2n$ prisoners each opening $n$ boxes, the sum $\frac{1}{n+1} + \dots + \frac{1}{2n}$ approaches $\ln 2$. So the chance of survival only falls to $1 - \ln 2 \approx 0.307$, even with a million prisoners.

Why interviewers like it. Random guessing makes the prisoners succeed or fail independently. Following the loops ties their fates together, so everyone succeeds on the same event: no long loop.