100 Prison Problem- Why does this solution not work?

Question

There is a combinatoric riddle which goes as follows: 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.

The best solution found thus far is one where: 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.

Through this process, as long as a cycle of more than 50 does not exist, there is a fairly high (roughly 30%) chance that the prisoners succeed. This is because there is a roughly 70% chance that a cycle of 51 or more exists.

When trying to calculate the probability of there being a cycle of 51 or larger, I had a prisoner start at his own drawer. The probability that the drawer didn't contain his number should be 99/100. In such a case, he goes to the second drawer (whose number was found in the first drawer). The probability that this drawer doesn't contain his number is 98/99. Thus the probability of him going through 51 or more drawers before finding his own number, I assume, should be 99/100 * 98/99 * 97/98 *...*49/50. Hence, the probability of there being a cycle of size 51 or more by this chain of reasoning would be 49/100.

I was hoping to ask if someone here could let me know the flaw in my line of reasoning.

Thank you.

Answer 1

Let me provide a method for calculating the number of permutations in $S_{n}$ that contain a $k$-cycle when $2k>n$.

Clearly at most one of these cycles can exist, we can select it in $\binom{n}{k}\times (k-1)!$ ways and then permute the remaining elements in $(n-k)!$ ways.

---

We also note that the probability a $51,52,\dots$ or $100$-cycle exists is just the individual sum of probabilities as these events are mutually exclusive.

---

Therefore the probability the prisoners fail is:

$$\sum\limits_{k=51}^{100} \frac{\frac{100!(k-1)!(100-k)!}{k!(100-k)!}}{100!}=\sum\limits_{k=51}^{100} \frac{(k-1)!}{k!}=\sum\limits_{k=51}^{100} \frac{1}{k}\approx 0.688$$

Answer 2

Your flaw is somewhat similar to the birthday paradox: each particular prisoner has a 49/100 chance of being in a chain of 51 or more. But the probability of at least one prisoner being in a chain of 51 or more is about 70%. Going from the first two the second is complicated, because the probabilities are not independent: if one prisoner is in a cycle of 51 or more, then at least 50 other prisoners are also in cycles of 51 or more.

Answer 3

The answer of @Acccumulation already mentions it, but I think it needs more emphasis: dependence is the key. Assuming the permutation of numbers is completely random, it does not matter which half of the drawers the first prisoner opens – as long as these are 50 different drawers (opening the same drawer twice is obviously suboptimal), the probability of finding his number is exactly $1/2$ whatever he does.

The key is in dependence of choices of the prisoners.

Suppose that $P(A_i)$ is the probability that the $i$'th prisoner found his number. As we have observed, $P(A_1) = 1/2$, but in fact $P(A_i) = 1/2$ for any $i$. However, because prisoners can make their choices based on the permutation hidden in the drawers, they are able to force $A_i$ and $A_j$ to be dependent and concentrate the failures on one particular set of permutations.

More precisely,

• consider the set of all possible permutations in drawers $\Omega = \{\pi_1, \pi_2, \ldots\}$,
• let's call a permutation $\pi$ successful for the $i$'th prisoner if his searching strategy succeeds in finding his number,
• define $\Omega_k$ as the set of permutations that are successful for all prisoners in range $\{1,\ldots, k\}$.

Basic probability gives us $P(A_1) = \frac{|\Omega_1|}{|\Omega|} = \frac{1}{2}$. Now, if the second prisoner were to make his choices randomly, then he would split $\Omega_1$ further in half, that is the size of $\Omega_2$ would be half of the size of $\Omega_1$ and a quarter of $\Omega$. On the other hand, by adjusting his strategy, i.e., taking into account the permutation he is observing, the second prisoner can try to concentrate his successes on the permutations in $\Omega_1$ and his failures on the permutations in $\Omega \setminus \Omega_1$. In this way $|\Omega_2|$ is strictly bigger than $|\Omega| / 4$, although smaller than $|\Omega_1|$. If all prisoners follow the suit, when one fails, a lot of other will fail too, but also when one succeeds, many other will succeed as well.

Finally to give you some intuition about why the particular drawers opened do not matter much (i.e., why it matters less than the dependence): suppose that we make the prisoners agree on an arbitrary permutation $\sigma$ and follow a strategy where the $i$'th prisoner starts with $\sigma(i)$ and when he finds $x$ in the drawer, follows up with $\sigma(x)$. This strategy does not change anything in the probabilities – because the permutation $\pi$ in the drawers is random, the probability of $\pi \circ \sigma$ having a cycle of length $\geq 51$ is also less than $70\%$. While no prisoner can beforehand commit to a set of drawers to open, the opened drawers are, due to $\sigma$, in a way, arbitrary.

Bonus puzzle:

There is yet another puzzle that uses a similar technique. There are 100 prisoners that wear hats, black or white (arbitrary assignment, there are no count constrains). They all see each other, but not the color of their hats. Each of them writes on a piece of paper (so that the others do not see) what color of hat they think they have. If all have guessed correctly, they are free. What is the best strategy for the prisoners to guess their hat colors?

I hope this helps $\ddot\smile$