One-Eyed People With Hats

[Trojan Horse]

Here's a variation of the "what color of hat is on my head?" puzzle. I came up with this variation on my own, though I'm sure others have thought of it independently.

First, here's the original puzzle, for those that are not familiar with it:

Five people are playing a game. They are seated in a circle, and a hat (either red or blue) is placed on each person's head. Each person can see the colors of all the other hats, but not his own. Each person must guess the color of hat on his own head. If everyone guesses correctly, the group wins the game; if even one guess is wrong, the group loses the game.

The group is allowed to strategize together before the game begins. But once the hats are in place, they are not allowed to communicate with each other in any way. What strategy gives them the best chance to win?

Answer: Everyone should make their guess under the assumption that the total number of blue hats is even. For example, if someone sees three blue hats and one red hat, he should guess that his hat is blue, so as to make the total number of blues even.

The group will win when the total number of blue hats IS even, which will happen 50% of the time. And since each individual guess always has a 50% chance of being right, there's no way the team can do any better. 50% is the best they can do.

Of course, they could instead all guess that the total number of blue hats is odd. It makes no difference.

Now, here's the variation: let's say that all five people are one-eyed. Each only has his left eye. As a result, each person cannot see the hat on their immediate right; each person can only see the other three hats.

As before, the players can strategize in advance. But once the hats are in place, they can't communicate with each other, and they can't turn their heads to see the person on their right. What is their best strategy now?

[Zag]

I assume they have to make their guesses simultaneously? That is, none of them get to hear the guesses of the others before making their own guess, right?

[Trojan Horse]

Correct.

[Thok*]

[ralphmerridew]

Computer search found 8/32: Assume the pattern is one of rrrrr, rrBrB, rBrBr, rBBBB, BrrBB, BrBBr, BBrrB, BBBrr

[ralphmerridew]

Trying for other numbers hats reveals that for 2,3,4,6 people, maximum win is 1/4; a search of 7 hats found a 1/4 solution, but hasn't run to exhaustion yet.

There ought to be a simple proof that 1/4 is an upper bound for 2 or more hats.

[ralphmerridew]

And there is: Select two adjacent people, Alice and Bob. Define two hatsets as equivalent if all hats, other than those worn by Alice and Bob, are the same. There are 2^n / 4 equivalence classes. It is possible for them to win in at most one hatset in any equivalence class; therefore, they can win at most (2^n/4) / (2^n) = 1/4.

[Trojan Horse]

Congrats, ralphmerridew. That does it.

I'm currently trying to generalize this problem: I'm looking at what happens when there are n colors of hats, and each person can see all but m of the hats (their own, and the m-1 to their right). It's easy to get an upper bound for how well the team can do; it's [1/(n^m)], by a similar reasoning to what you just gave. But I don't yet know that this bound can always be achieved.

[ralphmerridew]

The theoretical maximum seems to always be achievable, and with a linear code.

Number hats 0, 1, ... (NCOLORS - 1).

Definition: A "hat-case" is an ordered list of NPEOPLE values from 0 to NCOLORS-1.

Definition: For two hat-cases A and B, define C := A (+) B as the hatcase such that C[i] = (A[i] + B[i]) mod NCOLORS.

Definition: A set S of hat-cases is a linear code iff:
1) The hat-case with all zeros is in S.
2) For any two hat-cases A and B (not necessarily distinct) in S, A (+) B is also in S.


For any number of colors, the linear code generated by (1,-1,0,...), (0,1,-1,0,...), (0,0,1,-1,0,...) ... (0,...,1,-1) is an optimal solution for m=1.

For any number of colors, the linear code generated by (1,0,1,0,1) and (0,1,1,1,1) is an optimal solution for 5 people, m = 3.

(1,0,1,0,0), (0,1,0,1,0), (0,0,1,1,1) generates an optimal solution for 5 people, m=2.

If there is an optimal solution for n colors, p people, m hidden hats, then there's an optimal solution for n colors, p*d people, m*d hidden hats. (Each person considers only himself, and the people d,2d,3d, ...(p-1)d to his left; split the problem into d disjoint subproblems.).

For p odd, m=2, (1,0,1,0,0,...), (0,1,0,1,0,...), (0,0,1,0,1,0,...), ... (0,..0,1,0,1,0), (0,...,0,1,1,1) generates a solution.

[Zag]

[Nsof]

Call the original puzzle "2 hat colors where each person can see all but own hat" - P(2,1).
Generally, P(n,m) where n is the number of hat colors and m is the number of hats not seen.
The original post asked for P(2,2)

Using the same strategy as suggested in the original post its relatively easy to show
1. P(n,1) = 1/n.

Im having trouble with this*
2. P(2,m) = P(2^m,1)

but then this would follow
3. P(n,m)=(n^m,1)=1/n^m

*Strong intuition/seems right/makes sense/yada yada
reduction maybe?

[ralphmerridew]

This seems to work:

For p people, each able to see m hats, and unable to see p-m hats:
Let Q = (floor (p/m))*m.
Define b(x,y) for 0 <= x < p, 0 <= y < m such that:
b(x,y) :=
1 if x < Q and x == y (mod p)
0 if x < Q and x != y (mod p)
... and the parts when x >= Q, I can't find a general rule that works, but I've been able to find one for every combination of p, m that I've tried.

Consider the linear code generated by { (b(0,y), b(1,y), ..., b(p-1,y)) | 0 <= y < m }. In advance, choose one person as the root. Each person assumes that the hatset is in the code.

[Deception]

Answer:
They can strategize before the game, correct?

Each person holds up fingers denoting the color of the hat the person to their immediate left is wearing in your left hand, and in your right hand the color of hat that the person two spaces to your left is wearing.

1= red
2= blue

Seems easy enough, are you guys over complicating this or am I cheating?

[grz*]

I think you're breaking the clause that they may not communicate *in any way.* If they are sharing information then they are communicating, by definition.