Yet Another Hat Puzzle (Maybe)
There are n players who are allowed to communicate, and then the game starts and they are not allowed to communicate thereafter. At the start, each player is given red hat with prob p and blue hat with prob 1-p. Each player is allowed to see all others' hats but not their own. Each player is then (separately from everyone else) allowed to guess the color of their hat or choose to pass. Success: at least one player should guess and all who guess should be correct. How high can one make the prob of success?
ps: With p=1/2, this is the well-known puzzle discussed by Sara Robinson. In that case, the prob is like 1-1/n. Peter Winkler and Elwyn Berlekamp among others discuss the problem in this article, and establish the connection to Hamming codes. So, may be there is a clean solution for the general p in terms of weighted codes? For small n, one should write down the hat combinations and work out the probability.
ps: With p=1/2, this is the well-known puzzle discussed by Sara Robinson. In that case, the prob is like 1-1/n. Peter Winkler and Elwyn Berlekamp among others discuss the problem in this article, and establish the connection to Hamming codes. So, may be there is a clean solution for the general p in terms of weighted codes? For small n, one should write down the hat combinations and work out the probability.
Labels: aggregator
posted by metoo at 6:13 PM
4 Comments:
http://www.hpl.hp.com/research/info_theory/hats_extsum.pdf seems to claim a solution.
Another modification of the original puzzle which i come up with while thinking about solution (and which makes it a bit simpler), is for even $n$, to require *everyone* to tell the color of their hat. I was actually surprised by the (relatively high) success probability.
I suppose better than 1/2^n.
-- metoo
A decoding algorithm for Hamming code
We defined binary [7,4,3] Hamming code as C1={(x1,x2,x3,x4,x5,x6,x7): x5=x1+x2+x4, x6=x1+x3+x4, x7=x2+x3+x4}. The textbook gives a general description of binary Hamming codes through parity matrices, and the [7,4,3] Hamming code can be obtained by letting r=3 in the general definition. Consider the following description of the Hamming code. Let C2 be the code those parity check matrix H (according to the standard definition of a parity check matrix. Recall that the book’s definition of a parity check matrix is the transpose of the standard definition) is the matix those columns are binary representations of integers 1-7. (for example, binary representation of 1 is [0 0 1], and of 6 is [1 1 0])
(a) Show that the codes C1 and C2 are equivalent.
(b) Use the parity check matrix of C2 to devise a decoding algorithm that doesn’t use cosets (or coset leaders) and correctly decodes received vectors when they contain exactly one error.
Hamming code and the hat puzzle
The binary Hamming code of length 7 has an interesting connection to a well known puzzle: “The Hat Problem”. The puzzle is as follows:
At a mathematical show with 7 players, each players receives a hat that is red or blue. The color of each hat is determined by a coin toss. So the hat colors of players are determined randomly and independently. Each person can see the other player’ hats but not his own. When the host signals. All players must simultaneously guess the color of their own hats or pass. The group shares a $1 million prize if at least one player guesses correctly no players guess incorrectly.
No communication of any sort is allowed between the players during the show. But they are given the rules in advance and they can have an initial strategy session before the game starts. What should they do to maximize their changes?
(a) There is an obvious strategy with a 50% chance of winning. What is that?
(b) Is there a strategy with a higher chance of winning?
As you might predict there is a strategy with a much higher chance of winning than 50%, and it makes use of the [7,4,3] Hamming code. The fact that the Hamming code is perfect and the 1-error correcting makes this solution possible. In fact that is the best possible solution for the puzzle. Describe how the Hamming code can be used to solve this puzzle with a winning probability of 7/8.
Post a Comment
<< Home