2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do we know how many hats of each colour is distributed? $\endgroup$ – астон вілла олоф мэллбэрг Sep 12 '16 at 10:24
  • $\begingroup$ No, it can be any number. $\endgroup$ – pi66 Sep 12 '16 at 10:25
  • $\begingroup$ 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 $\endgroup$ – Cato Sep 12 '16 at 10:27
  • 1
    $\begingroup$ @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. $\endgroup$ – астон вілла олоф мэллбэрг Sep 12 '16 at 10:30
  • 3
    $\begingroup$ Surely if colors don't have to be used, then n=2 has no winning strategy $\endgroup$ – Cato Sep 12 '16 at 10:46
0
$\begingroup$

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.

$\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.