Puzzle : The Stark Raving Mad King

A stark raving mad king tells his 100 wisest men he is about to line them up and place either a red or blue hat on each head. Once lined up, they must not communicate amongst themselves nor attempt to look behind them nor remove their own hat.

The king tells the wise men that they will be able to see all the hats in front of them. They will not be able to see the color of their own hat or the hats behind them, although they will be able to hear the answers from all those behind them.

The king will then start with the wise man in the back and ask "what color is your hat?" The wise man will only be allowed to answer "red" or "blue," nothing more. If the answer is incorrect then the wise man will be silently killed. If the answer is correct then the wise man may live but must remain absolutely silent.

The king will then move on to the next wise man and repeat the question.

Before they are lined up, the king makes it clear that if anyone breaks the rules then all the wise men will die. The king listens in while the wise men consult each other to make sure they don't devise a plan to communicate anything more than their guess of red or blue.

What is the maximum number of men they can be guaranteed to save?

.

;

;

;

;

;

;

;

;

;

;

;

;

;

;

;

;

;

;

HINT :

To solve this problem, you need to presume that each wise man can count the total number of red hats in front of them without error, that all the wise men have great attention to detail and that all the wise men care about the greater good. The first wise man will give an answer which may result in his death, but will allow each subsequent wise man to give a correct answer.

source : http://www.folj.com/puzzles/very-difficult-analytical-puzzles.htm

Solution below..

Answer: 99.

Solution:

You can save about 50% by having everyone guess.

You can save 50% or more if every even person agrees to call out the color of the hat in front of them. That way the person in front knows what color their hat is, and if the person behind also has the same colored hat then both will survive.

So how can 99 people be saved? The first wise man counts all the red hats he can see (all but his own) and then answers "blue" if the number is odd or "red" if the number is even. Each subsequent wise man should be able to then guess correctly the color of their hat, based on the number of red hats in front of them, and all the answers from all the wise men behind them.

For example if the first wise man answers "blue" he indicates to everyone that he sees an odd number of red hats. If the second wise man then sees an odd number of red hats, he can deduce that he has a blue hat on. He will then state "blue" so that everyone knows he still saw an odd number of hats. If the third wise man then sees an even number of red hats then he must be wearing a red hat. He will then state "red" so that everyone knows he saw an even number of hats. Etc..

This does not presume an even number of red and blue hats. There could be 94 blue hats and then 6 red ones. All the hats could be red.