Let’s start with a small number, say six prisoners and an equal number of numbered cards and numbered drawers.

Placing the cards in the drawers effectively makes a one-to-one map from the set S = {1, 2, …, n} onto itself1. If that sounds confusing, imagine drawing n nodes and then drawing arrows between them, so that every node has exactly one “outgoing” arrow and one “incoming” arrow (and yes, a number can point to itself and satisfy these rules)

Table 1: A 6-permutation example
Drawer Card
1 4
2 6
3 1
4 3
5 5
6 2

With only six elements, the mapping could look like this:

1 --------> 4      +-> 2 --+
                   |       |
^           |      |       |       5 --+
|           |      |       |           |
+---- 3 <---+      +-- 6 <-+       ^   |
                                   +---+

Any way of drawing this map ends up in one or more disjoint cycles. With this map in mind, the general strategy is simple:

  1. Every prisoner opens the drawer with their own number.
  2. If the card matches the prisoner’s number, he’s done.
  3. Else the prisoner now opens the drawer indicated by the card that he just saw.

Why does this work? No matter how the graph is drawn, by starting with their own number, every prisoner ensures that they are looking in a cycle that necessarily contains their own number. The question is whether this cycle is larger than n/2. For any 2n prisoners (n ∈ ℕ) this probability is (Wikipedia contributors 2020)


1 − ln 2 ≈ 0.30685

 

 

References and Bibliography

Wikipedia contributors. 2020. “100 Prisoners Problem — Wikipedia, the Free Encyclopedia.” 2020. https://en.wikipedia.org/w/index.php?title=100_prisoners_problem&oldid=969369446.


six ⇐ Part of Brevity Quest 2020Catalan's conjecture


  1. Alternatively, this is a permutation of the numbers 1 − n

Log in or register to write something here or to contact authors.