One hundred prisoners are each given a number, and those hundred numbers sit in random order in a hundred boxes. Each prisoner may open 50 boxes, and every prisoner must find their own number for the group to survive. What strategy maximises the survival probability, and what is that probability?

One hundred prisoners are each given a number, and those hundred numbers sit in random order in a hundred boxes. Each prisoner may open 50 boxes, and every prisoner must find their own number for the group to survive. What strategy maximises the survival probability, and what is that probability?

Approach: Have each prisoner follow the cycle of the permutation that begins at the box carrying their own label. The group then fails exactly when the permutation contains one long cycle, so compute the probability of that event.

Follow the cycles, which survives with probability 0.3118. Prisoner i opens box i, then the box labelled with the number found there, and so on. This traces the cycle of the random permutation containing i, so prisoner i succeeds exactly when that cycle has length at most 50, and the whole group succeeds exactly when the cycle structure contains no cycle longer than 50. At most one such long cycle can exist, and a uniform permutation of 100 has a cycle of length k > 50 with probability 1/k, so the failure probability is the harmonic number difference H_100 - H_50, which is 0.688, and survival is 0.312. Independent guessing gives 2^{-100}, so building correlated strategies out of one shared permutation is what carries the result.

Follow-up: What survival probability does the same strategy give if each prisoner may open 60 boxes?

Key concepts: cycle structure, random permutation, correlated strategies, harmonic number.