Idealogian

I've gotten some requests for the explanation, so here goes. Stop me if I'm going too fast.

First, a word of explanation. "mod" is a mathematical term that means, "divided by, only forget the actual answer and just give me the remainder." It is represented by the '%' symbol. Thus, 13 % 5 = 3. It is often used when a number that can be of any size must be forced into a particular range (e.g., we want to somehow represent 3428 as being between in a range of 50, we'd say that 3428 % 50 = 28). By "mod"ding numbers, you can sort of count in a loop - 47, 48, 49, but then 50 % 50 is 0, so we go from 49 to 0, 1, 2, etc. Similarly in reverse - 5, 4, 3, 2, 1, 0, 49, 48, 47.

Now, on to the answer. First an explanation, then an example.

In the answer I gave, each person uses an overall piece of information - which color hat was represented by an odd number - together with what he knows about all the hats aside from his, to figure out the color of his own hat. vvilly's suggestion works on a similar theme, only with a different piece of overall information. If each color is said to correspond to a particular unique number, then the colors of all the hats can be given as the sum of their numbers. Each person can then know the sum of all the hats, subtract from that the sum of all the hats that aren't his, and thereby arrive at the number/color of the hat that is his.

The only catch is that by summing up all the numbers, the total may be way outside the range of "allowable" values. Therefore, mod must be used to force the total back into the correct range.

If this isn't clear yet, an example will hopefully help.

Let's make it easy (relatively). Six people, four colors - red, green, blue and yellow. The prisoners arbitrarily assign the numbers: R = 0, G = 1, B = 2 and Y = 3. They arrive in the morning, and have placed upon their heads the colors: G Y R B Y B.

The last person (wearing blue) looks ahead and sees five hats, and translates them into numbers: 1(G) 3(Y) 0(R) 2(B) 3(Y). This adds up to 9. There's no color that corresponds to 9, though, so he takes 9 % 4 = 1, to force himself back into the given range. (9 is the sum; 4 is the number of colors.) He therefore announces, "Green," and has a one in four chance of surviving himself.

The second to last person - #5 - looks at the four hats ahead of him and sees: 1 3 0 2. This adds up to 6, and 6 % 4 = 2. In other words, #5 seems a total whose remainder when divided by 4 is 2, but he knows that the guy behind him saw a total whose remainder when devided by 4 is 1. In other words, he knows that the color of his own hat is raising the sum by some number that changes the remainder from 2 to 1. The only possible number (in the 0-3 range) that could do that is 3. (Counting 3 up from 2 - 3,0,1.) Thus, number 5 knows that his own hat must be a 3 - yellow - and announces that to get himself freed.

#4 is next. He knows that #6 saw a remainder of 1 (green), and that #5 just determined himself to be a remainder of 3 (yellow), which means that #5 must have seen a remainder of 2 himself. #4 sees 1 3 0 - a total of 4, and 4 % 4 = 0. If he sees a remainder of 0, but knows the guy behind him saw a remainder of 2, that means he himself must be a 2 - blue. He announces that and goes free.

Now comes #3. He knows that #6 saw in #1-#5 a total whose remainder was 1. He knows that the two behind him (#4 & #5) him were yellow and blue - 3 + 2 - which means they were contributing 5 to the total that
#6 saw.
A remainder of 1 minus 5 leaves a remainder of 0 (counting 5 down from 1 - 0,3,2,1,0). Which means that in #1-#3, the sum is some number whose remainder is 0 (which fits with what we said #4 saw).
#3 sees in front of him: 1 3 - a sum of 4. 4 % 4 = 0. If the remainder of #1 & #2 is the same as that for #1, #2 and #3 together, that must mean that #3 doesn't change the remainder at all, which means that #3 must be a 0 - red.

Almost there. #2 knows that #6 saw in #1-#5 a total whose remainder was 1. He knows the three behind him where yellow, blue and red - 3 + 2 + 0 = 5. Again, a remainder of 1 minus the 5 contributed by #3-#5 leaves a remainder of 0, so he knows the remainder of the remaining people - #1 and #2 - is 0. In front of him, he sees one hat: 1. In order to get from a remainder of 1 to a remainder of 0, his hat must be adding 3 (2,3,0). Therefore, he must be yellow. He announces that and goes free.

And finally, #1 knows that #6 saw in #1-#5 a total whose remainder was 1. He knows that the four behind him were yellow, blue, red and yellow - 3 + 2 + 0 + 3 = 8. Which means they were contributing 8 to the total that #6 saw. A number with a remainder of 1 minus 8 would be 1 (starting from 1 counting down 8 - 0,3,2,1,0,3,2,1). Thus, he knows that the remaining person - himself - must have a remainder of 1. He therefore announces himself to be green and goes free.

Hope this helps. If it's still not clear, just ask.