7
$\begingroup$

For starters, this problem doesn't originate from me, it's a friend's coding theory problem and I got interested, thinking about it, but I can't think of any as I only have very basic coding theory knowledge. (I'm not taking that course btw)

So the problem goes as follows~

A perverse extra terrestrial force has captured 7 humans, out of desire to get a clue about the intelligence of the human race. The next day, they will be put to a test; if they succeed, they will be returned home safely and humanity will probably not be bothered anymore, however if they fail, they will all be disposed of, and humans will be seen as weak and suitable for enslaving....

They are told the following: The next day, each of them will get a hair-coloring, at random, either blond or black, without knowing which. After hair-coloring, they will be all brought together. At that moment, each person will be able to see everyone's hair-color except their own. Then, every person is required to either guess their own hair-color by writing the color on a piece of paper, or to refrain from guessing. All pieces of paper are collected; if all guessers guess correct, with at least one person guessing, they succeed the test, but if at least one guesser guesses it wrong, they fail. Then they are sent off to discuss their strategy...

What should they do? An obvious strategy is to design one person to randomly guess a color; that will save the humanity half of the times. However, they can do (much) better. Imagine you are one of the seven, provide the team with a good strategy.... (Hint: Think of the coloring as an unknown binary word, and think of the missing color as a possible error)

So, what could possibly be a good method?

$\endgroup$
7
  • $\begingroup$ Do the people know if the others are guessing or refraining? $\endgroup$
    – fgp
    Apr 1 '14 at 14:51
  • 1
    $\begingroup$ I don't think it matters because the hair color is determined randomly. $\endgroup$ Apr 1 '14 at 14:54
  • 4
    $\begingroup$ This is Todd Ebert's PhD thesis. It's described in many coding theory books. See the hat puzzle. $\endgroup$
    – Git Gud
    Apr 1 '14 at 14:54
  • $\begingroup$ @ireallydonknow But it'd provide them with a way to communicate... $\endgroup$
    – fgp
    Apr 1 '14 at 14:57
  • 1
    $\begingroup$ @ireallydonknow I guess this is not what you want, so you should explicitly forbid it: Everbody talks with another person. As nobody wants to die, they tell each other what the others hair color is. Done. No guessing needed at all. $\endgroup$ Apr 2 '14 at 15:04
4
$\begingroup$

As mentioned by Git Gud above, this was introduced by Todd Ebert in his PhD thesis. I was not able to find the thesis online, but here is a solution that uses Hamming Codes. First, some notation. I will use the binary Hamming Code of length 7, which for me means all vectors $x=(x_1,\dots,x_7)$ such that $x_i\in \{0,1\}$ and, working modulo 2, we have
$$ x_1+x_3+x_5+x_7=0\\ x_2+x_3+x_6+x_7=0\\ x_4+x_5+x_6+x_7=0 $$ Some things I will mention without proof about this code: First, it has dimension $4$, meaning that it contains $2^4$ codewords. Second, it is one error correcting, meaning if a single $x_i$ is flipped (from $0$ to $1$ or vice versa), we can detect the error and successfully recover the original codeword.

Now how do we solve the problem with this?

We label each person 1 through 7, and create a binary word of length 7 based on the hair color each person gets. Namely, we let $w=(w_1,\dots,w_7)$ with $w_i=0$ if person $i$ has blonde hair, and $w_i=1$ if person $i$ has black hair. To determine the guessing strategy, I will display the strategy for person 1. The strategy for person $i$ is similar.

Person $1$ sees six letters of $w$. Namely, they know that $w$ has the form $$ (?,w_2,w_3,\dots,w_7). $$ Now if it is the case that
$$ (0,w_2,w_3,\dots,w_7) $$ is in the Hamming Code, then person $1$ guesses $1$. Similarly, if $$ (1,w_2,w_3,\dots,w_7) $$ is in the Hamming Code, then person $1$ guesses $0$. If neither option is in the Hamming Code, then person $1$ does not guess.

Is this strategy well defined? Note that since the Hamming Code is one error correcting, only one of the listed codewords could possibly be in the Code, so person $1$ will never have two conflicting choices. The only other difficulty is to show that someone always guesses. If it is the case that $w$ is in the Hamming Code, then each of the seven people will guess. Consider the case in which $w$ is not in the Hamming Code. Let $$ w_1+w_3+w_5+w_7=\alpha_1\\ w_2+w_3+w_6+w_7=\alpha_2\\ w_4+w_5+w_6+w_7=\alpha_3 $$ From our definition of the Hamming Code, at least one of $\alpha_1,\alpha_2,\alpha_3$ is nonzero. I will leave it to you to check that, in this case, the decimal number represented by the binary number $\alpha_3\alpha_2\alpha_1$ is the number of a person that will guess, and moreover that person will be the only person that will guess.

Now how successful is this strategy? Again, if $w$ is in the Hamming Code, then all seven people will guess, and in fact they will all guess incorrectly. But if $w$ is not in the Hamming code, then only one person will guess, and it is easy to see that, in this case, this person always guesses correctly. Thus the probability of failure is the probability that $w$ is in the Hamming Code. From the note above, there are $2^4$ codewords, out of a total of $2^7$ binary words. Thus the probability of success is $$ \frac{2^7-2^4}{2^7}=\frac{7}{8}. $$ I think you could make an argument that this is in fact the best possible strategy, although I have not formalized it and could be wrong. But at the very least it gives a better result than $\frac{1}{2}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.