100 prisoners, 100 boxes, and a strategy that shouldn't work but does
100 numbered prisoners face 100 boxes, each secretly holding one prisoner's number in random order. Each prisoner may open just 50 boxes before leaving everything exactly as they found it, with no communication once the process starts. If every prisoner finds their own number, all are freed; if even one fails, all remain imprisoned. Is there a strategy that gives them a real chance?
Reveal the answer
Yes — over 30%. Each prisoner opens the box matching their own number first, then follows the number found inside to the next box, chasing a 'cycle' through the boxes. This works because a random shuffle of 100 numbers has roughly a 31% chance that every cycle within it is 50 boxes or shorter. Proposed by Anna Gál and Peter Bro Miltersen in 2003, it's a staple of probability courses for how good the odds turn out to be.
— Anna Gál and Peter Bro Miltersen, The 100 Prisoners Problem — 2003