100 prisoners and 100 boxes

Question

There are 100 prisoners, numbered 1 to 100. In a room are 100 boxes, each containing a slip with a distinct prisoner's number (a random permutation). One at a time, each prisoner enters the room and may open 50 boxes, looking for their own number. Then they leave, restoring the boxes exactly, and cannot communicate with those who follow. If every prisoner finds their own number, all go free. If even one fails, all are executed. The prisoners may agree on a strategy beforehand. Find a strategy that succeeds with probability greater than 30%. (Random guessing gives 2^{-100}, essentially zero.)

Accepted Answer

The strategy (cycle-following). Prisoner k opens the box labeled k first. Whatever number n is inside, they next open box n, then the box labeled with the number found there, and so on, following the "pointer chain", for up to 50 boxes. Why it works. The boxes define a permutation: box 	o number inside. Following the chain from box k traces the cycle of that permutation containing k. Prisoner k's own number sits in the box that points to box k, that is, the number k is the "closing link" of k's cycle. So prisoner k finds their number within 50 openings if and only if the cycle containing k h…

100 prisoners and 100 boxes

Your answer

More Brainteasers questions