Condemned prisoners and random permutations

In this post I will present one of my favorite logic puzzles. As with many great logic puzzles (see the blue-eyed islanders puzzle, for example), the mathematics is embedded in a gruesome storyline. The puzzle can be stated as follows:

There are 100 prisoners. The warden places 100 wooden boxes in a row in an empty room. He writes the name of each prisoner on 100 separate slips of paper and places one of these slips into each of the 100 boxes, in a manner of his choosing.

Each prisoner is lead into the room, one at a time. The prisoner is allowed to open up to 50 boxes. If the prisoner does not find his own name, all prisoners are executed. If a prisoner finds his own name, the prisoner must reset the boxes exactly as he found them. The process then continues onto the next prisoner. If all 100 prisoners find their own name, all of the prisoners will be released the next morning.

The prisoners are allowed to agree on a strategy before this process starts, however they may not communicate in any way after the process has started. What strategy should the prisoners use to minimize the chance of execution?

Notice that if each of the prisoners open 50 randomly selected boxes, then each prisoner will find his own name with probability . Thus the prisoners will escape execution with probability

This is roughly 1 divided by the number of grams of matter composing the Earth. Below the fold we present a strategy that succeeds with probability about .307 (highlight to see probability).

The strategy

 The prisoners agree on a numbering of the boxes, using the numbers through . Moreover, they randomly choose a numbering of themselves, again using the numbers through . (To be more precise the numbering is chosen uniformly randomly from the space of all possible numberings.) Each prisoner uses the following method for choosing which boxes to open. Prisoner opens box first. If he finds his name, the process moves onto the next prisoner. If prisoner ‘s name is not in box the box must contain the name of some other prisoner, say prisoner . Prisoner now opens box . Again, if prisoner finds his name in box , the process moves onto the next prisoner. If prisoner doesn’t find his name in box , it must contain the name of another prisoner, say prisoner . Prisoner then opens box . This process continues until prisoner has either found his own name, or has exhausted his tries.

Why the strategy works: the analysis

Translating the situation into combinatorial language, the map that tells us the number of the prisoner whose name is in box is a permutation of the set of integers . Moreover, since the prisoners chose a random numbering of themselves, we can view  as a randomly selected permutation of the set .

Recall that a permutation can be decomposed as the disjoint union of cycles. Furthermore, observe that prisoner will find his own name if the cycle of that contains has length less than or equal to . Conversely, if there is some cycle that has length greater than then there will be a prisoner who will not find his name in the first boxes he opens.

We have reduced matters to the following question: what is the probability that a randomly chosen permutation contains no cycles of length or greater? Let’s compute the number of permutations with a cycle of length . First observe that there are possible choices of the elements that will compose a particular -cycle. Furthermore, there are exactly unique cycles with a given choice of elements. Finally there are possible permutations of the remaining elements. Putting this together we have that the number of permutations with a cycle of length is exactly

Since there are possible permutations, the probability that a randomly chosen permutation, , will have an -cycle is . We can conclude from this that the probability that the prisoners fail (and are executed), which is equal to the probability that some cycle in the permutation has length greater than , is at most

by the union bound. Thus the probability that the prisoners succeed with this strategy is greater than about .

Remarks: Notice that as we increase the number of prisoners in the problem, the probability that the above strategy will succeed converges to a quantity larger than  . I am unaware if this is the best known strategy, certainly we haven’t established anything here about its optimality. I am unsure where this problem originated, I learned of it about a year ago in Gier Helleloid‘s course on algebraic combinatorics. Peter Taylor has an exposition of this online here.

Updated 9/04/2009: A few changes the reflect the fact that the probability computed isn’t exact (we apply the union bound at one point).