View source for 100 prisoners problem

{{short description|Mathematics problem}}
[[File:100 prisoners problem qtl1.svg|thumb|upright=1.4|Each prisoner has to find their own number in one of 100 drawers, but may open only 50 of the drawers.]]
The '''100 prisoners problem''' is a [[Mathematics|mathematical]] [[Mathematical problem|problem]] in [[Probability theory|probability theory]] and [[Combinatorics|combinatorics]]. In this problem, 100 numbered prisoners must find their own numbers in one of 100 drawers in order to survive. The rules state that each prisoner may open only 50 drawers and cannot communicate with other prisoners. At first glance, the situation appears hopeless, but a clever strategy offers the prisoners a realistic chance of survival.

Danish computer scientist Peter Bro Miltersen first proposed the problem in 2003.

== Problem ==

The 100 prisoners problem has different renditions in the literature. The following version is by [[Biography:Philippe Flajolet|Philippe Flajolet]] and [[Biography:Robert Sedgewick (computer scientist)|Robert Sedgewick]]:<ref name="flajolet">{{citation|author=Philippe Flajolet, Robert Sedgewick|title=Analytic Combinatorics|publisher=Cambridge University Press|year=2009|pages=124|title-link= Analytic Combinatorics}}</ref>

:''The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a last chance. A room contains a cupboard with 100 drawers. The director randomly puts one prisoner's number in each closed drawer. The prisoners enter the room, one after another. Each prisoner may open and look into 50 drawers in any order. The drawers are closed again afterwards. If, during this search, every prisoner finds their number in one of the drawers, all prisoners are pardoned. If even one prisoner does not find their number, all prisoners die. Before the first prisoner enters the room, the prisoners may discuss strategy — but may not communicate once the first prisoner enters to look in the drawers. What is the prisoners' best strategy?''

If every prisoner selects 50 drawers at [[Randomness|random]], the [[Probability|probability]] that a single prisoner finds their number is 50%. Therefore, the probability that all prisoners find their numbers is the [[Product (mathematics)|product]] of the single probabilities, which is <big>(</big>{{sfrac|1|2}}<big>)</big><sup>100</sup> ≈ {{val|0.0000000000000000000000000000008}}, a vanishingly small number. The situation appears hopeless.

== Solution ==

=== Strategy ===

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|information]] gained from the contents of every drawer they already opened to decide which one to open next. Another important observation is that this way the success of one prisoner is not [[Independence (probability theory)|independent]] of the success of the other prisoners, because they all depend on the way the numbers are distributed.<ref name="curtin" />

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:<ref name="stanley">{{citation|author=Richard P. Stanley|title=Algebraic Combinatorics: Walks, Trees, Tableaux, and More|publisher=Springer|year=2013|pages=187–189}}</ref>

# Each prisoner first opens the drawer labeled with their own number.
# If this drawer contains their number, they are done and were successful.
# Otherwise, the drawer contains the number of another prisoner, and they next open the drawer labeled with this number.
# The prisoner repeats steps 2 and 3 until they find their own number, or fail because the number is not found in the first fifty opened drawers.

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). By starting with their own number, the prisoner guarantees they are on the specific cycle of drawers containing their number. The only question is whether any cycle is longer than fifty drawers - and only one cycle can possibly be too long, since at most one can comprise more than half of the total drawers.

