The 100 Prisoners Problem
Imagine 100 prisoners, numbered 1 to 100, face an unusual challenge. In a room are 100 boxes, also numbered 1 to 100. Inside each box is a randomly assigned number from 1 to 100 (each number appearing exactly once). The prisoners must find their own number by opening boxes, but here’s the catch: each prisoner can open only 50 boxes.
The prisoners can devise a strategy beforehand, but once the challenge begins, they cannot communicate. If all 100 prisoners find their number, everyone goes free. If even one prisoner fails, all remain imprisoned.
What’s the best strategy? And what are the odds of success?
Try It Yourself!
Before we dive into the mathematics, let’s experience the problem firsthand. Below is a simulator where you can play the game yourself. Choose the number of prisoners (between 5 and 100), and then try to help each prisoner find their number by clicking on boxes.
The Naive Strategy
The most obvious approach is for each prisoner to simply open 50 random boxes. This seems reasonable, but the probability of success is dismal.
For any single prisoner, the probability of finding their number in 50 random boxes out of 100 is exactly 1/2. Since all 100 prisoners must succeed, and their outcomes are independent under random selection, the probability that everyone succeeds is:
$$P(\text{success}) = \left(\frac{1}{2}\right)^{100} \approx 7.9 \times 10^{-31}$$
That’s essentially zero! You’re more likely to win the lottery while being struck by lightning… multiple times.
Naive Strategy: Probability vs Number of Prisoners
Watch how the probability of success plummets as we increase the number of prisoners:
As you can see, even with just 10 prisoners, the probability drops to about 0.1%. With 100 prisoners, it’s practically impossible.
The Clever Strategy: Following the Loops
Here’s where mathematics reveals something beautiful. Instead of opening random boxes, each prisoner should follow a simple rule:
- Start by opening the box with your own number
- Look at the number inside that box
- Open the box with that number next
- Continue following this chain
Why does this work? The key insight involves understanding permutations and cycles.
Understanding Cycles in Permutations
When we randomly assign 100 numbers to 100 boxes, we’re creating a permutation of the numbers 1 through 100. Every permutation can be decomposed into cycles.
For example, if:
- Box 1 contains number 4
- Box 4 contains number 7
- Box 7 contains number 1
Then we have a cycle: 1 -> 4 -> 7 -> 1
Let’s explore this with smaller numbers:
The interactive explorer above lets you:
- Generate all permutations for small values of n (3, 4, or 5)
- See both standard notation and cycle notation
- Filter permutations that have at least one “long cycle” (longer than n/2)
- Understand why long cycles matter
Why This Strategy Works
Here’s the crucial insight: A prisoner succeeds if and only if they are in a cycle of length ≤ 50.
When prisoner k follows the loop strategy:
- They start at box k
- They follow a path through boxes determined by the permutation
- This path forms a cycle that eventually leads back to box k
- If this cycle has length ≤ 50, they’ll find their number within 50 opens
The prisoners all succeed if and only if there is no cycle longer than 50 in the permutation.
Calculating the Probability
The probability that a random permutation of 100 elements has no cycle longer than 50 is:
$$P(\text{success}) = 1 - \sum_{k=51}^{100} \frac{1}{k}$$
Computing this sum:
$$P(\text{success}) = 1 - \left(\frac{1}{51} + \frac{1}{52} + \cdots + \frac{1}{100}\right) \approx 0.3118$$
That’s over 31%! This is astronomically better than the naive strategy’s probability of essentially zero.
Loop Strategy: Probability vs Number of Prisoners
The Mathematics Behind It
Why Does the Cycle Length Matter?
In a permutation of n elements, prisoner i will find their number within k tries using the loop strategy if and only if i belongs to a cycle of length at most k.
For n = 100 and k = 50:
- The probability that a specific prisoner is in a cycle of length > 50 is: Σ(j=51 to 100) of 1/100
- But we care about whether ANY prisoner is in such a cycle
- The probability that NO cycle has length > 50 is: 1 - Σ(j=51 to 100) of 1/j
The Harmonic Series Connection
As n approaches infinity, if each prisoner can open n/2 boxes, the probability of success approaches:
The limit as n approaches infinity is: P_n = 1 - ln(2) ≈ 0.3069
This beautiful result connects combinatorics, probability, and analysis through the harmonic series!
Optimality
Remarkably, this loop-following strategy is optimal. No other strategy can achieve a higher probability of success. The proof involves showing that the problem reduces to avoiding long cycles in a random permutation, and the loop strategy is the unique way to leverage this structure.
Why This Problem is Beautiful
The 100 prisoners problem is beloved by mathematicians because:
-
Counterintuitive Result: The fact that 31% >> 0% is shocking. A seemingly hopeless problem becomes tractable with the right insight.
-
Deep Connection: It connects permutation theory, probability, and the harmonic series in an elegant way.
-
Collaborative Success: Unlike independent trials, the prisoners’ fates are intertwined through the structure of the permutation.
-
Real-World Metaphor: It illustrates how understanding underlying structure (cycles in permutations) can dramatically improve outcomes.
Variants and Extensions
What if prisoners can open k < n/2 boxes?
As k decreases below n/2, the probability drops rapidly. The threshold at n/2 is special—it’s where the strategy becomes remarkably effective.
What about communication?
If prisoners could communicate between trials (but not during), they still can’t improve the strategy. The beauty is that the strategy requires only coordination before any prisoner enters, not during.
The Malicious Director
In an interesting variant, suppose the director can see the prisoners’ strategy and arrange the boxes adversarially (not randomly). Can the director always force them to fail? Yes! The director can always create a single cycle of length n, guaranteeing failure.
Conclusion
The 100 prisoners problem shows us that:
- Mathematical structure can be hidden in apparent randomness
- Clever strategies can overcome seemingly impossible odds
- Group coordination can be more powerful than independent action
- Beautiful mathematics often lies beneath simple-seeming puzzles
The next time you face a problem that seems impossible, remember: there might be a hidden structure waiting to be discovered, turning hopeless odds into reasonable ones.
Further Reading
Subscribe to our newsletter
Stay updated with the latest articles, tutorials, and insights from our team. We'll never spam your inbox.
By subscribing, you agree to our Privacy Policy and consent to receive updates from our company.