Prisoners, boxes, and beautiful graph theory

Probability Level 2

There are 1000 prisoners and the warden decides to play the following game.

The prisoners are numbered 1 through 1000.
There is a room with 1000 boxes, numbered 1 through 1000.
There are 1000 pieces of paper, each numbered 1 through 1000.

The pieces of paper are randomly distributed one per box. (That is, paper #445 is just as likely to be in box #445, box #1, or any other box.)

Each prisoner will be taken in turn into the room with the boxes. He will open boxes of his choice one-by-one until either he finds the piece of paper with his own number on it or he has opened 500 boxes. Then he must leave and the room is reset. No communication between the prisoners is allowed once the game has begun.

If every prisoner finds the piece of paper with his or her number, then they will all be released. If a single prisoner fails to find his or her paper, then all of the prisoners will be locked up forever.

The prisoners are allowed to form a strategy before the game begins. What is the optimal strategy for the prisoners?

Approximately what is this strategy's probability of success?

[Note: there is both a cool graph-theoretic approach to this problem and also a group-theoretic approach. The end result of both is very simple and very beautiful. Have fun.]

[50\%, 100\%]

[10\%, 20\%)

[30\%, 40\%)

[20\%, 30\%)

[0\%, 10\%)

[40\%, 50\%)

1 solution

Maggie Miller
Sep 15, 2015

View the arrangement of papers in boxes as an element of the symmetric group $S_{1000}$ (the permutation in which $n$ is sent $m$ iff locker $m$ contains the slip labeled $n$ ). Then the prisoners will succeed exactly when this element has no cycle of length greater than $500$ .

For $k>500$ , there are ${1000\choose k}(k-1)!(1000-k)!$ elements in $S_{100}$ with cycles of length $k$ . Therefore, the probability of the prisoners succeeding is $\displaystyle 1-\frac{\sum_{k=501}^{1000}{1000\choose k}(k-1)!(1000-k)!}{1000!}\approx.307\in\boxed{[30\%,40\%)}$ .

(This is a famous problem, and in general one can show that when there are $2N$ prisoners and boxes and each prisoner picks $N$ slips, the probability of success tends to $1/e\approx0.368$ as $N\to\infty$ ).

Small correction: The prob. of success tends to 1 - ln $(2)$ , not 1/e . By chance, did you think of the "Secretary problem" while writing the text you put as additional information in brackets?

Meer Kat - 5 years, 8 months ago

Great solution. Just curious about one thing: How do you show that this is the optimal strategy?

nicholas chin - 5 years, 7 months ago

There is actually a simpler version of this problem, with a simple explanation: https://www.youtube.com/watch?v=vIdStMTgNl0

Siva Budaraju - 4 years, 3 months ago

more information : https://en.wikipedia.org/wiki/100 prisoners problem

Thomas Lesgourgues - 3 years, 2 months ago

Prisoners, boxes, and beautiful graph theory

1 solution

0 pending reports