100 prisoners problem

Surprisingly, there is a strategy that provides a survival probability of more than 30%. The key to success is that the prisoners do not have to decide beforehand which drawers to open. Each prisoner can use the information gained from the contents of every drawer he already opened to help decide which one to open next. Another important observation is that this way the success of one prisoner is not independent of the success of the other prisoners, because they all depend on the way the numbers are distributed.[2]

To describe the strategy, not only the prisoners, but also the drawers are numbered from 1 to 100, for example row by row starting with the top left drawer. The strategy is now as follows:[3]

1. Each prisoner first opens the drawer with his own number.
2. If this drawer contains his number he is done 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.

By starting with his own number, the prisoner guarantees he is on a sequence of boxes containing his number. The only question is whether this sequence is longer than 50 boxes.

The reason this is a promising strategy is illustrated with the following example using 8 prisoners and drawers, whereby each prisoner may open 4 drawers. The prison director has distributed the prisoners' numbers into the drawers in the following fashion:

number of drawer	1	2	3	4	5	6	7	8
number of prisoner	7	4	6	8	1	3	5	2

The prisoners now act as follows:

• Prisoner 1 first opens drawer 1 and finds number 7. Then he opens drawer 7 and finds number 5. Then he opens drawer 5, where he finds his own number and is successful.
• Prisoner 2 opens drawers 2, 4, and 8 in this order. In the last drawer he finds his own number 2.
• Prisoner 3 opens drawers 3 and 6, where he finds his own number.
• Prisoner 4 opens drawers 4, 8, and 2, where he finds his own number. Note that this is the same cycle encountered by prisoner 2, but he isn't aware of it.
• Prisoners 5 to 8 will also each find their numbers in a similar fashion.

In this case, all prisoners find their numbers. This is, however, not always the case. For example, the small change to the numbers of swapping drawers 5 and 8 would cause prisoner 1 to fail after opening 1, 7, 5, and 2 (and not finding his own number):

number of drawer	1	2	3	4	5	6	7	8
number of prisoner	7	4	6	8	2	3	5	1

And in the following arrangement, prisoner 1 opens drawers 1, 3, 7, and 4, at which point he has to stop unsuccessfully:

number of drawer	1	2	3	4	5	6	7	8
number of prisoner	3	1	7	5	8	6	4	2

Indeed, all prisoners except 6 (who succeeds directly) fail.

Graph representations of the permutations (1 7 5)(2 4 8)(3 6) and (1 3 7 4 5 8 2)(6)

The prison director's assignment of prisoner numbers to drawers can mathematically be described as a permutation of the numbers 1 to 100. Such a permutation is a one-to-one mapping of the set of natural numbers from 1 to 100 to itself. 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 permutation of the first example above can be written in cycle notation as

${\displaystyle (1~7~5)(2~4~8)(3~6)}$

and thus consists of two cycles of length 3 and one cycle of length 2. The permutation of the third example is accordingly

${\displaystyle (1~3~7~4~5~8~2)(6)}$

and consists of a cycle of length 7 and a cycle of length 1. The cycle notation is not unique since a cycle of length ${\displaystyle l}$ can be written in ${\displaystyle l}$ different ways depending on the starting number of the cycle. During the opening the drawers in the above strategy, each prisoner follows a single cycle which always ends with his own number. In the case of eight prisoners, this cycle-following strategy is successful if and only if the length of the longest cycle of the permutation is at most 4. If a permutation contains a cycle of length 5 or more, all prisoners whose numbers lie in such a cycle do not reach their own number after four steps.

Probability distribution of the length of the longest cycle of a random permutation of the numbers 1 to 100. The green area corresponds to the survival probability of the prisoners

In the initial problem, the 100 prisoners are successful if the longest cycle of the permutation has a length of at most 50. Their survival probability is therefore equal to the probability that a random permutation of the numbers 1 to 100 contains no cycle of length greater than 50. This probability is determined in the following.

A permutation of the numbers 1 to 100 can contain at most one cycle of length ${\displaystyle l>50}$. There are exactly ${\displaystyle {\tbinom {100}{l}}}$ ways to select the numbers of such a cycle (see combination). Within this cycle, these numbers can be arranged in ${\displaystyle (l-1)!}$ ways since there are ${\displaystyle l}$ permutations to represent distinct cycles of length ${\displaystyle l}$ because of cyclic symmetry. The remaining numbers can be arranged in ${\displaystyle (100-l)!}$ ways. Therefore, the number of permutations of the numbers 1 to 100 with a cycle of length ${\displaystyle l>50}$ is equal to

${\displaystyle {\binom {100}{l}}\cdot (l-1)!\cdot (100-l)!={\frac {100!}{l}}.}$

The probability, that a (uniformly distributed) random permutation contains no cycle of length greater than 50 is calculated with the formula for single events and the formula for complementary events thus given by

${\displaystyle 1-{\frac {1}{100!}}\left({\frac {100!}{51}}+\ldots +{\frac {100!}{100}}\right)=1-\left({\frac {1}{51}}+\ldots +{\frac {1}{100}}\right)=1-(H_{100}-H_{50})\approx 0.31183,}$

where ${\displaystyle H_{n}}$ is the ${\displaystyle n}$-th harmonic number. Therefore, using the cycle-following strategy the prisoners survive in a surprising 31% of cases.[3]

