ABSTRACT
O ne hundred condemned prisoners are called together by aprison guard, who informs them that they are being trans-ferred. Their new prison has a hard-as-nails reputation, so it is 9
more or less assured that the 100 prisoners will be executed. The soft-hearted warden of their current prison has decided to give the prisoners a chance to be released rather than transferred. Towards this end, he has proposed a game thus. There are 100 closed boxes on a table. Each box contains the name of one prisoner, and each prisoner’s name appears exactly one time, in one box. Each prisoner may open no more than 50 of the boxes, one box at a time, in the hope of finding his name. The prisoners may not confer with one another during game play, may not shift the order of the boxes, and may not extract and exchange any names within the boxes. If all prisoners find their own names, they will all be released. The prisoners are given one half hour to discuss the warden’s proposal, after which they must inform the guard whether or not they intend to play. At first glance, this seems a futile undertaking. If each prisoner randomly inspects 50 boxes, then the chance of a collective release of all prisoners is equal to ( 12 )100 ≈ 7.9 × 10−31, in other words, practically zero. Luckily, one of the prisoners was mathematician-cum-investment banker before embarking on a life of crime and landing in the pokey. Our derailed mathematician explains to the other prisoners that they have about a 30% chance of gaining their freedom. The others can hardly believe it. Nevertheless, it is true. The solution is simple and easy to understand. Each prisoner is assigned one particular box, and no two prisoners are assigned the same box. The prisoners all have phenomenal memories, and each knows not only which box is assigned to him, but also which box is assigned to each of the other prisoners. Each prisoner first opens the box assigned to him. If he encounters his own name, he stops. If he encounters a name other than his own, he opens the box assigned to that prisoner. He continues in this fashion until either finding the box with his own name, or until he has opened 50 boxes. This strategy gives a 31.2% chance of all prisoners finding their names. Yet we see again that math always comes in handy. To understand this surprising result, we need to understand the concept of a cyclic of a permutation of the numbers 1, 2, . . . ,m. A permutation is a rearrangement of the numbers 1 to m in an ordered list. We will elucidate the concept of cycle by using the permutation (7, 3, 8, 6, 1, 4, 5, 2) of the list (1, 2, 3, 4, 5, 6, 7, 8). This permutation is made up of three disjoint cycles
1→ 5→ 7→ 1, 2→ 8→ 3→ 2, and 4→ 6→ 4 with lengths 3, 3 and 2, respectively. The chance of each prisoner
finding his own name is no different from the chance that in a random permutation of the numbers 1, 2, . . . , 100, there will be no cycle with length greater than 50. This is most easily seen by imagining that the box in which the guard has placed the name of the ith prisoner has an invisible label i for all i and imagining that the ith prisoner will be assigned the box located in the ith position of the random order in which the guard has placed the boxes. What is the probability that a randomly generated permutation of the numbers 1, 2, . . . , 100 will include a cycle with length greater than 50? Stated more generally: what is the probability Qn that a random permutation of the numbers 1, 2, . . . , 2n will include a cycle with length greater than n? The answer is
Qn = 1
n+ 1 + 1
n+ 2 + · · ·+ 1
2n.
