Monday, November 29, 2021

Four people in a square with hats

I heard of this problem from here, which was also solved in this paper

Four people are trying to escape from a room. Guards have placed a hat on each person’s head, and each hat is one of three colors: red, yellow or blue. The four people are arranged at the vertices of a square, with an obstacle in the middle. Each person can see the hats on the heads of those on adjacent vertices of the square, but they cannot see the hat of the person diagonally across from them. They also do not know the color of the hat on their own head.

Each person must guess the color of the hat on their own head. If at least one person guesses correctly, they can all escape the room together. No communication is allowed once the hats are placed on their heads, but they can coordinate on a strategy beforehand. They also know how they will be arranged in the square.

How can they be guaranteed to escape the room?

==========================================

Below is my solution.

Suppose the four people are $a, x, b,$ and $y$ in circular order. These letters could also refer to the colors of their hats i.e. $0, 1,$ or $2$. Let $\hat{a}$ and $\hat{b}$ be how $a$ and $b$ guess their own hat colors given $(x,y)$, which is depicted below. The first of each pair of bold digits is $\hat{a}$ and the second is $\hat{b}$. 




Now, imagine as $x$ and $y$ we know $(a,b)$. For every possible $(a,b)$, assume the worst that they both got it wrong. For example if $(a,b)=(1,2)$ then assume $(\hat{a},\hat{b})\in\{(0,0),(0,1),(2,0),(2,1)\}$. Clearly, $(\hat{x},\hat{y})=(1,0)$ makes sure at least $x$ or $y$ gets it right. The same conclusion holds for all other possibilities of $(a,b)$, which we now prove below using algebra in $Z_3$ i.e. $-1=2$.

Strategies of $a$ and $b$ above are actually $\hat{a}=x+y$ and $\hat{b}=x-y+1$. From $x$'s and $y$'s perspective, $x=2(\hat{a}+\hat{b}+2)$ and $y=2(\hat{a}-\hat{b}+1)$. So $x$ wants to know $\hat{a}+\hat{b}$ and $y$ wants to know $\hat{a}-\hat{b}$. They can guarantee to get exactly one right: on the $\hat{a}\hat{b}$ plane, the four grid points that differ with $(a,b)$ at both coordinates are vertices of a $1\times 1$ square. Two of them have the same $\hat{a}+\hat{b}$ and the other two have the same $\hat{a}-\hat{b}$. Therefore $x$ and $y$ can guess accordingly and exactly one of them will be right.

2 comments:

Starvind said...

Thanks for the comment on my blog and your solution. I like how you break it down into this simple grid for simple to understand solution.
There is a little handwaving at the end because besides saying it you don't actually prove that this works in all possible cases.

Shen-Fu Tsai said...

You're right, I went through all of them but didn't put it down. Now I add another paragraph to prove it without having to check one by one.