Peter Winkler of Dartmouth College collects mathematical puzzles. Every once in a while, he encounters a particularly fiendish puzzle that gets him to scratch his head and wonder whether he heard it correctly. Or the puzzle sounds so trivial that he has to ask himself whether he missed something.
The following puzzle, which Winkler describes in the September College Mathematics Journal, belongs in the category: “Wait a minute—I must not have heard that correctly.”
The names of 100 prisoners are placed in 100 wooden boxes, one name to a box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room. They may look into up to 50 of the boxes to try to find their own name, but must leave the room exactly as it was.
The prisoners are permitted no further communication after leaving the room. They do have a chance to plot a strategy in advance. Good thing. Unless they all find their own names, they will all be executed.
If each prisoner examines 50 boxes at random, the probability of the group’s survival is a miniscule 1/2100, or about 0.00000000000000000000000000000008. Even worse, if they all happen to look into the same 50 boxes, their chances drop to zero.
However, there is a strategy that the prisoners can use to increase the probability of success to more than 30 percent. Incredible but true! The trick is to find this strategy.
This puzzle, in a different form, was originally devised by computer scientist Peter Bro Miltersen of the University of Aarhus, Denmark. It appears in a 2003 paper on substring searches presented at a conference on automata, languages, and programming.
Here’s the strategy.
Beforehand, the prisoners randomly assign “ownership” of one box to each prisoner. As a result, each of the 100 boxes now has a “label” on the outside.
Each prisoner goes to the box with his name on it. He finds another prisoner’s name in the box. He then looks into the box labeled with that prisoner’s name. He continues in this fashion until he finds his own name or ends up looking into 50 boxes.
Why does this procedure greatly increase the prisoners’ chances of survival?
The random assignment of a box with a name in it to each prisoner is just a permutation of the 100 names, chosen uniformly at random from the set of all such permutations, Winkler explains.
So, in inspecting boxes, each prisoner follows a cycle of that permutation, beginning with his box. If they don’t exceed the 50-box limit, they succeed in finding their own name. If the particular permutation chosen by the prisoners happens to have no cycle of length greater than 50, the process works, every prisoner finds his name, and no one gets executed.
Indeed, the probability that a random permutation of 2n objects has no cycle of length greater than n is at least 1 minus the natural logarithm of 2.
In this case, the probability of the prisoners surviving is a bit larger than 1 – ln 2. It comes to 31.18 percent.
The strategy works because the prisoners, in effect, impose a structure on their search and take advantage of a basic property of random permutations.
