The Challenge
The Paradox
The Setup
- 100 prisoners, numbered 1-100
- 100 drawers, each containing a random slip (1-100)
- Each prisoner may open at most 50 drawers
- Must find the slip with their own number
- ALL must succeed for freedom
- Can strategize before, but NO communication during
Random Strategy
Each prisoner randomly opens 50 drawers. Probability of success = 50/100 = 50%
For ALL 100 to succeed: (1/2)^100 ≈ 10^-30
That's a 1 in 1,000,000,000,000,000,000,000,000,000,000 chance!
Cycle Strategy
Each prisoner starts at the drawer matching their number, then follows the chain of slips until they find themselves.
This works because the permutation forms cycles. If all cycles are ≤ 50, everyone succeeds!
Monte Carlo Simulation
Why Cycles Matter
The Key Insight
With random strategy, prisoners fail independently—bad for everyone.
With cycle strategy, they fail together—either the longest cycle is ≤50 (all succeed) or >50 (those in it fail).
Correlated fate is better than independent fate!
Cycle Following Demo
Watch how prisoner 1 follows the chain:
Deep Insights
Correlated vs Independent
The brilliance is converting independent events into correlated ones. With random strategy, each prisoner's success is independent. With cycles, they share fate—and shared fate with some chance beats independent doom.
Cycle Probability
A random permutation has a cycle of length k with probability 1/k. The chance the longest cycle exceeds n/2 is approximately ln(2) ≈ 69%. So 31% have all cycles ≤ 50.
Optimal Strategy
The cycle-following strategy is provably optimal! No other strategy can achieve higher than ~31% success probability. The proof uses information theory.
Real-World Applications
This problem appears in distributed computing, parallel algorithms, and cryptography. The cycle-finding approach is used in Pollard's rho algorithm for integer factorization.
Harmonic Numbers
The exact probability involves harmonic numbers: P = 1 - (H_100 - H_50) where H_n = 1 + 1/2 + 1/3 + ... + 1/n. As n→∞, this approaches 1 - ln(2).
Published 2003
This problem was published by Peter Bro Miltersen and Anna Gál. The elegant solution was found by Sven Skyum. It quickly became a classic in combinatorics and probability.
The Beautiful Truth
Sometimes the best strategy isn't to maximize individual success, but to correlate your fates. When you must ALL succeed, it's better to have a 31% chance of total success than a 50% individual chance that multiplies to nothing.
"In the face of collective doom, unite your fates."