2

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.

pi66
  • 7,164
  • Do we know how many hats of each colour is distributed? – Sarvesh Ravichandran Iyer 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
  • 1
    @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. – Sarvesh Ravichandran Iyer Sep 12 '16 at 10:30
  • For n = 3, then a color is repeated and is either opposite or adjacent to itself, if it is opposite then two people have the same color left and right to them, they can pre-agree to guess the same color depending what color they see (e.g. first in alphabetical order, so red, blue green - they say green if they see tow blues) then one has to be correct - hmm, what if the matching color is adjacent to itself - in that case if each says the color they can't see - I believe it works (but not proved) – Cato Sep 12 '16 at 10:36
  • Not all $n$ colours need to be used, though – pi66 Sep 12 '16 at 10:41
  • why can't they all guess red, then one has to be right - I don't understand? To the guy who says it didn't work, on BRBR - sorry I didn't make it clear, they guess the ALTERNATIVE color to their neighbour, so the second would guess RED - they bet on a change in sequence every time – Cato Sep 12 '16 at 10:41
  • 3
    Surely if colors don't have to be used, then n=2 has no winning strategy – Cato Sep 12 '16 at 10:46
  • @benguin - I think that, but we've been told they don't have to be used – Cato Sep 12 '16 at 10:52
  • @AndrewDeighton Yes, I have understood what you meant. But I have the same problem as you: if they all shout red, at least one of them will win. On the other hand, if there are three colors, then I don't see a strategy at all for this. If all the players decide on a strategy and know what each other are shouting, then they can plan a strategy. – Sarvesh Ravichandran Iyer Sep 12 '16 at 11:29
  • 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{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}

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

     – Ennar Sep 12 '16 at 17:29
  • This should be very brute-forceable with computers, but I'm wondering if there is some elegant argument to do it directly. – Ennar Sep 12 '16 at 17:30

1 Answers1

0

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.

Ennar
  • 23,082