100 Prisoners and Box Permutation Loop Strategy

Scenario

100 numbered prisoners ($1$ to $100$) are offered a chance for freedom. In an execution room, there are 100 closed boxes, inside of which the numbers $1$ to $100$ are randomly placed in a uniform random permutation $\pi \in S_{100}$. Each prisoner enters the room alone, inspects up to $50$ boxes, and leaves the room with all boxes closed exactly as found. No communication is permitted after the process begins. All 100 prisoners must find their own number for any prisoner to be freed. If even one prisoner fails, all are executed.

Your Task

1. Compute the probability of team success if each prisoner inspects $50$ boxes independently and uniformly at random.
2. Describe the permutation cycle-following strategy.
3. Prove that the team success probability under this strategy is: $P_{\text{success}} = 1 - \sum_{L=51}^{100} \frac{1}{L} \approx 1 - \ln 2 \approx 31.18\%$
4. Explain why a random permutation cannot contain more than one cycle of length $L > 50$.

Constraints

• At most 50 boxes opened per prisoner.
• Uniform random permutation over $S_{100}$.

Examples Random guessing succeeds with probability $(1/2)^{100} \approx 8 \times 10^{-31}$. The cycle strategy achieves $> 31\%$.