4 hats puzzle

[ANANymous]

Can someone solve the following brainteaser with an explanation of how the people in the problem choose hat color:

There are 4 people wearing black or white hats. They do not know the color of their own hat. They cannot communicate. They must come up with a strategy for simultaneously shouting out a hat color or keeping their mouth shut. Your goal is to come up with the solution that yields the highest probability of getting at least one hat color correct and no hat colors incorrect. For example, if the hats are black black black white in that order, and you guess black, doesn't guess, doesn't guess, doesn't guess, then this would count as a successful attempt; however if you guessed black, black, black, black, this would be unsuccessful.

Semi spoiler below-the solution for 3 people:

Using 0 as representation for white and 1 for black, you have the following table seating available. 000, 001, 010, 011, 100, 101, 110, 111

If every time you are at the table and you see two hats of the same color, you guess the opposite color, you will guess correctly in 6 out of 8 attempts, and if you do not see two hats of the same color, then you pass/ do not guess. This yields a 75% win rate for this game among the 3 participants.

Thank you in advance for answers.

[araver]

There has been something similar posted: http://brainden.com/forum/topic/13034--

But it does not work for n=4.

In short the optimal solution for other values of n (including n = 3) is:

Spoiler

For n=2^m-1 (n=3,7,15,31,63..) a nice statement holds: "The set of n-bit strings can be partitioned in radius-1 balls".

This means that choosing a nice set of possible strings (m) will get you the following optimal strategy for  1-1/2^m probability of success. E.g. for n =3, m = 2, winning strategy is 75%.

They have to communicate beforehand so that they establish the strategy (step 0 below). Assume that one of them is the always the first and use 1/0 for black/white. There is an unknown number with exactly 3 bits of information of which everyone knows 2 bits.

Step 0) choose a set A that partitions the space (such as a Hamming set) of all n-bit numbers where every number not in A can be obtained from one in A flipping exactly 1 bit. e.g. for n=3 A = {000, 111}. One can easily get by flipping exactly one bit 000 (100, 010, 001) and 111 (011, 101, 110). A has exactly m elements (n = 2^m-1).

Step 1) compute a and b which are two possible solutions with 1 and 0 as your own hat and the rest of the bits you see.

Step 2) If neither a nor b are in A, abstain.

Step 3) If a or b are in A (at most one due to how A was constructed), choose the one that does not belong to A.

The above strategy fails if the actual hats are describing one of the elements in A since all would choose the wrong color in Step 3. So 2/8 chances of failing means 75%.

In the rest of the cases (6/8), the solution (denoted d) is 1 bit away from an element x in A which means:

- the person that doesn't know that bit will figure out which of a and b is not in A in Step 3 and make the correct choice.

- the others will abstain. Not easy to understand why but it's a property of the partitioning set itself - every n-digit number belongs to exactly one radius-1 ball. This is why it doesn't work for other values of n.

Assume the solution is not in A, someone other (than the one who corresponds to the bit flipped from an element x in A) computes some a_j and b_j as candidates in step 1. One of these candidates is d the solution and the other (denoted c) differs from d in one bit. We already know d is not in A.

Assuming that c is in A we get x and c each differing from d in exactly one bit but a different position. Which is false b/c of how A was constructed. So c is not in A, therefore this guy will abstain in step 2.

Since all but one abstain and that one gets it correctly, the game is won.

Now for n = 4, I do not know of an optimal solution.

[araver]

A solution with 50% odds is

Spoiler

16 possibilities.

Choose A = {0000,1111} in step 0.
0000 (1000, 0100, 0010, 0001)
1111 (0111, 1011, 1101, 1110)

If 0000 or 1111 they all choose wrong in step 3.
If 1000, 0100, 0010, 0001, 0111, 1011, 1101, 1110, then they all choose correctly.
E.g. for 1000
The first sees 1000 and 0000 as possibilities. 0000 is in A so he chooses 1000
The rest see 2 not in A e.g 1010 and 1000 as possibilities. Neither are in A so they abstain.

If 0011, 0101, 0110, 1001, 1010, 1100 then they fail by all abstaining since these are all 2 bits away from both elements in A.

8/16 = 50% chance of success.

 

[ANANymous]

I appreciate the responses araver; however this link does not provide the solution I am looking for:

http://brainden.com/forum/topic/13034--

And the answer I believe is greater than the answer to 3 people.  I believe it is not 50% based on the person who asked this question initially (who also knew the answer, but whom I can no longer locate).

Spoiler

I am almost certain the answer is 7/8ths, but I am unsure how the selection process works (my confidence for the answer comes from the question giver acknowledging this as the right answer).  The trick is I cannot explain how the selection process works for n = 4.

 

Edited October 23, 2016 by ANANymous

[bonanova]

First thoughts (that are consistent with a better result than in the 3-person example):

Spoiler

It's tempting to say 50% is the best possible result since whatever pattern you see your hat is black or white with equal likelihood.

But the OP doesn't ask how an individual can guess correctly more often than not: rather, it's the group response that matters. And the 3-person example shows the group can succeed in more than half of the cases. One reason is we can tell people when not to guess. But more importantly, we can pack a disproportionately large number of wrong individual guesses into a few (otherwise) disastrous cases. By "otherwise" I mean that in the terms of the OP it's not worse to have many wrong individual guess than to have only one. That is a huge clue.

So you look for a strategy where the wrong individual guesses  are clustered into a few disastrous cases, remembering that all cases have equal likelihood. In the 3-person example the disastrous cases are 111 and 000. For those cases, all three persons make a guess and all of their guesses are wrong. In the six other cases, when one hat differs from the other two, each person either abstains or guesses correctly. The group success probability is thus 6/8.

