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.