The director of a prison offers 100 prisoners on death row, which are numbered from 1 to 100, a last chance. In a room there is a cupboard with 100 drawers. The director puts in each drawer the number of exactly one prisoner in random order and cloese the drawers afterwards. The prisoners enter the room one after another. Each prisoner may open and look into 50 drawers in any order and the drawers are closed again afterwards. In during this search every prisoner finds his number in one of the drawers, all prisoner are pardoned. If just one prisoner does not find his number, all prisoners have to die. Before the first prisoner enters the room, the prisoners may discuss their strategy, afterwards no communication of any means is possible. What is the best strategy for the prisoners?
The key to success is that the prisoners do not have to decide beforehand which drawers they are going to open. Each prisoner can use the information gained from the contents of previously opened drawers to help him decide which drawer to open next. The success of one prisoner is not independent of the success of the other prisoners.
In order to describe the strategy, not only the prisoners, but also the drawers are numbered from 1 to 100. 1. Each prisoner first opens the drawer with his own number. 2. If this drawer contains his number he is finised with his search and was successful. 3. Otherwise, the drawer contains the number of another prisoner and he next opens the drawer with this number. 4. The prisoner repeats steps 2 and 3 until he finds his own number or has opened 50 drawers. This approach ensures that every time a prisoner opens a drawer he either finds his own number or the number of another prisoner he has not encountered so far.
Here is an example using eight prisoners and drawers, whereby each prisoner may open four drawers.
number of drawers | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
number of prisoner | 7 | 4 | 6 | 8 | 1 | 3 | 5 | 2 |
The prisoner now act as follows:
In this case, all prisoners will be successful in finding their numbers.
However, it is not always the case. See the following example.
number of drawers | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
number of prisoner | 3 | 1 | 7 | 5 | 8 | 6 | 4 | 2 |
The prisoner now act as follows:
Unfortunately, all prisoners die.
The prison director’s assignment of prisoner numbers to drawers can mathematically be described as a permutation of the number 1 to 100. A sequence of numbers which after repeated application of the permutation returns to the first number is called a cycle of the permutation. Every permutation can be decomposed into disjoint cycles, that is cycles which have no common elements.
The first example has three cycles: (1, 7, 5), (2, 4, 8), (3, 6). The second example has two cycles: (1, 3, 7, 4, 5, 8, 2), (6).
During the opening the drawers in the above strategy, each prisoner follows a single cycle which always ends with his own number. In order to be successful, the longest cycle of permutation is at most 50 in 100-drawers setting.
The survival probability is calculated as follows:
A permutation of the number 1 to 100 can contain at most one cycle of lenght \(l>50\). There are exactly \({100}\choose{l}\) ways to select the numbers of such a cycle. Within this cycle, the numbers can be arranged in \((l-1)!\) ways since there are \(l\) possibilities to select the starting number of the cycle. The remaining numbers can be arranged in \((100-l)!\) ways. Therefore, the number of permutations of the numbers 1 to 100 with a cycle of length \(l>50\) is equal to \[{100\choose{l}} \times (l-1)! \times (100-l)! = \frac{100!}{l}\]
The probability that a uniformly distributed random permutation contains no cycle of length greater than 50 is \[1-\frac{\sum_{l=51}^{100} \frac{100!}{l}}{100!} = 1 - \left(\frac{1}{51} + \dots + \frac{1}{100} \right) \approx 0.31183\]
Let’s simulate the process of prisoners’ startegy.
round <- 10000
result <- rep(FALSE, round)
for (r in 1:round){
n <- 100
winner <- rep(FALSE, n)
drawer <- sample(1:n, n, replace = FALSE)
for (i in 1:n){
k <- 1 # number of drawers opened for each prisoner
j <- drawer[i] # the drawers should be opened
while (winner[i] == FALSE & k <= n/2){
if (i == j) winner[i] <- TRUE # the prisoner finds his number
else j <- drawer[j] # otherwise find the other drawer to open with the number which is in the previous drawer
k <- k + 1 # number of drawers opened plue one
}
}
if (sum(winner) == n) result[r] <- TRUE # if success, all winners should be TRUE
}
mean(result) # theoretically 0.31183## [1] 0.311