If every prisoner randomly chooses \(50\) drawers and hedges their chances, the probability that a single prisoner finds their number is \(50%\). Since each prisoner chooses these drawers independently, the probability that every prisoner finds their number is \(\frac{1}{2^{100}} = 0.0000000000000000000000000000008124\), which is too small. This begs the question, is it the optimal strategy?

A more optimal strategy is to note that these prisoners can use a deterministic strategy to decide which drawer to open, where prisoner \(N\) opens box \(N\) to reveal a number \(X_N\). They then open box \(X_N\) to reveal a number \(X_{X_N}\). They continue this procedure until they either find their number or exceed 50 tries. This way, the success of each prisoner is no longer independently distributed, since prisoner \(N\) is essentially ensuring that their cycle (which is a unique permutation cycle of notes) is deterministic and contains a box with number \(N\).

Specifically, the permutation of numbers to boxes is a permutation of the numbers from \(1\) to \(100\). The mathematical idea behind this strategy is that every permutation can be decomposed into disjoint cycles (cycles wiwthout any common elements). The prisoners will all be successful if the longest cycle of the permutation has a length atmost \(50\), and their collective probability of survival is equal to the probability that a random permutation of the numbers from \(1\) to \(100\) contains no cycle of length greater than \(50\).

To calculate this probability, note that any permutation of the numbers from \(1\) to \(100\) can contain at most one cycle of length \(\ell\) greater than \(50\), and that there are \({100 \choose \ell}\) ways to select \(\ell\) numbers from the \(100\) possible numbers for the prisoners, where these \(\ell\) numbers form the elements of the permutation cycle. Additionally, these numbers can be arranged in \((\ell-1)!\) ways since there are \(\ell\) permutations to represent different cycles of length \(\ell\), since permutations are invariant under cyclic shifts. The remaining numbers can then be arranged in \((100-\ell)!\) ways. Therefore, the number of permutations of these numbers with a cycle of length \(\ell>50\) is \({\binom {100}{l}} \cdot (l-1)! \cdot (100-l)! = \frac {100!}{l}\).

The probability, that a random permutation does not contain a cycle of length \(\ell\) greater than \(50\) can then be found by first calculating the probability that each permutation does contain a cycle of length \(50\): $$\Pr[\text{survival}] = 1-{\frac {1}{100!}}\left({\frac {100!}{51}}+\ldots +{\frac {100!}{100}}\right)$$ $$=1-\left({\frac {1}{51}}+\ldots +{\frac {1}{100}}\right)$$ $$\approx 0.311827821$$ Therefore, using the cycle-following strategy, the prisoners survive with a probability that is approximately \(\frac{1}{3}\).

Before we define a strategy, we define a methodology to approach this scenario. Let the manner in which Charlie opens 50 boxes be defined by a sequence (inspired from a linked list structure) in which Charlie opens the box numbered \(N\) to find a note numbered \(X_N\). Charlie would then open the box numbered \(X_N\) to find a note number \(X_{X_N}\), and continue this process to \(X_{X_{X_N}}\), and so forth. Therefore, we have defined a method of traversing through the notes and boxes.

The following figure is a diagrammatic representation for the case of 10 boxes. We use a program to randomize the numbers on the notes with unique numbers from 1 to 10.

Then, for any number we start with:
1) If we start with N = 10, then we are done.
2) If we start with any other arbitrary number, there is a longest theoretically possible cycle (of length 9) of boxes that can be traversed. (In this system, of course this theoretical limit is reduced to 4). This cycle can be found by traversing the system using our traversal mechanism to enumerate the cycle that starts with each number:

N = 1: (1 5 3 7)

N = 2: (2 8 4)

N = 3: (3 7 1 5)

N = 4: (4 8 4)

N = 5: (5 7 1)

N = 6: (6 9)

N = 7: (7 1 5 3)

N = 8: (8 4 2)

N = 9: (9 6)

Therefore, we have shown that such a method of traversing through the notes and boxes reveals the existence of cycles. This can be proven by realizing that the only way in which Charlie can land on a box numbered \(N\) is if another box contains a note numbered \(N\). Therefore, the winning strategy would be to reduce the length of such a cycle to \(50\) or less such that the last note Charlie chooses would be \(N\), which guides Charlie back to the box numbered \(N\).

We claim that the strategy for which Bob and Charlie can always win if Bob splits the longest cycle into two smaller cycles (each of which should have a length that is lesser than or equal to \(50\)). We will first describe a procedure to implement this strategy, and then we will prove that this strategy guarantees a win. To define this procedure systematically, let the cycle be denoted by the variable \(V\).

1) When \(|V|<50\), no splitting is required, a win is guaranteed.





2) If \(|V| \geq 50\), we define the following algorithm:






Therefore, when Charlie begins to traverse the notes and boxes in the cycle (which we know that exists), the cycle will have a length that is atmost \(50\), where the last ‘vertex’ of the cycle corresponds to the box with number \(N\) (so that it guides Charlie back to the initial block numbered \(N\)).

Hence, we have proven that this is a winning strategy for Charlie and Alice.