100 prisoners problem

At first glance, the situation appears hopeless, but a clever strategy offers the prisoners a realistic chance of survival.

Anna Gál and Peter Bro Miltersen first proposed the problem in 2003.

The strategy is now as follows:[3] If the prisoner could continue indefinitely this way, they would inevitably loop back to the drawer they started with, forming a permutation cycle (see below).

During the opening of the drawers using the above strategy, each prisoner follows a single cycle which always ends with their 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.

In the initial problem, the 100 prisoners are successful if the longest cycle of the permutation has a length of at most 50.

is equal to 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 where

is an arbitrary natural number, the prisoners' survival probability with the cycle-following strategy is given by With the Euler–Mascheroni constant

holds, which results in an asymptotic survival probability of Since the sequence of probabilities is monotonically decreasing, the prisoners survive with the cycle-following strategy in more than 30% of cases independent 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.

[2] The 100 prisoners problem was first considered in 2003 by Anna Gál and Peter Bro Miltersen in the proceedings of the 30. International Colloquium on Automata, Languages and Programming (ICALP).

[4] In their version, player A (the prison director) randomly colors strips of paper with the names of the players of team B (the prisoners) in red or blue and puts each strip into a different box.

[4] Initially, Gál and Miltersen assumed that the winning probability quickly tends to zero with increasing number of players.

However, Sven Skyum, a colleague at Aarhus University, brought his attention to the cycle-following strategy for the case of this problem where there are no empty boxes.

[2] In spring 2004, the problem appeared in Joe Buhler and Elwyn Berlekamp's puzzle column of the quarterly The Emissary of the Mathematical Sciences Research Institute.

Thereby, the authors replaced boxes by ROMs and colored strips of paper by signed numbers.

The authors noted that the winning probability can be increased also in the case where the team members don't find their own numbers.

[7][8] With slight alterations this form was adopted by Philippe Flajolet, Robert Sedgewick and Richard P. Stanley in their textbooks on combinatorics.

[1][3] The problem, or riddle, along with a detailed explanation of the solution, was featured by the channel Veritasium in a 2023 video on YouTube.

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 whether 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.

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

To this end, they just have to ensure that their 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 agreeing among themselves on a specific random numbering of the drawers, provided that the director does not overhear this and does not bother to respond by replacing numbers in the boxes before the prisoners are let in.

, they can ensure their escape by opening significantly fewer than half of the drawers.

[12] In the variant where any prisoner who finds their number is free, the expected probability of an individual's survival given a random permutation is as follows: Without strategy:

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:[13] If the players select their doors randomly, the winning probability is only ⁠4/9⁠ (about 44%).