Jean Eugene Roberts wrote:Moonbeam, I for one vote for you revealing the answer, I don't think anyone's going to have luck with this one.
........... and here it is:
The answer is parity bits. Let red = 1 and blue = 0. The prisoner at the rear of the line counts up the number of red hats he sees. If the result is odd he says "red", otherwise "blue". (This is called "even parity". You could do it the other way around; the decision is arbitrary.) If his hat happens to be the opposite colour he will be killed on the spot: a 50% probability if the hats are given out randomly, and the only risk any of them has to take as long as nobody screws up.
Now all the prisoners now know the parity of the remainder of the line - call this the "parity bit". If any prisoner says "red", the others know that the line after that position has opposite parity, and mentally flip the parity bit. This continues all the way down the line, with each prisoner knowing the parity of the remaining part of the line and toggling this value every time someone says "red". When it's his turn, he counts the number of red hats. If his own hat is red then the parity bit and the count will disagree. Therefore, if the parity of the count is the same as the parity bit he says "blue", otherwise "red".
An example. Let's say prisoner #20 says "red", and is freed (or not). Everyone knows that there are an odd number of red hats distributed among the other 19 prisoners. Now prisoner #19 counts the red hats in front of him and comes up with 5. Since he knows the line from himself forward has odd parity and so does the part of the line in front of him, he must have a blue hat; otherwise the count would have been even. (If the parity bit was even and he counted 4 red hats, he would reach the same conclusion.) He says "blue" and is freed. Prisoner #18 counts and sees 4 red hats - an even number, but the parity bit is odd. He knows that his hat must be red, and after he says "red" everyone else knows that the parity bit is now even. And so on.