100 Prisoners Problem Explained: A Cycle Strategy That Boosts Collective Win Odds to ~30%

Overview

This video revisits the 100 prisoners problem where 100 participants each look in 50 of 100 boxes in hopes of finding their own dollar bill. If any one person misses their bill, the group loses. The naive approach of choosing boxes at random gives each person a 1/2 chance, making the group odds astronomically small.

Key insights

• A cycle-based strategy dramatically improves the group success rate to about 30 percent.
• The arrange boxes into cycles using the dollars inside as pointers, so following your number leads you to your bill within 50 steps whenever all cycles are 50 or shorter.
• When the permutation of boxes has no chain longer than 50, everyone wins by following the same strategy, tying fates together.

Introduction

The video analyzes a puzzle in which 100 people must each locate their own dollar bill hidden in one of 100 boxes. Each person is allowed to inspect exactly 50 boxes. The group only wins if every person finds their own bill. If each person picks 50 boxes at random, the probability that a single person finds their bill is 1/2, making the joint probability that all 100 players succeed equal to (1/2) raised to the 100th power, an unimaginably small number. The natural question is whether there exists a strategy that improves the chances for the entire group, and if so, how it works and why it matters.

The Naive vs The Coordinated Approach

Initially, the presenter notes that random box selection for each person yields vanishingly small odds for everyone to succeed. While correlating choices between a few players can offer tiny improvements, as the number of participants grows the benefits drop rapidly. The surprising twist is that a particular coordinated strategy can push the collective win rate to around 30 percent, which is notably higher than the probability of any two people succeeding at random.

The Core Idea: Boxes Form Hidden Chains

The central idea is to view the dollar bills inside the boxes as chain pointers that link boxes together. Because the room arrangement is fixed each time, the first box in any sequence points to another box, which points to another, creating chains that eventually cycle back on themselves. Each arrangement of the dollars partitions the 100 boxes into disjoint cycles. Importantly, the longest possible cycle length cannot exceed 100 and, in general, there will be a mix of short and long cycles. The crux is that a player will find their own bill within 50 steps if and only if the cycle containing their own box has length at most 50.

The Strategy: Start at Your Own Box and Follow the Chain

Under this strategy, each player starts with the box that matches their own number and then uses the dollar inside to determine which box to open next. Repeating this process traces along the cycle containing their starting point. If this cycle length is 50 or fewer, the player will reach their own dollar within the allowed 50 steps. If any cycle exceeds 50, at least one player will fail to find their bill within 50 steps, and the whole group loses.

Why This Works For The Group

The elegance of the method is not that it increases a single player’s odds but that all players’ outcomes are linked by the same underlying structure. The random rearrangement of boxes creates a fixed set of cycles, and the event that no cycle exceeds 50 boxes occurs with probability about 30 percent. When that happens, everyone who follows the cycle strategy succeeds, and the entire group wins. Conversely, if any cycle is longer than 50, the strategy guarantees collective loss. The fates of all players are bound together by the boxes themselves.

Implications and takeaways

The result is a striking example of how information embedded in a system can be exploited to coordinate actions across a large group. The strategy does not boost the odds for a single participant, but it creates a correlated outcome across the entire group that, in a nontrivial fraction of random box arrangements, leads to collective success. This demonstrates a powerful idea in probability and combinatorics: the structure of a permutation and its cycle decomposition can drastically alter group-wide outcomes when a shared rule is applied. The video invites viewers to think about how similar linked conditions might apply in other problems where many agents must act in concert to succeed.

Conclusion

In short, by treating the random box arrangement as a collection of cycles and by following your own number's chain, the group can achieve a surprisingly high probability of success, around 30 percent, a dramatic improvement over the naive independent random approach. The strategy is a vivid illustration of how global structure and coordinated behavior can transform collective outcomes in probabilistic systems.