100 Prisoners and Drawers

Probability · Hard · Free problem

There are 100 prisoners, numbered 1 through 100, and a room with 100 drawers. Each drawer contains a slip with a unique prisoner number, arranged as a uniformly random permutation of $\{1, 2, \dots, 100\}$.

The process works like this: each prisoner enters the room one at a time and may open up to 50 drawers. After each prisoner's turn, all drawers are closed again. The prisoners cannot communicate once the process begins, but they can agree on a strategy beforehand.

The group wins if and only if every single prisoner finds the drawer containing their own number.

If each prisoner opens 50 drawers uniformly at random, what is the probability the group succeeds?

Describe a deterministic strategy that achieves a success probability strictly greater than 1%.

Compute (or tightly bound) the success probability of your strategy. Express the answer in terms of the cycle structure of the underlying permutation.

Hints

Think about the structure a random permutation gives you. What mathematical object connects drawer contents to prisoner numbers?
If prisoner $i$ starts at drawer $i$ and follows the chain $i \to \sigma(i) \to \sigma^2(i) \to \cdots$, how many steps until they return to their own number? What property of the permutation determines this?
The strategy fails if and only if there exists a cycle of length

Loading problems...

Worked Solution

How to Think About It: At first glance, this seems hopeless. If each prisoner opens 50 random drawers, they find their number with probability

/2$, and since the searches are independent, the group succeeds with probability $(1/2)^{100} \approx 10^{-31}$. That is essentially zero. The breakthrough is realizing that the drawers define a permutation, and a permutation has structure -- specifically, cycle structure. If the prisoners can exploit that structure, their outcomes become correlated, which is exactly what you need.

Quick Estimate: The cycle-following strategy fails only when the permutation has a cycle of length

Loading problems...

gt; 50$. A random permutation of 100 elements has at most one such cycle. The probability of having a cycle of length $k$ for $k > 50$ is

/k$ (a classical result). So the failure probability is $\sum_{k=51}^{100} 1/k \approx \ln(100) - \ln(50) = \ln 2 \approx 0.693$. That gives a success probability of roughly

- 0.693 \approx 0.307$, or about 31%. Remarkably, over 30% -- vastly better than the

0^{-31}$ from random guessing.

Approach: We describe the cycle-following strategy, prove it succeeds if and only if the longest cycle has length $\leq 50$, then compute the probability of that event exactly.

The Strategy (Cycle-Following):

Prisoner $i$ first opens drawer $i$.
If drawer $i$ contains number $j$, prisoner $i$ next opens drawer $j$.
Continue following the chain: each drawer tells you which drawer to open next.
Stop when you find your own number or have opened 50 drawers.

Why It Works: The permutation $\sigma$ on $\{1, \dots, 100\}$ decomposes into disjoint cycles. Prisoner $i$ belongs to exactly one cycle: $i \to \sigma(i) \to \sigma^2(i) \to \cdots \to i$. By following the chain starting at drawer $i$, prisoner $i$ traverses exactly their own cycle. They find their number after $L$ steps, where $L$ is the length of their cycle. So prisoner $i$ succeeds if and only if their cycle has length $\leq 50$.

Since every prisoner in the same cycle has the same cycle length, and every prisoner is in some cycle, the group succeeds if and only if every cycle has length $\leq 50$ -- i.e., the longest cycle in $\sigma$ has length at most 50.

Computing the Success Probability:

Let $A_k$ be the event that the permutation has a cycle of length $k$, for $k > 50$. Since a permutation of 100 elements can have at most one cycle of length

Loading problems...

gt; 50$, the events $A_{51}, A_{52}, \dots, A_{100}$ are mutually exclusive.

The number of permutations of $\{1, \dots, 100\}$ containing a specific cycle of length $k$ is:

$\binom{100}{k} \cdot (k-1)! \cdot (100-k)! = \frac{100!}{k}$

So:

$P(A_k) = \frac{100! / k}{100!} = \frac{1}{k}$

The failure probability is:

$P(\text{fail}) = \sum_{k=51}^{100} \frac{1}{k} = H_{100} - H_{50}$

where $H_n = \sum_{j=1}^{n} 1/j$ is the $n$-th harmonic number.

Therefore the success probability is:

$P(\text{success}) = 1 - \sum_{k=51}^{100} \frac{1}{k} = 1 - H_{100} + H_{50}$

Numerically, $H_{100} \approx 5.18738$ and $H_{50} \approx 4.49921$, giving:

$P(\text{success}) = 1 - (5.18738 - 4.49921) = 1 - 0.68817 \approx 0.31183$

More precisely, $P(\text{success}) \approx 31.18\%$.

Asymptotic Note: For

n$ prisoners each opening $n$ drawers, the success probability tends to

- \ln 2 \approx 0.3069$ as $n \to \infty$. The $n = 50$ case is already very close to this limit.

Answer: The cycle-following strategy succeeds with probability

- \sum_{k=51}^{100} \frac{1}{k} = 1 - H_{100} + H_{50} \approx 31.18\%$. Each prisoner starts at their own drawer and follows the permutation chain. The group wins if and only if the permutation has no cycle of length greater than 50.

Intuition

The key insight is that random guessing makes the prisoners' outcomes independent, which is devastating when you need all 100 to succeed simultaneously. The cycle-following strategy does the opposite: it perfectly correlates their fates. Every prisoner in the same cycle either succeeds or fails together, so the only thing that matters is the length of the longest cycle. You have converted a problem about 100 independent coin flips into a single question about permutation statistics.

This is a beautiful example of a broader principle in combinatorics and probability: structured strategies that exploit correlations can massively outperform independent random attempts. In quant work, the same idea appears everywhere -- from reducing variance through correlated hedging to designing coordinated trading strategies. Whenever you see a problem where independent success probabilities multiply to something tiny, ask whether there is hidden structure that lets you correlate the outcomes. The permutation cycle structure here is the hidden gift.