About 100 Prisoners
A puzzle about a cabinet of drawers. 100 prisoners are numbered 1 to 100. The warden puts slips with the numbers 1 to 100 into 100 numbered drawers, one slip in each, shuffled. One at a time, each prisoner goes into the room alone and may open 50 drawers looking for the slip with their own number, then leaves the room exactly as it was; nobody can pass any message once the night begins. If every one of the 100 finds their own number, they are all set free; if even one doesn't, none of them is. They may agree a plan beforehand.
A prisoner who opens 50 different drawers finds their number with a chance of one half, however they choose which drawers to open. If all of them guess, the chance that all 100 succeed is (1/2)100, about 1 in 1.27 × 1030. Yet there is a plan that wins about 31% of the time.
THE ROOM: play a prisoner. Click or tap drawers to open them (up to 50); each slip names another drawer. The plan: open the drawer with your own number, then the drawer whose number is on the slip you found, and so on. Point the way lights the next drawer on that plan, and the red pencil trail shows where you've been. NEXT PRISONER closes the drawers and sends in the next; WHOLE NIGHT sends in all 100, following the plan, at the speed you pick, and fills in the register (green found it, red ran out of drawers; click or tap a square to see that prisoner's walk, or reach it with Tab, move with the arrow keys and press Enter). NEW NIGHT shuffles the slips again. Keys: N new night, W whole night, P next prisoner, C close the drawers; on MANY NIGHTS, R runs; on the other tabs N is a new night.
MANY NIGHTS: pick how many nights and press RUN. Every night the slips are shuffled afresh; the page counts the nights everyone found their number, following the loops and guessing at random, with the Expected share for each. The lower chart shows how many of the 100 found their number each night.
THE LOOPS: tonight's shuffle drawn as loops. The longest-loop chart gives the chance of each longest loop, with tonight's marked.
THE WARDEN: what if the warden hears of the plan? ONE SWAP: what if one prisoner may look in every drawer and swap two slips first? THE ODDS: any number of prisoners and drawers.
THE STORY
The puzzle comes from computer science. Anna Gál and Peter Bro Miltersen put a version of it, with coloured strips of paper in boxes, in a 2003 paper about how compactly data can be stored, and expected that the team's chance of winning would quickly fall towards zero as the team grew. Their colleague at Aarhus University, Sven Skyum, pointed out the loop plan. In 2006 Peter Winkler posed it with prisoners and drawers in the College Mathematics Journal, and the same year Eugene Curtin and Max Warshauer proved that no plan can do better than following the loops.
The same maths of loops in a shuffle is behind Secret Santa: drawing names from a hat makes loops of givers, and the chance that nobody draws themselves settles at about 37% for any group of seven or more. See Secret Santa on this site.
HOW IT WORKS
Loops. Start at any drawer, read its slip, go to the drawer with that number, and so on: you always come back to where you started, because no two drawers hold the same slip. So the 100 drawers split into loops. Prisoner 17 starts at drawer 17, which is on the loop that holds slip 17: the slip in the drawer just before drawer 17 on that loop. Following the slips, they reach it after going all the way round, so they find their number after exactly as many drawers as their loop is long. Everyone on a loop of 50 or less finds theirs; everyone on a longer loop fails. So the night is won exactly when no loop is longer than 50.
The sum. There can be at most one loop longer than 50, and in a fair shuffle of 100 a loop of exactly L (more than 50) turns up with chance exactly 1/L. (Count them: choose its L drawers, C(100, L) ways; arrange them in a loop, (L − 1)! ways; shuffle the rest, (100 − L)! ways; divide by 100!.) So the chance of losing is 1/51 + 1/52 + … + 1/100 = 0.6882, and of winning 1 − 0.6882 = 0.3118. With n prisoners and n/2 drawers each the same sum tends to ln 2, so even with a million prisoners the plan wins about 30.7% of the time: the limit is 1 − ln 2 = 30.69%.
Why it beats guessing. Each prisoner still has exactly a half chance. What changes is that their successes are tied together: prisoners on the same loop succeed or fail together, and the whole group wins only when no loop is longer than 50. On a lost night, most fail at once (everyone on the long loop, at least 51 of them); on a won night, all 100 succeed. MANY NIGHTS shows this: on average 50 find their number either way, but with loops it's either all 100 or 49 at most.
Any n and k (THE ODDS): the chance a shuffle of n has no loop longer than k comes from following the loop through drawer 1: its length is equally likely to be 1, 2, … n, and what's left is a smaller fair shuffle. So for n ≥ 1, p(n) = (p(n−1) + p(n−2) + … + p(n−min(k, n))) / n, with p(0) = 1. The page adds these up directly, and in logarithms for chances too small for a computer's ordinary numbers. The tests check it against counting every shuffle for up to 8 prisoners and against the published sequences for loops of at most 2 and 3. Guessing at random wins with (k/n)n.
The warden. A warden who knows the plan can put all 100 slips in one loop of 100, and then nobody finds their number. The prisoners' answer: before the night, they shuffle a secret list that gives each number a drawer (number 1 means drawer 64, and so on), and walk by the list instead. Whatever the warden did, the loops they now walk are those of a fair shuffle, so they are back to 31.18%. The page checks this by trying every possible list for a loop of 6.
One swap. If the first prisoner may look in every drawer and swap the slips in two of them, they can save everyone. Only a loop longer than 50 does harm, and there's at most one. Swapping the slips in two drawers on the same loop cuts it in two; cut a loop of L into halves of L/2 (rounded down and up), and both are 50 or less. So the night is always won. For smaller k, one swap saves the night only when exactly one loop is too long and it is no more than twice k.
Simplifications. On MANY NIGHTS the random guessers don't really pick 50 drawers each: each finds their slip with a chance of exactly one half whatever the shuffle, independently of the others, so the page tosses a fair coin for each (the same odds, much faster). Shuffles use a seeded random number generator, so a night number always gives the same shuffle, and a link brings the same night back.
FURTHER WATCHING AND READING