Rainbow Hats Puzzle

Question

Seven prisoners are given the chance to be set free tomorrow. An executioner will put a hat on each prisoner's head. Each hat can be one of the seven colors of the rainbow and the hat colors are assigned completely at the executioner's discretion. Every prisoner can see the hat colors of the other six prisoners, but not his own. They cannot communicate with others in any form, or else they are immediately executed. Then each prisoner writes down his guess of his own hat color. If at least one prisoner correctly guesses the color of his hat, they all will be set free immediately; otherwise they will be executed. They are given the night to come up with a strategy. Is there a strategy that they can guarantee that they will be set free?

So I came across a puzzle today that even after reading the explanation of the solution I do not understand how it mathematically works. I think it's a pretty interesting question so I won't post the answer (I probably can't phrase it right anyways considering I don't understand it). It might be a common math puzzle anyways.

I was hoping someone could give me an intuitive and mathematical explanation as to how to solve this and why it works.

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

Answer 2

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.

Answer 3

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.

Answer 4

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 any given person 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.

Answer 5

First label the different colors by elements of $\mathbb{Z}/7\mathbb{Z}$. Let $c_i\in \mathbb{Z}/7\mathbb{Z}$ denote the color of the $i$th person's hat. Then the total $T = \sum c_i$ is some number that no one prisoner knows. However, $$c_i = T - \sum_{j\neq i} c_j,$$ and the last quantity on the right hand side the $i$th prisoner does know. Suppose that the prisoners arrange that the $i$th prisoner will guess his color is $i - \sum_{j\neq i}c_j$. Then the $T$th prisoner will have correctly guessed his color.