Prisoners and hats

2047 prisoners are kept in a dungeon. One day, the King decided to do an experiment. They will each be given either a blue hat or a red hat and then collected in a room. Each prisoner can see the color of everyone else's hats but not his own. No form of communication is allowed. After a few minutes, the warden will come and ask each of them individually what he thinks the color of his hat is. They can answer "red" or "blue." Each prisoner must answer by whispering to the warden's ear, so that the other prisoners can't hear his answer. Those who can answer correctly will be freed, but those who answer incorrectly will be executed on the spot. The prisoners found out about this experiment the night before, so they had some time to devise a scheme to ensure they can save as many people as possible.

Question 1: What is the scheme that allows everyone to live in this case?

Suppose now the King decided to alter the experiment a little bit. The warden will come to the room immediately after everyone get their hats. Each prisoner is allowed to answer "red", "blue", or "I don't know." If everyone answers "I don't know", they will all be executed. If someone answers "red" or "blue" and he is wrong, they will all be executed. Otherwise, everyone is freed at the same time. In other words, in order for them to live, at least one person must answer "red" or "blue" and he must be right. As before, the prisoners can't hear everyone's answers, and the release or execution is delayed until everyone had given their answers.

Question 2: What is the scheme that allows everyone to live with the highest probability? What is that probability?

Solution

Question 1

For Q1, they can agree to do the following:

"If you see an odd number of blue hats among your friends, go to the North corner of the room, otherwise go to the South corner of the room." Then everyone will split into 2 groups where each group has the same color. Each prisoner then can infer his own color from their group.

Question 2

For Q2, consider the case of 3 prisoners. Each prisoner will see two colors. Then they employ the following algorithm:

1. If they see the same color, then they answer the color that they don't see.


2. If they see different colors, then they answer "I don't know."

For example, if the prisoners are given Red, Red, Blue, then the blue prisoner will answer "blue", and the red prisoners will answer "I don't know" so they all live. Similarly, if they are given RBB, then they will all live. But if they all have the same color, then all of them will answer the wrong color, and they all die. There is a 1/4 probability for them to get all the same color, so the probability of living is 3/4.

Now we generalize this concept to $2^n - 1$ prisoners.

Each prisoner will get an ID number from 1 to $2^n-1$ that's expressed as an $n$ digit binary number. Each prisoner must memorize everyone's ID. Then each prisoner looks at their inmates' hats, and he computes the XOR of all the IDs of the people wearing red hats that he sees. Because XOR is an associative and commutative operation, this computation can be done one at a time. If the final result matches his own number, then he says "BLUE". If the final result is zero, then he says "RED". In any other cases, he says "I don't know."

Now we analyze when they live or die.

Say set $R$ consists of the prisoners wearing red hats and $B$ consists of those wearing blue. Let $x$ be the XOR of all ID's in $R$.

Case 1: $x$ is zero

If $x$ is zero, then all prisoners in $B$ will have zero as part of their calculations, so they will all say "red". For each prisoner $r$ in $R$, he will calculate the XOR of $R - r$. But since we know that the XOR of $R$ is zero, then the XOR of $R - r$ is necessarily $r$'s number itself, so that $r$ will say "blue". This way, everyone answers but they're all wrong, so they all die.

Case 2: $x$ is not zero, but prisoner $x$ wears red

In this case, everyone in $B$ will compute $x$, but since that is not their number, they will answer "I don't know." Also, for each prisoner $r$ in $R$, he will calculate the XOR of $R-r$. Most of them will say "I don't know" because that calculation is not his own number. But we wish to investigate who among them will compute $x$ or zero.

If $\sum (R-r) = x$ (where the summation refers to XOR sum, not conventional sum), then

$\sum (R-r) \oplus r = x \oplus r$

$\sum R = x \oplus r$

But since $\sum R = x$, then $x = x \oplus r$, which means $r = 0$. Since no one's ID is zero, no one will have computed $x$ as a result of their calculations.

If $\sum (R-r) = 0$, then

$x = \sum (R-r) \oplus r = r$

That means prisoner $x$, and only prisoner $x$ will have computed zero, at which case he will say "red". In this case, only one person, that is prisoner $x$ will say red, and everyone else will say "I don't know."

Case 3: $x$ is not zero, but prisoner $x$ wears blue

Again, everyone in $B$ will compute $x$ and prisoner $x$ himself will say "blue." Everyone else in $B$ will say "I don't know." Now, most prisoners in $R$ will say "I don't know" but we wish to see if anyone will have computed $x$ or zero.

The calculations are exactly the same as in case 2, $\sum (R-r) = x \iff r = 0$ which means no one will have computed $x$. $\sum (R-r) = 0 \iff r = x$ which means no one in $R$ will have computed zero.

So in this case, prisoner $x$ will say "blue" and everyone else will say "I don't know."

From all three cases above, we conclude that they will all live if and only if $x$ is not zero. Since the probability of $x$ is uniformly distributed over $x$, then this probability is $1 - \frac{1}{2^n}$