A hundred prisoners are numbered 1 to 100. In a sealed room stand a hundred boxes, and inside each box, in random order, sits one prisoner’s number. One by one, each prisoner enters the room alone and may open 50 of the boxes, hunting for their own number. If every single prisoner finds their number, all go free. If even one fails, all are executed. They may plan a strategy beforehand, but once the first prisoner walks in there is no more communication, and the boxes are never rearranged.
Now the grim arithmetic. If each prisoner just opens 50 boxes at random, that prisoner has a one-in-two chance. For all hundred to succeed by luck, you multiply one half by itself a hundred times, and the result is one in more than a million trillion trillion. That is not a hard problem. That is a certain death sentence.
And yet there is a strategy that lifts the whole group’s chance of survival to about 31 per cent. Almost one in three. It was proved to work by the computer scientists Anna Gal and Peter Bro Miltersen in 2003, and the first time you hear it, it feels like a cheat.
The rule is this. Each prisoner opens the box with their own number on it first. Inside is some number, so they go to the box carrying that number next, and then the number inside that one, and so on, following the chain. Every prisoner walks their own trail through the boxes.
Because each box holds exactly one number and each number sits in exactly one box, these trails form closed loops. A prisoner following their loop is guaranteed to reach their own number, as long as the loop is 50 boxes or shorter. So the whole hundred survive or die on a single question: does the arrangement contain any loop longer than 50? The strategy does not make each prisoner more likely to win on their own. It ties all their fates together, so they tend to win as a group or lose as a group, and the odds of a monstrously long loop turn out to be a bit under 70 per cent. Flip that around, and the prisoners walk free about 31 times in 100.