Following the lead of the 3-person example, look for strategies where everyone will guess wrong in a very few special cases, i.e. 1111 and 0000. If you can get all the wrong individual guesses into those two cases you can achieve 14/16 = 0.875 success probability. And you can't do better than that. 1111 and 0000 have the same likelihood of success, and they together comprise 12.5% of the cases. That's the smallest available container for housing the wrong individual responses.

 

[araver]

Yeah, that's not what I meant. I did not mean to discourage you from trying, just trying to put you in the right direction.

Lemme rephrase that:

If you could do a strategy with the odds you are expecting, you would design a very efficient error correcting code. There's a thing called Hamming bound preventing that. Non-trivial cases when one happens to reach that bound have been mapped out since the 70s (for prime alphabets, so including binary). Mathematical proofs. One class is the one I gave you in the spoiler above. The other works for larger n.

In basic terms, every bit of information you add is another entropy generator that messes up the cases. Only in perfect settings one can separate entropy in different "jars" efficiently.

P.S. All of these codes are used in every bit of technology you currently use.

[ANANymous]

1 hour ago, bonanova said:

Following the lead of the 3-person example, look for strategies where everyone will guess wrong in a very few special cases, i.e. 1111 and 0000. If you can get all the wrong individual guesses into those two cases you can achieve 14/16 = 0.875 success probability. And you can't do better than that. 1111 and 0000 have the same likelihood of success, and they together comprise 12.5% of the cases. That's the smallest available container for housing the wrong individual responses.

Herein lies my initial question:  How do we achieve 14/16, what is the selection method used by the 4 hat wearing participants?  Is that solvable?

[plainglazed]

perhaps this tho would consider it cheating per the assumed spirit of these types of brain teasers

Spoiler

What is meant by "simultaneous" when only one will possibly respond?  We know if we mute one of the four hat wearers we have the same scenario as the three person 75% result.  If those three wait an instant for a potential response from that fourth, who would only respond if he sees three of the same hat color, he could get two of the four correct that the three alone would miss.

 

[ANANymous]

This would be considered cheating I believe, it is not the solution being sought, but was a nice try

[phaze]

if they all agree on answering the opposite colour  if they see 3 hats of the same colour this would Fail for 0000 and 1111 but suceed for 0001 0010 0100 1000 1110 1101 1011 and 0111 with only one person making a claim and others remaining silent.  If nobody responds they have not lost as they only need to respond simultaneously.  They now know two hats are the same and so at a different agreed point of time they all can say the opposite colour thus getting it right 14 out of the 16 different options.

[bonanova]

I like phaze's solution. I would add just a tweak, as described in the second spoiler.

Recap:

Spoiler

In the 3-hat problem, there are only two color distributions: 3-0 and 2-1, in some order. Each observer sees either 2-0 or 1-1. In the latter case the distribution is 2-1, but the majority color is not known. It depends on the color of the observer's hat. So that observer must remain silent. In the former case, the distribution is either 3-0 or 2-1 and the majority color is known. Since in 75% of the cases the distribution is 2-1, calling the minority color gives the group a success probability of 0.75.

We have to guaranty not only that no one guesses wrong but also that at least one observer will guess right. Fortuitously, in the 3-hat problem, at least one observer will see 2-0. At least one observer will give a correct response.

(All of this was given in the OP.)

The 4-hat problem permits three color distributions: 4-0, 3-1 and 2-2 in some order. Each observer, however, still sees one of two things: 3-0 or 2-1 in some order. In the former case the distribution is either 4-0 or 3-1, and the majority color is known. Since in 75% of those two cases it's 3-1, calling the minority color gives the group a success probability of 0.75, just as in the 3-hat case. But when the observer sees 2-1, the distribution is either 3-1 (with the majority color known) or 2-2. 

It's this final uncertainty that kills us. When the distribution is 2-2, then no observer will see 3-0, and everyone will remain silent. But the OP requires that at least one observer speaks his correct color. So further guidance is needed.

To put it another way: For 3 hats, at least one observer will see 2-0. So he can speak and the others remain silent. For 4 hats there is no certainty of an observer seeing 3-0. The distribution can be 2-2, and in those 6/16 of the cases, using the 3-hat solution, no one will speak.

(It is the needed further guidance that phaze's post provides.)

phaze proposes that we take initial silence by all observers as an indication that the distribution is 2-2. In that case, every observer sees 2-1. Further, he knows his hat is the minority color and, after a pause say of a predetermined number of seconds, he guesses that color.

With phaze's solution, only the 4-0 case is guessed incorrectly, and that (as I had pointed out) is the Holy Grail. They comprise 2/16 of the cases, giving the group the theoretically optimal 7/8 success probability.

Tweak.

Spoiler

The crux of the 4-hat solution is that, when the distribution is 2-2, everyone will see 2-1, initially be unable to discern between the 2-2 and 3-1 cases and remain silent to permit someone who might see 3-0 to speak. If no one speaks, then everyone knows two things: the distribution is 2-2, and his own color is the minority color.

But now the problem is for everyone to shout his color simultaneously, presumably without aid of say a stopwatch.

A tweak can be added to the solution. During the pre-game strategy meeting, a captain can be appointed. When there is initial silence, of say more than five seconds (which will give even the slowest thinker of the group a chance to respond if he sees 3-0) the the captain (only) shouts his (minority) color.