# Optimal Strategy for the 100 Prisoners Problem Explained

Written on

## Understanding the Optimal Strategy

In a prior discussion, I detailed the most effective approach to tackle the 100 prisoners dilemma. The scenario involves 100 prisoners, numbered from 1 to 100, who have a chance to secure their release. They face 100 closed boxes, each containing a slip of paper with a unique number from 1 to 100. Each prisoner is allowed to open 50 boxes, check the contents, and then close them again. All prisoners must locate their respective numbers to achieve freedom; if even one fails, they all face dire consequences. While they cannot communicate during the search, they can strategize beforehand. What is their optimal plan?

To summarize, the best method involves starting with the box that corresponds to their own prisoner number and then continuing to open boxes based on the numbers found in each opened box.

### Demonstrating Optimality

To establish that this strategy is indeed the best, I will first present a simpler variant of the problem, referred to as the "light" version.

In this version, once a prisoner opens a box, it remains open. If a prisoner discovers their number from a previously opened box, they win automatically. However, if they find their own number, they cannot open any additional boxes.

This "light" variant simplifies matters significantly. Here, later prisoners have a much higher probability of finding their number due to the boxes remaining open. Interestingly, any strategy will yield the same results; the assignment of slips to boxes is random, making the specific strategy irrelevant.

The key difference from the original scenario is the fact that opened boxes stay open. In the traditional version, prisoners close each box after checking it, which could lead to ineffective strategies, such as multiple prisoners opening the same set of boxes. This limitation does not exist in the light version, meaning there are no ineffective strategies here.

Since leaving boxes open cannot be detrimental, a strategy that performs equally in both versions cannot be surpassed by any other strategy.

Let’s designate a strategy that performs equally well in both versions as S1. For any strategy to surpass S1, it must excel in the original game while maintaining the same performance in the light version. However, this is impossible!

To illustrate, let’s call the hypothetical superior strategy S2. By definition, S2 must perform at least as well in the light version as in the original. If S2 does better than S1 in the original version, it must also perform better in the light version, which contradicts our earlier conclusion that all strategies yield the same results there. Hence, S2 cannot exist!

Why is this significant? Because the loop-following strategy described earlier is S1! It performs equally well in both scenarios.

### Exploring the Logic with an Example

Consider Suzy, the n-th prisoner, about to open her allotted number of boxes. There are two scenarios: either a previous prisoner failed their search (resulting in failure for everyone), or every prior prisoner succeeded. We will focus on the latter situation.

Assuming all prisoners use the loop-following strategy, Suzy is effectively playing both versions of the game simultaneously, with the same configuration of numbers in each.

If Suzy is the first prisoner, the loop-following strategy ensures equal chances in both versions. However, if she is not the first, and her box is already open in the light version, it indicates a prior prisoner successfully found her number. While her box remains closed in the original, she will still find her number because it is part of a loop that a previous prisoner followed, which contains at most 50 boxes.

Should Suzy’s box remain closed in the light version, the loop-following strategy leads her to explore the same boxes in both versions. If any box was open, it confirms that a previous prisoner had already accessed her loop.

From this reasoning, it is clear that following the loop strategy offers Suzy identical chances of success in both scenarios. This conclusion holds true regardless of how many prisoners precede her, confirming that the loop-following strategy is optimal. No alternative approach can yield better results.

This explanation draws inspiration from an insightful article on Algorithm Soup, with the original proof documented here.

## Chapter 2: Visualizing the Problem

Explore the intricacies of the 100 prisoners problem through engaging videos that delve deeper into the concepts discussed.

The first video titled "The Riddle That Seems Impossible Even If You Know The Answer" unpacks the complexity of the problem.

The second video titled "Solution to The Impossible Bet | The 100 Prisoners Problem" provides a detailed analysis of the optimal strategy.