Guess colour of hats from neighbors

Four people stand in a circle, each wearing a hat which is one of $n$ colours. Each person can see the two neighbours. They must simultaneously guess the colour of their own hat. If at least one of them guesses correctly, they all win. For which $n$ do they have a winning strategy?

For $n=1$ they win trivially. Also, note that the two opposite people see the same two neighbours.

• Do we know how many hats of each colour is distributed? – астон вілла олоф мэллбэрг Sep 12 '16 at 10:24
• No, it can be any number. – pi66 Sep 12 '16 at 10:25
• if it's n=2, they can guess the other color to their left neighbour, and no one being correct would imply that there was only 1 color, so they have to win that way - becasue there can not be a 'run' of 4 colors the same – Cato Sep 12 '16 at 10:27
• @AndrewDeighton Suppose the order was $BRBR$, then the first person would guess $R$, the second $B$, the third $R$ and the fourth $B$. They all chose their left neighbours, but none of them got it right. – астон вілла олоф мэллбэрг Sep 12 '16 at 10:30
• Surely if colors don't have to be used, then n=2 has no winning strategy – Cato Sep 12 '16 at 10:46

I will expand on my comment. Note that this not a complete solution to the problem and is surely not an elegant one. What I tried is to show that there is no winning strategy for $n=2$, but surprisingly, it seems there actually is.

Let us assume that $n=2$ and let us denote by $x_i\in \{0,1\}$ the color of hat of $i$-th person. Strategy amounts to choice of $(f_1,f_2,f_3,f_4)$ where $f_i\colon \{0,1\}^2\to \{0,1\}$ is a function which determines what $i$-th person will say depending on the color of hats of their neighbours. There is no winning strategy if for any fixed choice of $(f_i)$, the system

\begin{array}{c r} \begin{align} f_1(x_4,x_2) &= 1 - x_1\\ f_2(x_1,x_3) &= 1 - x_2\\ f_3(x_2,x_4) &= 1 - x_3\\ f_4(x_3,x_1) &= 1 - x_4 \end{align} & \tag 1 \end{array}

has a solution in $\{0,1\}^4$.

If for all $(f_i)$ there exists a solution $(x_i)$ of the above system, then there exists a solution for the system

\begin{array}{c r} \begin{align} f_1(1-f_4(y,x),1-f_2(x,y)) &= 1-x\\ f_3(1-f_2(x,y),1-f_4(y,x)) &= 1-y \end{align} & \tag 2 \end{array}

as well, by setting $x = x_1,\ y = x_3$. (Actually, the systems are equivalent.)

Hence, if we show that there exists strategy $(f_i)$ such that system $(2)$ has no solutions, then it is a winning strategy.

At this point, I just randomly tried if

$$f_2\equiv \left(\begin{array}{c c} 1 & 0\\ 0 & 1 \end{array}\right),\ f_4\equiv \left(\begin{array}{c c} 1 & 1\\ 1 & 0 \end{array}\right)$$ would work (where $f_k(i,j)$ is the $(i+1,j+1)$-th matrix entry).

Writing down the casework $(x,y)\in\{0,1\}^2$ for the system $(2)$, one can easily find that if we choose $$f_1\equiv \left(\begin{array}{c c} 0 & 0\\ 1 & 0 \end{array}\right),\ f_3\equiv \left(\begin{array}{c c} 0 & 0\\ 0 & 0 \end{array}\right)$$ system $(2)$ has no solutions.