=== Examples ===

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:
:{| class="wikitable" style="text-align:center"
|-
! number of drawer
| &nbsp;1 &nbsp; || &nbsp; 2 &nbsp; || &nbsp; 3 &nbsp; || &nbsp; 4 &nbsp; || &nbsp; 5 &nbsp; || &nbsp; 6 &nbsp; || &nbsp; 7 &nbsp; || &nbsp; 8 &nbsp;
|-
! 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 they open drawer 7 and find number 5. Then they open drawer 5, where they find their own number and are successful.
* Prisoner 2 opens drawers 2, 4, and 8 in this order. In the last drawer they find their own number, 2.
* Prisoner 3 opens drawers 3 and 6, where they find their own number.
* Prisoner 4 opens drawers 4, 8, and 2, where they find their own number. This is the same cycle that was encountered by prisoner 2 and will be encountered by prisoner 8.  Each of these prisoners will find their own number in the third opened drawer.
* Prisoners 5 to 7 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 their own number):
:{| class="wikitable" style="text-align:center"
|-
! number of drawer
| &nbsp; 1 &nbsp; || &nbsp; 2 &nbsp; || &nbsp; 3 &nbsp; || &nbsp; 4 &nbsp; || &nbsp; 5 &nbsp; || &nbsp; 6 &nbsp; || &nbsp; 7 &nbsp; || &nbsp; 8 &nbsp;
|-
! 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 they have to stop unsuccessfully:
:{| class="wikitable" style="text-align:center"
|-
! number of drawer
| &nbsp; 1 &nbsp; || &nbsp; 2 &nbsp; || &nbsp; 3 &nbsp; || &nbsp; 4 &nbsp; || &nbsp; 5 &nbsp; || &nbsp; 6 &nbsp; || &nbsp; 7 &nbsp; || &nbsp; 8 &nbsp;
|-
! number of prisoner
| 3 || 1 || 7 || 5 || 8 || 6 || 4 || 2
|}

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

=== Permutation representation ===
{{multiple image|direction=horizontal|image1=Permutation cycles qtl1.svg|image2=Permutation cycles qtl2.svg|width=110|footer=Graph representations of the permutations (1&nbsp;7&nbsp;5)(2&nbsp;4&nbsp;8)(3&nbsp;6) and (1&nbsp;3&nbsp;7&nbsp;4&nbsp;5&nbsp;8&nbsp;2)(6)}}

The prison director's assignment of prisoner numbers to drawers can mathematically be described as a [[Permutation|permutation]] of the numbers 1 to 100. Such a permutation is a [[Bijection|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 [[Cyclic permutation|cycle]] of the permutation. Every permutation can be decomposed into [[Disjoint sets|disjoint]] cycles, that is, cycles which have no common elements. The permutation of the first example above can be written in [[Cycle notation|cycle notation]] as

:<math>(1 ~ 7 ~ 5 )( 2 ~ 4 ~ 8) (3 ~ 6)</math>

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

:<math>(1 ~ 3 ~ 7 ~ 4 ~ 5 ~ 8 ~ 2) (6)</math>

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 <math>l</math> can be written in <math>l</math> 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 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. 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 of success ===
[[File:Permutation longest cycle length pmf qtl2.svg|thumb|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|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 <math>l > 50</math>. There are exactly <math>\tbinom{100}{l}</math> ways to select the numbers of such a cycle (see [[Combination|combination]]). Within this cycle, these numbers can be arranged in <math>(l-1)!</math> ways since there are <math>l</math> permutations to represent distinct cycles of length <math>l</math> because of cyclic symmetry. The remaining numbers can be arranged in <math>(100-l)!</math> ways. Therefore, the number of permutations of the numbers 1 to 100 with a cycle of length <math>l > 50</math> is equal to

:<math>\binom{100}{l} \cdot (l-1)! \cdot (100-l)! = \frac{100!}{l}.</math>

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

:<math>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,</math>

where <math>H_n</math> is the <math>n</math>-th [[Harmonic number|harmonic number]]. Therefore, using the cycle-following strategy the prisoners survive in a surprising 31% of cases.<ref name="stanley" />

=== Asymptotics ===
[[File:Integral Test.svg|thumb|The harmonic numbers are approximately given by the area under the hyperbola and can therefore be approximated by a logarithm]]

If <math>2n</math> instead of 100 prisoners are considered, where <math>n</math> an arbitrary natural number, the prisoners' survival probability with the cycle-following strategy is given by

:<math>1 - ( H_{2n} - H_n ) = 1 - (H_{2n} - \ln 2n) + (H_n - \ln n) - \ln 2.</math>

With the [[Euler–Mascheroni constant]] <math>\gamma</math>, for <math>n \to \infty</math>

:<math>\lim_{n \to \infty} (H_n - \ln n) = \gamma</math>

holds, which results in an asymptotic survival probability of

:<math>\lim_{n \to \infty} ( 1 - H_{2n} + H_n ) = 1 - \gamma + \gamma - \ln 2 = 1 - \ln 2 \approx 0.30685.</math>

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.<ref name="stanley" />

=== Optimality ===

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 [[Permutation#Foata's transition lemma|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.<ref name="curtin">{{citation|author=Eugene Curtin, Max Warshauer|title=The locker puzzle|journal=Mathematical Intelligencer|volume=28|year=2006|pages=28–31|doi=10.1007/BF02986999|s2cid=123089718 }}</ref>

== History ==

The 100 prisoners problem was first considered in 2003 by Danish computer scientist Peter Bro Miltersen who published it with Anna Gál in the [[Conference proceedings|proceedings]] of the ''30. International Colloquium on Automata, Languages and Programming'' (ICALP).<ref name="miltersen">{{citation|author=Anna Gál, Peter Bro Miltersen|contribution=The cell probe complexity of succinct data structures|title=Proceedings 30th International Colloquium on Automata, Languages and Programming (ICALP)|year=2003|pages=332–344}}</ref> 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. Some of the boxes may be empty (see below). Every player of team B must guess their color correctly after opening half of the boxes for their team to win.<ref name="miltersen"/> Initially, Miltersen assumed that the winning probability quickly tends to zero with increasing number of players. However, Sven Skyum, a colleague of Miltersen at [[Organization:Aarhus University|Aarhus University]], brought his attention to the cycle-following strategy for the case of this problem where there are no empty boxes. To find this strategy was left open as an exercise in the publication. The paper was honored with the best paper award.<ref name="curtin" />

In spring 2004, the problem appeared in Joe Buhler and [[Biography:Elwyn Berlekamp|Elwyn Berlekamp]]'s puzzle column of the quarterly ''The Emissary'' of the [[Organization:Mathematical Sciences Research Institute|Mathematical Sciences Research Institute]]. Thereby, the authors replaced boxes by [[Read-only memory|ROM]]s and colored strips of paper by [[Sign (mathematics)|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. If the given answer is the product of all the signs found and if the length of the longest cycle is half the (even) number of players plus one, then the team members in this cycle either all guess wrong or all guess right. Even if this extension of the strategy offers a visible improvement for a small number of players, it becomes negligible when the number of players becomes large.<ref name="buhler">{{citation|author=Joe Buhler, Elwyn Berlekamp|title=Puzzles Column|journal=The Emissary|url=http://www.msri.org/web/msri/about-msri/news/emissary-newsletter|volume=Spring 2004|year=2004|pages=3}}</ref>

In the following years, the problem entered the mathematical literature, where it was shaped in further different ways, for example with cards on a table<ref>{{citation|author=Richard E. Blahut|title=Cryptography and Secure Communication|publisher=Cambridge University Press|year=2014|pages=29–30}}</ref> or wallets in lockers (''locker puzzle'').<ref name="curtin" /> In the form of a prisoner problem it was posed in 2006 by Christoph Pöppe in the journal ''Spektrum der Wissenschaft'' and by [[Biography:Peter Winkler|Peter Winkler]] in the ''College Mathematics Journal''.<ref name="pöppe">{{citation|author=Christoph Pöppe|title=Mathematische Unterhaltungen: Freiheit für die Kombinatoriker|journal=Spektrum der Wissenschaft|volume=6/2006|year=2006|pages=106–108|language=german|url=http://www.spektrum.de/alias/mathematische-unterhaltungen/freiheit-fuer-die-kombinatoriker/848868}}</ref><ref name="winkler">{{citation|author=Peter Winkler|title=Names in Boxes Puzzle|journal=College Mathematics Journal|volume=37|number=4|year=2006|pages=260, 285, 289}}</ref> With slight alterations this form was adopted by Philippe Flajolet, Robert Sedgewick and [[Biography:Richard P. Stanley|Richard P. Stanley]] in their textbooks on combinatorics.<ref name="flajolet" /><ref name="stanley" />

== Variants ==

=== Empty boxes ===

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 whether in this case the winning probability tends to zero with growing number of team members.<ref name="miltersen" />

In 2005, Navin Goyal and [[Biography:Michael Saks (mathematician)|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.<ref>{{citation|author=Navin Goyal, Michael Saks|title=A parallel search game|journal=Random Structures & Algorithms|volume=27|number=2|pages=227–234|year=2005|doi=10.1002/rsa.20068 |s2cid=90893 }}</ref>

[[Biography:David Avis|David Avis]] and [[Biography:Anne Broadbent|Anne Broadbent]] considered in 2009 a [[Quantum complexity theory|quantum theoretical]] variant in which team B wins with certainty.<ref>{{citation|author=[[Biography:David Avis|David Avis]], [[Biography:Anne Broadbent|Anne Broadbent]]|contribution=The quantum locker puzzle|title=Third International Conference on Quantum, Nano and Micro Technologies ICQNM '09|pages=63–66|year=2009}}</ref>

=== The malicious director ===
In case the prison director does not have to distribute the numbers into the drawers randomly, and realizes that the prisoners may apply the above-mentioned strategy and guesses the box numbering the prisoners will apply (such as numbers indicated on the boxes), they can foil the strategy. 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 or does not bother to respond by replacing numbers in the boxes before the prisoners are let in.<ref>{{citation|author=Philippe Flajolet, Robert Sedgewick|title=Analytic Combinatorics|publisher=Cambridge University Press|year=2009|pages=177}}</ref>

=== One prisoner may make one change ===
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.

=== Any prisoner who finds their number is free ===
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: <math>\frac{1}{2}</math>

With the strategy for the original problem: <math>(1 - \ln(2)) \cdot 1 + \sum_{k = \lfloor n/2 \rfloor + 1}^N  \frac{1}{k} \left(1-\frac{k}{n}\right) = 1 - \ln(2) + \sum_{\lfloor n/2 \rfloor + 1}^N \frac{1}{k} - \sum_{k = \lfloor n/2 \rfloor + 1}^N \frac{1}{n} = 1 - \ln(2) + \ln(2) - \frac{1}{2} = \frac{1}{2}</math>

It is noteworthy that although we receive the same expected values, they are from very different distributions. With the second strategy, some prisoners are simply destined to die or live given a particular permutation, and with the first strategy (i.e., no strategy), there is "truly" a 1/2 chance for every permutation.

=== Monty Hall problem ===

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]]:<ref name="landsberg" />

:''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 they are 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 they 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 {{sfrac|4|9}} (about 44%). The optimal strategy is, however, as follows:

* Player 1 first opens door 1. If the car is behind the door, the player is successful. If the keys were behind the door, the player next opens door 2; if instead the goat was behind the door, the player next opens door 3.
* Player 2 first opens door 2. If the keys are behind the door, the player is successful. If the goat was behind the door, the player next opens door 3; whereas if the car was behind the door, the player 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):

:{| class="wikitable"
| || Car − Keys − Goat || Car − Goat − Keys || Keys − Car − Goat || Keys − Goat − Car || Goat − Car − Keys || Goat − Keys − Car
|-
| Player 1
| style="background:#B9FFC5;" | Door 1: Car
| style="background:#B9FFC5;" | Door 1: Car
| style="background:#B9FFC5;" | Door 1: Keys <br /> Door 2: Car
| style="background:#FFCBCB;" | Door 1: Keys <br /> Door 2: Goat
| style="background:#FFCBCB;" | Door 1: Goat <br /> Door 3: Keys
| style="background:#B9FFC5;" | Door 1: Goat <br /> Door 3: Car
|-
|-
| Player 2
| style="background:#B9FFC5;" | Door 2: Keys
| style="background:#B9FFC5;" | Door 2: Goat <br /> Door 3: Keys
| style="background:#B9FFC5;" | Door 2: Car <br /> Door 1: Keys
| style="background:#FFCBCB;" | (Door 2: Goat) <br /> (Door 3: Car)
| style="background:#FFCBCB;" | (Door 2: Car) <br /> (Door 1: Goat)
| style="background:#B9FFC5;" | 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 {{sfrac|2|3}}, which is optimal since the first player cannot have a higher winning probability than that.<ref name="landsberg">{{citation|author=Adam S. Landsberg|title=The Return of Monty Hall|journal=Mathematical Intelligencer|volume=31|pages=1|number=2|year=2009|doi=10.1007/s00283-008-9016-8|doi-access=free}}</ref> 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 {{sfrac|2|3}} when the optimal strategy is employed.<ref>{{citation|author=Eric Grundwald|title=Re: The Locker Puzzle|journal=Mathematical Intelligencer|volume=32|pages=1|number=2|year=2010|doi=10.1007/s00283-009-9107-1|doi-access=free}}</ref>

=== Odd number of tries ===
Instead of having to find their number within the first 50 tries, the test could be finding the number within the 50 odd-numbered tries, {{math|1, 3, ..., 97, 99}}.  Any individual prisoner has a 50% chance of finding their own number on an odd-numbered try.  The main strategy will work for all the prisoners if the permutation of the prisoners contains only cycles of odd length.  For 100 prisoners the probability that all will succeed using the main strategy is approximately 7.9589%, which is substantially better than the probability {{math|(1/2){{sup|100}}}} that would be obtained if each prisoner opened drawers independently at random.

== See also ==
* [[Philosophy:Prisoner's dilemma|Prisoner's dilemma]]
* Three prisoners problem
* [[Unexpected hanging paradox]]
* [[Random permutation statistics]]
* [[Golomb–Dickman constant]]

== References ==
{{Reflist}}

== Literature ==

* {{citation|author=[[Biography:Philippe Flajolet|Philippe Flajolet]], [[Biography:Robert Sedgewick (computer scientist)|Robert Sedgewick]]|title=Analytic Combinatorics|publisher=Cambridge University Press|year=2009|isbn=978-1-139-47716-1}}
* {{citation|author=[[Biography:Richard P. Stanley|Richard P. Stanley]]|title=Algebraic Combinatorics: Walks, Trees, Tableaux, and More|series=[[Undergraduate Texts in Mathematics]]|publisher=Springer|year=2013|isbn=978-1-461-46998-8}}
* {{citation|author=Peter Winkler|title=Mathematical Mind-Benders|publisher=Taylor and Francis|year=2007|isbn=978-1-568-81336-3}}

== External links ==
* Rob Heaton: [http://robertheaton.com/2014/01/13/mathematicians-hate-civil-liberties-100-prisoners-100-boxes/ Mathematicians hate civil liberties - 100 prisoners and 100 boxes], 13 January 2014
* Oliver Nash: [http://ocfnash.wordpress.com/2009/12/12/pity-the-prisoners/ Pity the prisoners] {{Webarchive|url=https://web.archive.org/web/20140714230456/http://ocfnash.wordpress.com/2009/12/12/pity-the-prisoners/ |date=2014-07-14 }}, 12 December 2009
* Jamie Mulholland: [https://web.archive.org/web/20140714120037/http://people.math.sfu.ca/~jtmulhol/math302/notes/25-Prisoners-in-Boxes.pdf Prisoners in Boxes], Spring 2011 (PDF)
* MinutePhysics: {{YouTube|eivGlBKlK6M|An Impossible Bet}} and {{YouTube|C5-I0bAuEUE|Solution to The Impossible Bet}}, 8 December 2014
* Robert Feldt: [https://gist.github.com/robertfeldt/5038002a2654a0f06e4d8af51ab5d2f6 Stochastic simulation in Julia] to check the optimal strategy, 6 July 2022

[[Category:Probability theory paradoxes]]
[[Category:Permutations]]

{{Sourceattribution|100 prisoners problem}}