The harmonic numbers are approximately given by the area under the hyperbola and can therefore be approximated by a logarithm

If ${\displaystyle 2n}$ instead of 100 prisoners are considered, where ${\displaystyle n}$ an arbitrary natural number, the prisoners' survival probability with the cycle-following strategy is given by

${\displaystyle 1-(H_{2n}-H_{n})=1-(H_{2n}-\ln 2n)+(H_{n}-\ln n)-\ln 2.}$

With the Euler–Mascheroni constant ${\displaystyle \gamma }$, for ${\displaystyle n\to \infty }$

${\displaystyle \lim _{n\to \infty }(H_{n}-\ln n)=\gamma }$

holds, which results in an asymptotic survival probability of

${\displaystyle \lim _{n\to \infty }(1-H_{2n}+H_{n})=1-\gamma +\gamma -\ln 2=1-\ln 2\approx 0.30685.}$

Since the sequence of probabilities is monotonically decreasing, the prisoners survive with the cycle-following strategy in more than 30% of cases independently of the number of prisoners.[3]

In 2006, Eugene Curtin and Max Warshauer gave a proof for the optimality of the cycle-following strategy. The proof is based on an equivalence to a related problem in which all prisoners are allowed to be present in the room and observe the opening of the drawers. Mathematically, this equivalence is based on Foata's transition lemma, a one-to-one correspondence of the (canonical) cycle notation and the one-line notation of permutations. In the second problem, the survival probability is independent of the chosen strategy and equal to the survival probability in the original problem with the cycle-following strategy. Since an arbitrary strategy for the original problem can also be applied to the second problem, but cannot attain a higher survival probability there, the cycle-following strategy has to be optimal.[2]

At first, Gál and Miltersen considered in their paper the case that the number of boxes is twice the number of team members while half of the boxes are empty. This is a more difficult problem since empty boxes lead nowhere and thus the cycle-following strategy cannot be applied. It is an open problem if in this case the winning probability tends to zero with growing number of team members.[4]

In 2005, Navin Goyal and Michael Saks developed a strategy for team B based on the cycle-following strategy for a more general problem in which the fraction of empty boxes as well as the fraction of boxes each team member is allowed to open are variable. The winning probability still tends to zero in this case, but slower than suggested by Gál and Miltersen. If the number of team members and the fraction of boxes which are opened is fixed, the winning probability stays strictly larger than zero when more empty boxes are added.[9]

David Avis and Anne Broadbent considered in 2009 a quantum theoretical variant in which team B wins with certainty.[10]

In case the prison director does not have to distribute the numbers into the drawers randomly, he can foil the prisoners' strategy if he knows the numbering of the drawers. To this end, he just has to ensure that his assignment of prisoners' numbers to drawers constitutes a permutation with a cycle of length larger than 50. The prisoners in turn can counter this by choosing their own numbering of the drawers randomly.[11]

In the case that one prisoner may enter the room first, inspect all boxes, and then switch the contents of two boxes, all prisoners will survive. This is so since any cycle of length larger than 50 can be broken, so that it can be guaranteed that all cycles are of length at most 50.

In 2009, Adam S. Landsberg proposed the following simpler variant of the 100 prisoners problem which is based on the well-known Monty Hall problem:[12]

Behind three closed doors a car, the car keys and a goat are randomly distributed. There are two players: the first player has to find the car, the second player the keys to the car. Only if both players are successful they may drive the car home. The first player enters the room and may consecutively open two of the three doors. If he is successful, the doors are closed again and the second player enters the room. The second player may also open two of the three doors, but he cannot communicate with the first player in any form. What is the winning probability if both players act optimally?

If the players select their doors randomly, the winning probability is only 4/9 (about 44%). The optimal strategy is, however, as follows:

• Player 1 first opens door 1. If the car is behind the door, he is successful. If the keys were behind the door, he next opens door 2; if instead the goat was behind the door, he next opens door 3.
• Player 2 first opens door 2. If the keys are behind the door, he is successful. If the goat was behind the door, he next opens door 3; whereas if the car was behind the door, he next opens door 1.

In the six possible distributions of car, keys and goat behind the three doors, the players open the following doors (in the green cases, the player was successful):

	Car − Keys − Goat	Car − Goat − Keys	Keys − Car − Goat	Keys − Goat − Car	Goat − Car − Keys	Goat − Keys − Car
Player 1	Door 1: Car	Door 1: Car	Door 1: Keys Door 2: Car	Door 1: Keys Door 2: Goat	Door 1: Goat Door 3: Keys	Door 1: Goat Door 3: Car
Player 2	Door 2: Keys	Door 2: Goat Door 3: Keys	Door 2: Car Door 1: Keys	(Door 2: Goat) (Door 3: Car)	(Door 2: Car) (Door 1: Goat)	Door 2: Keys

The success of the strategy is based on building a correlation between the successes and failures of the two players. Here, the winning probability is 2/3, which is optimal since the first player cannot have a higher winning probability than that.[12] In a further variant, three prizes are hidden behind the three doors and three players have to independently find their assigned prizes with two tries. In this case the winning probability is also 2/3 when the optimal strategy is employed.[13]