A neat little puzzle (and its solution) at ScienceNewsOnline.

The scenario is this:

The names of 100 prisoners are placed in 100 wooden boxes, one name per box (assume the are all named differently). The boxes are lined up on a table in a room. Prisoners would be allowed in one by one. Each may look at the contents of 50 of the boxes, but they cannot rearrange the boxes, change the contents, i.e. they have the leave the room the way the found it. The entrance and exit of the room are separated, so prisoners who have looked cannot communicate with prisoners who haven't looked.

The king decrees the following: if all prisoners find the box with their own names, they would be free. Otherwise they'd be executed. They are given a chance to talk this through in advance before the first prisoner is led into the room.

Now, if each of the prisoners look at the boxes randomly, he/she would have a 50% chance of seeing a name. The probability of the group's survival becomes 0.5¹⁰⁰, an impossibly small number.

But, there is one strategy that could lead to a chance of survival greater than 30%. How?

From the article, here's what the prisoners could do. Assign to each prisoner a unique number from 1 to 100. When a prisoner is allowed into the room, he goes first to the box corresponding to his number. He looks at the name inside. He next looks for the box corresponding to the number of the person whose name is inside the box, and so on until he finds his own name or exhausts his 50 boxes.

How does this increase the chance of survival?

Let's look at this diagramatically. Since the names of the prisoners are unique, we can instead imagine that they are called by the number they assigned each other. And thus in each of the 100 boxes is a number. For the sake of illustration, we simplify it down to 10 boxes (and 10 people). We can imagine it looking somewhat like this

 Box num: 1 2 3 4 5 6 7 8 9 10 

 Content: 3 6 8 10 9 7 2 4 5 1 

When it is the turn of the prisoner named "1" to go in, he looks first in box 1, then in box 3, then in box 8, then in box 4, then in box 10, and there he finds his number. Prisoner 2 would look in box 2, box 6, and then box 7. Prisoner 3, however, would look in box 3, box 8, box 4, box 10, and then box 1. Hum, doesn't that sequence sound familiar to you? It is the same sequence prisoner 1 went through but in a slightly different order!

What we have here is what mathematicians call a permutation: an assignment to each member of a set another unique member of the set (the assignment is allowed to associate a member to itself). This is what the prisoners have done! The room with the boxes in it can be thought of as function that maps from the ordered set of boxes to the names contained in the boxes. This is obviously a 1-to-1 function. By assigning one box to each of the prisoners, the prisoners constructed another 1-to-1 function, this time from the set of prisoners to the set of boxes. Composing the two we have a map from the set of prisoners to themselves that is 1-to-1, and hence, a permutation.

A permutation admits a cycle-representation. Take the simplified model we have above. Recall that prisoners 1 and 3 ended up with similar, but offseted sequences of boxes. A cycle in a permutation is a sequence through the set that comes back to itself. To illustrate, for the model we constructed, the cycle representation is:

 ( 1 3 8 4 10 ) ( 2 6 7 ) ( 5 9 ) 

The first name that prisoner 1 finds would be that of prisoner 3, and then 8, and then 4, and so on. The cycle wraps back at the boundary, so the first name prisoner 6 finds would be that of prisoner 7, then prisoner 2.

From the illustration, it is easy to see that the cycles partition the set of prisoners into disjoint parts: prisoners 2, 6, and 7 would only see each other's names (and boxes), which prisoners 1, 3, 8, 4, 10 form their own little clique.

With all these preliminaries, we can now explain how the strategy helps.

We can see that the number of boxes that a prisoner has to open corresponds to the number of people in his cycle. In our model, prisoner 1 is in a cycle of length 5, i.e. that in his group there are 5 people. Prisoner 2 has length 3, and so on.

For the prisoners in the original scenario to survive, they have to choose a permutation such that all the cycles have 50 people or fewer. Since they don't originally know which names is in which boxes, their assignment of numbers is a random choice of permutation among all possible permutations. Their probability of survival, thus, is the same as the percentage of all permutations of 100 names that contains no cycles with more than 50 people.

Some small calculations:

• There are 100! possible permutations.
• Out of them, we subtract all the ones with a cycle longer than 50. (You can't have two cycles with more than 50 people in it, since cycles partition the set, and two cycles with more than 50 people in it would imply the set has more than 100 people to start with.)
• There are 100 c N * (N-1)! * (100-N)! = 100! / N permutations with a cycle that has length N > 50. [To see this, we note that there are 100 c N = 100! / (N! (100-N)!) ways to choose the members of the long cycle. The rest of the members can be permuted anyway they like, hence the (100-N)!. The N members have to be permuted in a way that there's only a single cycle, it is well known that the number of ways to do so is (N-1)!.]
• So: the number of good permutations is 100! - 100! / 51 - 100! / 52 - ... ; in other words, it can be written as 100! * (1 - Σ_{n = 51 .. 100}1/n)

So, in the end, the percentage of good permutations is 1 - Σ_{n= 51 .. 100}1/n, which, a quick punch in the calculator shows to be roughly 31.183%

(Hum, you ask, where does the article pull the phrase "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" from? That can be derived using the above calculations via Stirling's formula.)