The 100 Prisoners Puzzle: The Strategy That Beats Impossible Odds

A Puzzle That Sounds Completely Hopeless

Imagine 100 prisoners standing outside a room filled with 100 boxes. Inside each box is one slip of paper, and each slip has a different prisoner’s number on it, from 1 to 100. The slips have been placed randomly, one per box.

One by one, each prisoner will enter the room alone. Each prisoner may open up to 50 boxes, looking for the slip with their own number. After leaving the room, the boxes are closed again exactly as they were. The prisoners cannot communicate once the process begins.

Here is the deal: if every single prisoner finds their own number, all 100 prisoners go free. But if even one prisoner fails, everyone loses.

At first, this seems impossible. Each prisoner can only check half the boxes. So each person has a 50% chance of finding their number if they choose randomly. But for all 100 prisoners to succeed by random guessing, the chance is:

[ \left(\frac{1}{2}\right)^{100} ]

That is roughly:

[ 0.0000000000000000000000000000008 ]

In other words, practically zero.

And yet, there is a strategy that gives the prisoners about a 31% chance of success.

Not 3%. Not 0.03%. About 31%.

That is what makes the 100 prisoners puzzle one of the most surprising and beautiful probability puzzles ever invented. It feels like magic, but it is really mathematics hiding in plain sight.

The Rules of the 100 Prisoners Puzzle

Let’s state the puzzle clearly.

There are:

• 100 prisoners, numbered 1 to 100
• 100 boxes, also numbered 1 to 100
• 100 slips of paper, numbered 1 to 100
• Each box contains exactly one slip
• The slips are randomly placed in the boxes
• Each prisoner may open no more than 50 boxes
• Prisoners may agree on a strategy before anyone enters
• Once the process begins, they cannot communicate
• The boxes must be left as they were for the next prisoner
• Everyone wins only if all 100 prisoners find their own number

If the prisoners simply pick 50 boxes at random, each prisoner has a 1 in 2 chance of success. But the group needs all 100 to succeed, so the odds become astronomically bad.

The key question is:

How can the prisoners use a shared strategy to make their successes connected instead of independent?

That is the heart of the puzzle.

The Surprising Strategy

The winning strategy is sometimes called the “loop strategy” or “cycle-following strategy.”

Here is how it works:

1. Prisoner number 1 starts by opening box number 1.
2. If the slip inside says 1, they have found their number and leave successfully.
3. If the slip says, for example, 73, then they next open box 73.
4. If box 73 contains slip 12, they next open box 12.
5. They continue following the numbers from box to box.
6. They stop when they either find their own number or have opened 50 boxes.

Every prisoner does the same thing:

• Prisoner 2 starts at box 2.
• Prisoner 3 starts at box 3.
• Prisoner 47 starts at box 47.
• And so on.

At first, this may sound no better than random guessing. After all, each prisoner is still opening only 50 boxes. But this strategy uses the hidden structure created by the arrangement of slips inside boxes.

Instead of blindly searching, each prisoner follows a trail.

And that trail is not random chaos. It is part of a mathematical object called a permutation.

What Is Really Happening Inside the Boxes?

A permutation is just a rearrangement. In this puzzle, the slips inside the boxes form a rearrangement of the numbers 1 to 100.

For example:

• Box 1 might contain slip 73
• Box 73 might contain slip 12
• Box 12 might contain slip 1

This creates a loop:

[ 1 \rightarrow 73 \rightarrow 12 \rightarrow 1 ]

This loop is called a cycle.

Every box belongs to exactly one cycle. Some cycles may be short. For example:

[ 8 \rightarrow 8 ]

That means box 8 contains slip 8.

Some cycles may be longer:

[ 4 \rightarrow 91 \rightarrow 37 \rightarrow 62 \rightarrow 4 ]

The entire room is made of cycles. The prisoners do not know the cycles in advance, but the cycle-following strategy lets each prisoner travel along the cycle that contains their own number.

Here is the crucial fact:

A prisoner finds their own number within 50 boxes if and only if their cycle has length 50 or less.

So the group succeeds if and only if there is no cycle longer than 50.

That changes the problem completely.

Instead of needing 100 independent lucky guesses, the prisoners only need the random arrangement to avoid having a cycle of length 51 or more.

That happens much more often than you might expect.

Why the Strategy Works So Well

Let’s compare the two approaches.

With random guessing:

• Prisoner 1 has a 50% chance.
• Prisoner 2 has a 50% chance.
• Prisoner 3 has a 50% chance.
• This continues for all 100 prisoners.

The chance that all 100 succeed is:

[ \left(\frac{1}{2}\right)^{100} ]

That is unimaginably tiny.

With the cycle-following strategy, the prisoners’ fates are linked. If the arrangement contains only cycles of length 50 or less, everyone succeeds. If it contains a cycle longer than 50, everyone in that long cycle fails.

This may sound risky, but it is a much better kind of risk.

For 100 prisoners opening 50 boxes each, the probability of success is about:

[ 31.18\% ]

That is astonishing. A situation that appears hopeless suddenly gives the prisoners nearly a one-in-three chance.

The Probability Behind the Magic

So where does the 31% come from?

