The Hundred Prisoners and the Boxes

This is one of the most famous puzzles in quant interviewing, precisely because the naive probability is so bad and the actual answer is so good that most candidates assume they've made an arithmetic error.

The puzzle

100 prisoners, numbered 1 to 100. A room contains 100 boxes, also numbered 1 to 100, each containing one prisoner's number, placed by a random permutation unknown to the prisoners. Each prisoner, one at a time, may open up to 50 boxes, looking for their own number, then the room is reset exactly as they found it before the next prisoner enters. No communication after the process starts. All 100 prisoners must find their own number for everyone to survive. Is there a strategy giving a decent chance of success, and if so, how good?

The naive approach fails badly. If each prisoner opens 50 boxes at random, each one succeeds with probability $50/100 = 1/2$. But the prisoners need all 100 to succeed, and independent 50% chances multiply: $(1/2)^{100}$, a number smaller than one in a trillion trillion. This looks hopeless.

The strategy: follow the cycle. Each prisoner starts by opening the box matching their own number. Whatever number they find inside, they open that numbered box next, and repeat, always opening the box named by the number they just found, up to 50 boxes. This isn't random — it's following the permutation's own structure.

Why it works. Any permutation of 100 items decomposes into disjoint cycles. If prisoner $k$ is in a cycle of length $L$, starting at box $k$ and following the chain always returns to box $k$ after exactly $L$ steps — and crucially, that chain passes through every box in $k$'s own cycle before repeating. So prisoner $k$ finds their number within 50 boxes if and only if the cycle containing $k$ has length at most 50. All 100 prisoners succeed exactly when no cycle in the permutation is longer than 50 — and since a 100-element permutation can have at most one cycle longer than 50 (two such cycles wouldn't fit), this reduces to one clean question about one number.

The number. The probability a random permutation of 100 elements has no cycle longer than 50 works out to roughly $1 - \ln 2 \approx 0.31$ — about 31%. That's a wildly different outcome from one-in-a-trillion-trillion, achieved purely by coordinating on structure instead of searching independently.