My question concerns a variation and a generalization of the following riddle.
The Original Riddle:
A wicked witch kidnaps 2 gnomes. She paralyzes them, and places a hat on each of their heads. Each hat either has the number $1$ or the number $2$ written on it (both hats may have the same number). She then places the gnomes so they face each other (each gnome sees the number on the other gnome's hat). Afterwards, she puts the gnomes in separate rooms, where she undoes the paralysis, and asks each of the gnomes to guess which number is written on their own hat. If at least one of the gnomes guesses right, she'll let them go, otherwise she'll use them to make a gnome-stew. Luckily for the gnomes, they knew about the witch's plan, and they planned ahead. They prepared a strategy that will always guarantee that at least one of them guesses right. What was their strategy?
Solution:
The first gnome (call him gnome $A$), will always select the opposite of what he saw on the second gnome's (call him gnome $B$) hat, while gnome $B$ will always select the same value that he saw on gnome $A$'s hat. Putting this strategy in a truth table shows that it always works:
$$
\begin{array}{c|c|c|c}
\text{Gnome A's Hat} & \text{Gnome B's Hat} & \text{Gnome A's Guess} & \text{Gnome B's Guess} \\
\hline
1 & \color{lime}1 & 2 & \color{lime}{1} \\
\color{lime}1 & 2 & \color{lime}1 & 1 \\
\color{lime}2 & 1 & \color{lime}2 & 2 \\
2 & \color{lime}2 & 1 & \color{lime}2 \\
\end{array}
$$
One can also give a more intuitive explanation for the solution: Gnome $A$ gambles that both gnomes have different valued numbers on their hats, while gnome $B$ gambles that both gnomes have equal values numbers in their hats. Since these are the only possibilities, at least one of them must be correct.
A Variation:
How can the riddle be solved with 3 gnomes, and hats with 3 values ($1$, $2$ and $3$), where each of the gnomes sees the values on the other two gnomes' hats? And is there an intuitive explanation for the solution?
Partial Answer:
Trying out some values I found the following strategy solves the problem for 3 gnomes:
$$
% outer vertical array of arrays
\begin{array}{c}
% inner horizontal array of arrays
\begin{array}{cc}
% inner array of minimum values
\begin{array}{c|c|c}
\text{A's Hat} & \text{B's Hat} & \text{C's Guess} \\
\hline
1 & 1 & 3 \\
1 & 2 & 3 \\
1 & 3 & 1 \\
2 & 1 & 3 \\
2 & 2 & 1 \\
2 & 3 & 2 \\
3 & 1 & 2 \\
3 & 2 & 2 \\
3 & 3 & 1
\end{array}
&
% inner array of maximum values
\begin{array}{c|c|c}
\text{A's Hat} & \text{C's Hat} & \text{B's Guess} \\
\hline
1 & 1 & 2 \\
1 & 2 & 1 \\
1 & 3 & 3 \\
2 & 1 & 1 \\
2 & 2 & 2 \\
2 & 3 & 2 \\
3 & 1 & 1 \\
3 & 2 & 3 \\
3 & 3 & 3
\end{array}
\end{array}
\\ \\
% inner array of delta values
\begin{array}{c|c|c}
\text{B's Hat} & \text{C's Hat} & \text{A's Guess} \\
\hline
1 & 1 & 1 \\
1 & 2 & 2 \\
1 & 3 & 3 \\
2 & 1 & 3 \\
2 & 2 & 1 \\
2 & 3 & 3 \\
3 & 1 & 2 \\
3 & 2 & 1 \\
3 & 3 & 2
\end{array}
\end{array}
$$
Where the third column in each table represents a gnome's guess, given what he sees on the other two gnomes' heads. This strategy always works, as indicated in the truth table below:
$$
\begin{array}{c|c|c|c}
\text{A's Hat} & \text{B's Hat} & \text{C's Hat} & \text{A's Guess} & \text{B's Guess} & \text{C's Guess} \\
\hline
\color{lime}1 & 1 & 1 & \color{lime}1 & 2 & 3 \\
1 & \color{lime}1 & 2 & 2 & \color{lime}1 & 3 \\
1 & 1 & \color{lime}3 & 3 & 3 & \color{lime}3 \\
1 & \color{lime}2 & 1 & 3 & \color{lime}2 & 3 \\
\color{lime}1 & 2 & 2 & \color{lime}1 & 1 & 3 \\
1 & 2 & \color{lime}3 & 3 & 3 & \color{lime}3 \\
1 & 3 & \color{lime}1 & 2 & 2 & \color{lime}1 \\
\color{lime}1 & 3 & 2 & \color{lime}1 & 1 & 1 \\
1 & \color{lime}3 & 3 & 2 & \color{lime}3 & 1 \\
2 & \color{lime}1 & 1 & 1 & \color{lime}1 & 3 \\
\color{lime}2 & 1 & 2 & \color{lime}2 & 2 & 3 \\
2 & 1 & \color{lime}3 & 3 & 2 & \color{lime}3 \\
2 & 2 & \color{lime}1 & 3 & 1 & \color{lime}1 \\
2 & \color{lime}2 & 2 & 1 & \color{lime}2 & 1 \\
2 & \color{lime}2 & 3 & 3 & \color{lime}2 & 1 \\
\color{lime}2 & 3 & 1 & \color{lime}2 & 1 & 2 \\
2 & 3 & \color{lime}2 & 1 & 2 & \color{lime}2 \\
\color{lime}2 & 3 & 3 & \color{lime}2 & 2 & 2 \\
3 & \color{lime}1 & 1 & 1 & \color{lime}1 & 2 \\
3 & 1 & \color{lime}2 & 2 & 3 & \color{lime}2 \\
\color{lime}3 & 1 & 3 & \color{lime}3 & 3 & 2 \\
\color{lime}3 & 2 & 1 & \color{lime}3 & 1 & 2 \\
3 & 2 & \color{lime}2 & 1 & 3 & \color{lime}2 \\
\color{lime}3 & 2 & 3 & \color{lime}3 & 3 & 2 \\
3 & 3 & \color{lime}1 & 2 & 1 & \color{lime}1 \\
3 & \color{lime}3 & 2 & 1 & \color{lime}3 & 1 \\
3 & \color{lime}3 & 3 & 2 & \color{lime}3 & 1 \\
\end{array}
$$
However, I could not find any intuitive explanation for this solution, nor could I prove that this is the only solution. This motivates the first part of my question:
Is there a more intuitive way to look at the given solution for 3 gnomes, and is this the only solution?
The second part regards a generalization of the question:
Is there a general technique that can be used to solve this question for $n$ gnomes and hats with $n$ values?
Best Answer
The sum of the numbers on all of the hats must be congruent to one of $0, 1, 2 \pmod{3}$. If a gnome knows the sum of all the hats $\pmod{3}$ and the sum of the other gnomes' hats $\pmod{3}$, he can subtract to get the number on his hat $\pmod{3}$, and thus, the number on his hat.
Since the gnomes don't know the sum of all the hats $\pmod{3}$, they do the following: gnome $1$ assumes that the sum of the numbers on all the hats is $1 \pmod{3}$, gnome $2$ assumes that the sum of the numbers on all the hats is $2 \pmod{3}$, and gnome $3$ assumes that the sum of the numbers on all the hats is $0 \pmod{3}$. They each calculate the number on their hat based on this assumption. One of these gnomes must have made the right assumption, and thus, guesses their hat correctly.
For $n$ gnomes, the $i$-th gnome assumes the sum of the numbers on all of the hats is $i \pmod{n}$, and guesses his hat accordingly. By the same logic, one of the gnomes guesses correctly.
Note: No matter what the $n$ gnomes' strategy is, the probability of any gnome guessing correctly is still $1/n$. This means that the expected number of gnomes to guess correctly is always $n \cdot 1/n = 1$. Thus, if the gnomes' strategy has a non-zero probability of having two or more gnomes guess correctly, there will also be a non-zero probability of having zero gnomes guess correctly. Therefore, in any strategy that guarantees that at least one gnome guesses correctly, exactly one gnome guesses correctly every time (no more and no less).