The prisoners lose if there is a cycle longer than 50. In a permutation of 100 numbers, there can be at most one cycle longer than 50, because two such cycles would require more than 100 numbers.

For any particular length (k), where (k) is greater than 50, the probability that a random permutation contains a cycle of length (k) is:

[ \frac{1}{k} ]

So the probability of losing is:

[ \frac{1}{51} + \frac{1}{52} + \frac{1}{53} + \cdots + \frac{1}{100} ]

This sum is approximately:

[ 0.6882 ]

So the probability of winning is:

[ 1 - 0.6882 = 0.3118 ]

That means the prisoners win about 31.18% of the time.

Another way to think of it is this: the prisoners are betting that the random arrangement of slips does not contain one giant chain that is longer than 50. Random permutations often contain long cycles, but not always. The strategy succeeds exactly when the cycles are all short enough.

A Small Example With 10 Prisoners

The 100-prisoner version is dramatic, but a smaller example can make the idea easier to see.

Suppose there are 10 prisoners and 10 boxes. Each prisoner can open 5 boxes.

Imagine the slips are arranged like this:

| Box | Slip Inside | |---|---| | 1 | 4 | | 2 | 2 | | 3 | 8 | | 4 | 1 | | 5 | 10 | | 6 | 6 | | 7 | 3 | | 8 | 7 | | 9 | 5 | | 10 | 9 |

Now let’s find the cycles.

Box 1 contains 4, so go to box 4. Box 4 contains 1, so we return to 1:

[ 1 \rightarrow 4 \rightarrow 1 ]

That cycle has length 2.

Box 2 contains 2:

[ 2 \rightarrow 2 ]

That cycle has length 1.

Box 3 contains 8, box 8 contains 7, box 7 contains 3:

[ 3 \rightarrow 8 \rightarrow 7 \rightarrow 3 ]

That cycle has length 3.

Box 5 contains 10, box 10 contains 9, box 9 contains 5:

[ 5 \rightarrow 10 \rightarrow 9 \rightarrow 5 ]

That cycle has length 3.

Box 6 contains 6:

[ 6 \rightarrow 6 ]

That cycle has length 1.

All cycles are length 5 or less, so every prisoner succeeds using the cycle-following strategy.

For example, prisoner 5 starts at box 5, sees slip 10, opens box 10, sees slip 9, opens box 9, and finds slip 5. Success in 3 boxes.

This is the core idea in miniature.

Why Random Guessing Feels Tempting but Fails

Random guessing seems natural because each prisoner has half the boxes available. If you only think about one prisoner, random guessing is perfectly reasonable.

But the group goal changes everything.

The prisoners do not need one person to succeed. They need everyone to succeed. Random guessing makes the outcomes mostly independent, and independent risks multiply quickly.

Think of flipping a coin. Getting heads once is easy. Getting heads 100 times in a row is not.

The cycle strategy sacrifices some individual randomness in exchange for group coordination. Each prisoner follows a rule that connects their search to the actual structure of the room.

No one learns anything from previous prisoners. No one changes the boxes. No one sends secret messages. The strategy works because all prisoners use the same mathematical map hidden in the box labels and slip numbers.

That is what makes the puzzle so elegant.

Is This the Best Possible Strategy?

Yes, under the standard rules, the cycle-following strategy is optimal. That means no other strategy can give the prisoners a better chance of success, assuming the slips are randomly placed and the prisoners cannot communicate after the search begins.

This is part of what makes the puzzle famous. The strategy is not just clever; it is as good as possible.

The exact proof of optimality is more advanced, but the main intuition is this: the cycle strategy takes full advantage of the only reliable information available to every prisoner—the numbering system. It turns the room into a set of connected trails, and it ensures that if a prisoner’s number is reachable within 50 steps along their cycle, they will find it.

Other strategies may help some prisoners in some arrangements, but they cannot improve the overall success probability beyond the cycle strategy.

What Makes This Puzzle an Amazing Feat?

The 100 prisoners puzzle is an amazing feat because it transforms our intuition.

At first glance, it looks like a story about bad luck. One hundred people each get only half a chance, and one failure ruins everything. Surely the group is doomed.

But with the right strategy, the problem becomes something different. It becomes a lesson about structure, cooperation, and hidden order.

The prisoners cannot talk during the search, yet they can still coordinate through a shared plan. They cannot control the arrangement of slips, yet they can exploit the cycles inside that arrangement. They cannot make the odds perfect, but they can improve them from almost zero to about 31%.

That is a spectacular leap.

It is also a reminder that probability is not always about raw luck. Sometimes the way you organize your choices matters just as much as the choices themselves.

The Big Lesson

The 100 prisoners puzzle is famous because the answer feels impossible until you see it. Then, once you understand the cycle strategy, it feels almost inevitable.

Each prisoner starts with their own box. Each slip points to the next box. The prisoner follows the trail. If the trail loops back within 50 steps, they succeed. If all trails are short enough, everyone goes free.

The strategy works because it turns 100 separate searches into one shared bet on the cycle structure of a random permutation.

That is the beauty of the puzzle: no tricks, no cheating, no hidden communication—just a brilliant use of mathematics.

And the next time you face a puzzle that seems hopeless, remember the 100 prisoners. Sometimes the impossible odds are only impossible until someone finds the pattern.