The 100 Prisoners and 100 Boxes Problem, Solved

The cycle-following strategy solves the 100 prisoners problem with success probability near 31 percent, against effectively zero for random guessing.

The strategy where each prisoner follows the cycle starting at their own number succeeds with probability about 0.3118, versus a probability so close to zero under independent guessing that it would never happen in the observable lifetime of the universe. This is the sharpest illustration in the standard interview canon of how correlating outcomes, rather than treating them as independent, can turn an impossible task into one that succeeds roughly one time in three.

There are 100 prisoners, numbered 1 through 100, and 100 boxes, also numbered 1 through 100, arranged in a room. Before the game starts, the prisoner numbers are placed into the boxes according to a uniformly random permutation, one number per box. Prisoners enter the room one at a time, each may open up to 50 boxes, and each must find the box that contains their own number. Boxes are closed after being examined and the room is reset before the next prisoner enters, so no prisoner can leave information behind except through a strategy agreed in advance.

All 100 prisoners are freed if and only if every single prisoner finds their own number within their 50 allotted openings. If even one prisoner fails, the entire group fails. Prisoners may agree on a strategy beforehand but cannot communicate once the game begins.

The winning strategy has each prisoner start by opening the box matching their own number. If that box contains a different number, the prisoner next opens the box with that number on it, and continues this way, always opening the box labeled with the number just revealed, until either their own number appears or they have opened 50 boxes.

This traces out a cycle of the permutation. Picture the permutation as a function that sends each box label to the number sitting inside it. Starting at box i and repeatedly following that function generates the cycle containing i, and following that exact sequence is precisely what a prisoner does. Prisoner i finds their own number after exactly L openings, where L is the length of the cycle containing i. The prisoner succeeds if and only if L is 50 or smaller.