Lewko's blog

Condemned prisoners and random permutations

Posted in expository, math.CO by Mark Lewko on September 2, 2009

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 {1/2}. Thus the prisoners will escape execution with probability

\displaystyle \left(1/2\right)^{100}\approx 0.7888609052\times 10^{-30}.

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 {1} through {100}. Moreover, they randomly choose a numbering of themselves, again using the numbers {1} through {100}. (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 {x} opens box {x} first. If he finds his name, the process moves onto the next prisoner. If prisoner {x}‘s name is not in box {x} the box must contain the name of some other prisoner, say prisoner {y}. Prisoner {x} now opens box {y}. Again, if prisoner {x} finds his name in box {y}, the process moves onto the next prisoner. If prisoner {x} doesn’t find his name in box {y}, it must contain the name of another prisoner, say prisoner {z}. Prisoner {x} then opens box {z}. This process continues until prisoner {x} has either found his own name, or has exhausted his {50} tries.

Why the strategy works: the analysis

Translating the situation into combinatorial language, the map {\pi:[0,100]\rightarrow[0,100]} that tells us the number of the prisoner whose name is in box {x} is a permutation of the set of integers {[0,100]}. Moreover, since the prisoners chose a random numbering of themselves, we can view {\pi} as a randomly selected permutation of the set {[0,100]}.

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

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

\displaystyle {100\choose n} (100-n)! (n-1)!= \frac{100!(100-n)! (n-1)!}{n!(100-n)!} = \frac{100!}{n}.

Since there are {100!} possible permutations, the probability that a randomly chosen permutation, {\pi}, will have an {n}-cycle is {\frac{1}{n}}. 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 {\pi} has length greater than {50}, is at most

\displaystyle \frac{1}{51}+\frac{1}{52}+\ldots+\frac{1}{100} \approx \ln(100)-\ln(50) = \ln(2) \approx .693

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

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  {1-\ln(2)}. 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).

Advertisements

One Response

Subscribe to comments with RSS.

  1. Michael Lugo said, on March 1, 2010 at 11:28 pm

    Actually, the probability you compute here is exact. You use the union bound, but a permutation of 100 elements can’t have two or more cycles of length greater than 50, so the events you’re using it on are pairwise nonintersecting.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: