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:
- If they see the same color, then they answer the color that they don't see.
- 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}$
No comments:
Post a Comment