Recreational Mathematics – Solving the Rainbow Hats Puzzle

puzzlerecreational-mathematics

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. Is it also possible to give the step by step thought process of constructing this solution?

Best Answer

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.

Related Question