17
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ I would advise that you think about how this puzzle works with a smaller number of hats first (two, then three, then...). $\endgroup$ – Qiaochu Yuan May 26 '12 at 3:59
11
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ I remember hearing advice about giving mathematical talks to the effect that it is not possible to give a talk at too low a level. I think (meaning no disrespect to the OP) that this advice probably applies to math.SE answers as well. $\endgroup$ – Qiaochu Yuan May 26 '12 at 4:41
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ When I was working on this puzzle, I wondered whether I could have two correct guessers at the same time, but your simple probability argument shows it's impossible! $\endgroup$ – Mark Jul 8 '13 at 2:55
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

As written, this riddle has an easier answer. During the night, the prisoners nominate one of their number to give the correct answer. The other 6 number themselves (1-6). Then, they assign values to the colors as follows, dependent upon the number of people who write their answer with either their right or left hand. Prisoner# = 123456 corresponds to: Red= RRRRRR Orange=RRRRRL Yellow...

And so forth. When they are told to write their answers, each simply looks at the hat of the prisoner they've chosen for the correct answer and then begins to write an answer on their own sheet with the correct hand. While the riddle states no communication, the riddle also states they must write their answer and that they can see each other, so I figure this works.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Number the colors and the people 0-6. Each prisoner adds up the colors he sees , they then subtract that from their own number, then add seven until the answer is between 0-6 and that your answer. Now if you'r anything like I was when I herd the answer you probably said "how in the world does that work!!!!" so let me explain how it works:

Now think of it from an outside perspective. All of the hats combined add to sum total number(that no one knows), that total number is equal to a multiple of seven plus a number, smaller than seven. Now each prisoner sees all the hats except his own or the total number minus his hat number. Now one of the prisoners personal number is equal to the unknown number, smaller than seven when that prisoner subtracts what he sees from his number, his number and the smaller number cancel each other out, leaving a negative multiple of seven plus his hat number so when he adds seven until the answer lies between 0-6 he has his number.

In algebraic form it looks like this:

The sum of the hats the prisoner sees $(h)$ is equal to a multiple of seven $(7n)$ plus a number between 0-6 $(s)$ minus his hat number $(x)$.

$h=(7n+(s)-x)$

Now when he subtracts $(h)$ from his personal number $(p)$ which must be between 0-6, he gets:

$(p)-h=(p)-(7n+(s)-x)$

Now you notice that $(s)$ is between 0-6. And the personal numbers $(p)$ of the prisoners range between 0-6, so one of the prisoner has to have a personal number matching $(s)$. So for that particular prisoner we get the following equation:

$(s)-h=(s)-(7n+(s)-x)$ or $(s)-h=-(7n-x)$ or $(s)-h=-7n+x$

So when you add seven $(n)$ times to both sides you get:

$7n+(s)-h=x$

So when he adds the hats he sees and subtracts that from his personal number, than adds seven until the answer lies between 0-6, it will equal $(x)$.

$(p)-h+7n=x$

So the formula works. But remember it only works for one of the prisoners, the one whose personal number matches $(s)$.

p.s. Don't feel bad if you have to read this a few times over. It took me days to understand this puzzle.

| cite | improve this answer | |
$\endgroup$
-2
$\begingroup$

Its easy.

Every prisoner will write the same color, so that one among them will surely answer correct and they will be freed.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.