|
Here's the original puzzle, and here's the hint. Assign a number, 0 through n-1, to each of the n colors. We also number the gnomes g0, ..., gn-1. Of course we can't tell ahead of time if there will be any correlation between these numbers — so far they are arbitrary. Let's also write ci for the number of the color on gnome gi's head. Then the strategy is: gi guesses color i - Σj≠icj mod n. In other words, gnome gi adds up all the other colors he/she can see (as numbers), and subtracts this sum from his/her number i. Their guess is the resulting number, taken mod n. Why does this work? Let s = Σici be the sum of all hat colors. Then gnome gi guesses i-(s-ci) = ci-s+i mod n. So, when i=s mod n, we have gnome gs guessing cs-s+s=cs (mod n), the correct color! By the same analysis, we can also see that every other gnome gets their color wrong! I sure hope gnome s doesn't screw up. An interesting question from here: is this essentially the only strategy for this puzzle? I showed this puzzle to Manfred Warmuth (who solved it independently) and he conjectures that any solution can only have one gnome at a time guessing correctly. Can you prove it? |