A riddle with a witch and some gnomes (guessing numbers on hats)

Solution 1:

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).

Solution 2:

For the general question there is a simple method: The $k$th gnome assumes that the sum of the numbers is $k$ modulo $n$, that is, the sum of the numbers minus $k$ is divisible by $n$. With that assumption, he knows what his number is if he assumed correctly. Because one of the gnomes has to have the right assumption, one of them makes the correct guess.