Solution
100 Prisoners, 100 Boxes
Show the problem again
The numbers 1–100 are randomly placed into 100 closed boxes, one per box. Each prisoner (numbered 1–100) enters alone and may open at most 50 boxes, seeking their own number, then leaves without communicating. All prisoners succeed or all die. Random guessing gives success probability (1/2)^100, but the optimal strategy (each prisoner opens their own box number, then the box matching the number found inside, following the cycle) does astronomically better. To the nearest whole percent, what success probability does it achieve?
Worked solution
The answer is ≈ 31%, exactly 1 − (1/51 + 1/52 + ... + 1/100) ≈ 1 − ln 2. The box contents define a permutation; prisoner k's chain of openings traces the cycle containing k, which ends at k's number after exactly (cycle length) steps. Everyone succeeds iff the permutation has no cycle longer than 50. The probability a random permutation of 100 has a cycle of length ℓ > 50 is 1/ℓ, so the failure probability is Σ_{ℓ=51}^{100} 1/ℓ ≈ ln 2 ≈ 0.693, giving ≈ 31% success, astronomically better than (1/2)^100 because the strategy correlates everyone's fate.
Source: Strategy first published by Anna Gal and Peter Bro Miltersen, 'The Cell Probe Complexity of Succinct Data Structures' (2003); popularised as a puzzle by Peter Winkler. Statement written for AxiomIQ.