Rainbow Hats Puzzle

Solution 1:

I’m going to assume minimal mathematical background; I apologize if I’ve pitched this way too low. One classic solution works like this.

The prisoners number the colors $0$ through $6$; say red $=0$, orange $=1$, yellow $=2$, and so on through violet $=6$. They also number themselves $0$ through $6$; I’ll simply call them $P_0,P_1,\dots,P_6$. When the hats are put onto their heads, each prisoner performs the following calculation: he adds up the numbers of the colors of the six hats that he can see and subtracts that from his own personal number. For example, if $P_3$ sees hats with colors $0,2,2,5,5$, and $6$, he calculates $$3-(0+2+2+5+5+6)=-17\;.$$ Then he reduces this modulo $7$ to a number in the range from $0$ through $6$. If you’re not familiar with modular arithmetic, that simply means that he adds or subtracts $7$ repeatedly until he gets a number in the desired range. In this case $-17+3\cdot7=4$ is the final result. This is the number corresponding to the color blue, so he writes down blue. The claim is that if every prisoner follows this procedure, one will write down the name of the color of his own hat.

Here’s why it works. Note first what happens if $P_3$’s hat really is blue: then the hat colors add up to $$0+2+2+5+5+6+4=24\;,$$ and when we reduce this modulo $7$ we get $24-3\cdot7=3$, $P_3$’s personal number. The procedure ensures that this happens with each prisoner: he guesses the hat color that would make the sum of all seven hat colors equal (modulo $7$) to his own personal number.

Whatever the actual colors of the hats, their numbers must add up (modulo $7$) to one and only one of the seven numbers $0,1,2,3,4,5$, or $6$. Say they add up to $k$. Then $P_k$ and only $P_k$ writes down the color that makes the total correct. Every other prisoner writes down a color corresponding to one of the other six possible totals. Let’s say that $P_k$ wrote down color number $c_1$, that his own hat’s color is number $c_2$, and that the color numbers of the six hats that he could see added up to $t$. Then on the one hand the procedure ensures that he chose $c_1$ to make $t+c_1$ equal to his own number, $k$, modulo $7$, and on the other hand we know that $k$ is the actual total of the seven color numbers, so $t+c_2$ is equal to $k$ modulo $7$. In short, $t+c_1$ and $t+c_2$ reduce to the same number modulo $7$, so $c_1=c_2$: he wrote down the color of his own hat.

Solution 2:

Instead of colors, pretend the hats are labeled with the elements of $\mathbb{Z}/7$. When strategizing, you agree on the color-to-group-element correspondence, and assign each prisoner a distinct element of $\mathbb{Z}/7$. The prisoner who is assigned $k$ makes the guess which, if true, would make the sum of all the hats be $k$.

One useful route toward solutions to this kind of problem is to use linearity of expectation. In this problem, if the executioner places the hats using independent uniform random distributions, any strategy will lead to each prisoner having a $1/7$ chance of guessing correctly, and so the expected number of correct guesses is always $1$. This means that guaranteeing a correct guess is equivalent to guaranteeing that no two people will ever come up with a correct guess simultaneously, which I think is easier. A lot of other problems of this general type (like the 100 boxes problem) can be understood better in this way.

Solution 3:

There is a similar puzzle here with a pretty well explained solution as well: Prisoner Hat Riddle

Seems important to state any assumptions that may be missed in the problem as well.

Solution 4:

If you number the possible hat colors from 0 to 6, then the sum of the colors the hats actually have is one of 0-6 mod 7. If each of the prisoners make a guess as to what this is, exactly one of them will be right. Now you just have to see that this person will also correctly guess his own hat color, because his own hat color is completely determined given the sum of the hat colors mod 7.

Solution 5:

Here's how I think of it: like other answers, assume the hats are numbered 0 to 6 (instead of colors). If any player knew the sum of all hats mod 7 (including his own) it would be trivial to deduce his hat color. The problem, of course, is that no one knows the sum.

So the strategy is simply to go around the room and say to each player, "You answer assuming the sum is 0", then "You answer assuming the sum is 1", and so forth. The sum has to be between 0 and 6, so someone will get it right.