Answer to Puzzle #39: Google Puzzle. 100 Prisoners In a Line Survival Stratergy Executioner

39. An executioner lines up 100 prisoners single file and puts a red or a blue hat on each prisoner's head. Every prisoner can see the hats of the people in front of him in the line - but not his own hat, nor those of anyone behind him. The executioner starts at the end (back) and asks the last prisoner the colour of his hat. He must answer "red" or "blue." If he answers correctly, he is allowed to live. If he gives the wrong answer, he is killed instantly and silently. (While everyone hears the answer, no one knows whether an answer was right.) On the night before the line-up, the prisoners confer on strategy to help them. What should they do?

The person at the back, lets call him person number 1, will agree that if he sees an odd number of red hats he calls out red, if he sees an even number of red hats he calls out blue.
Unfortunately this means he has a 50% chance of survival but it guarantees everyone else's.

They know that the red count for the group 2 to 10 is odd. They use the number of reds that have gone before them to determine if the red count for them to 10 is odd or even. They count the reds in front of them. Comparing the odd or even nature of the two they are able to determine if they are wearing a red hat.
Read full article from Answer to Puzzle #39: Google Puzzle. 100 Prisoners In a Line Survival Stratergy Executioner