|
|
. . . . . . . . The solution to this puzzle must be much better articulated before it can be presented!
Sixteen prisoners are assembled and told the following: Each will receive
a hat that is either red or blue (the color is selected randomly and each
has a 1/2 probability.) Then, all the prisoners must simultaneously either:
- Try to guess the color of their hats, or
- Pass.
The prisoners will be set free if
- at least one person guesses, AND
- nobody guesses wrong.
Otherwise, they will be executed. The prisoners may consult beforehand to
decide on a strategy, but they will be unable to communicate in any way
after the hats are put on; and all must answer simultaneously.
What is a strategy that would maximize their probability of survival?
Source: unknown
At first, it looks like they have only a 50% probability of survival using a
strategy in which a prisoner selected in advance will guess at random while
everyone else remains silent. But if you think of the 3-prisoner
case, there's an easy strategy that gives them a 75% survival rate: In their strategy session, the prisoners
reason that the probability of their hats all being the same color is only 25%, so they will assume their
hats are not all the same color. Thus, any prisoner who sees two hats the same color will cry out that his
hat is the other color. Prisoners who see two different-color hats will remain silent. This strategy works
in all but the red-red-red and blue-blue-blue cases because apart from those cases, there will always be two
hats of one color and one hat of the other, and the odd man out will always guess correctly.
Now, how can this strategy be expanded to the 16-prisoner case, with an even better probability of survival?
Analysis:
http://mathforum.org/library/drmath/view/52219.html
The gist of the solution is the use of a (15,11) Hamming Code, with the 16th prisoner remaining silent, and hoping for the best.
Since valid Hamming Codes are so improbable, the prisoners will assume their hats represent an invalid Hamming Code.
Each prisoner will have agreed in advance on his bit number, and he will know what prisoners are in each bit group.
When they are assembled, each prisoner will imagine his hat is blue, and then if this makes a valid Hamming Code he will be prepared to cry out that his own hat is red.
In addition, each prisoner will imagine his hat is red, and then if this makes a valid Hamming Code he will be prepared to cry out that his own hat is blue.
Those prisoners who can't see a valid Hamming Code with either color hat will remain silent.
This strategy will fail only if the hats happen to be assigned as a valid Hamming Code. In this case, every prisoner will call out with the wrong answer!
The number of valid (15,11) Hamming Codes is 2^11, and the total number of 15-bit codes is 2^15, so the probability of success is 1-2^-4, or 93.75%
Adding a 16th prisoner who remains silent does not change this chance of success.
More about Hamming Code, and how it can be used to either detect 2 bit errors or correct 1 bit error, etc. Plus Hamming with parity...
http://www.ee.unb.ca/tervo/ee4253/hamming.htm
Another stab at analysis:
We're looking for a single-bit error correcting code like a (15,11,3) Hamming
Code *, which works great for 15 prisoners. It's important that the Hamming
Distance between valid codes be exactly 3, so that every invalid code is exactly
one bit away from being valid, and the prisoner representing that bit can call
out his hat color. Of course, a (16,11,3) code could be made by adding a
sixteenth bit that is always considered valid, regardless of whether it is 1 or
0. For the puzzle, this would be a sixteenth prisoner who remains silent. This
gives the group of 16 the same probability of success that the group of 15 would
have had. But I can't see a way (without cheating; see below) to improve the
odds by adding the 16th prisoner.
Cheating: The 16th prisoner, although he doesn't vote, can immediately close his
eyes upon seeing a valid Hamming Code among his comrades. In that case, everyone
would be able to reconstruct his own hat color from those of the other
prisoners, and give the correct answer. It would be worth trying this approach,
because if the deception were discovered, the prisoners would be executed, but
only in the case in which they would have been executed anyway. If successful,
this approach guarantees 100% survival. If not, the probability remains 15/16.
* A (t,i,d) code has t total bits, i information (i.e. data) bits, and Hamming
Distance d between valid codes. Hamming Distance is best explained by picturing
a t-dimensional hypercube, where each vertex represent one of the 2^t t-bit
codes -- one bit for each dimension. To go from one code to another, it is
necessary to traverse d edges if the codes are d units apart. The Hamming
Distance is the *minimum* distance between any two valid codes.
The webmaster and author of this Math Help site is Graeme McRae.