100 Hat puzzle.

[Arje]

I'm engaged in a ridiculous facebook war right now over the following puzzle. It's obvious to me that I'm not only right, I'm mega right. But this has not stopped the post in question from having like 40 responses, and me being the only one with logic powers bold enough to see the obvious solution in front of me.


As an exercise, I wanted to see how well you guys would succeed or fail at said puzzle.

This is a slightly different wording that the one being discussed on facebook, but the solution, problem ,and provisos are all the same.'

One hundred persons will be lined up single file, facing north. Each person will be assigned either a red hat or a blue hat. No one can see the color of his or her own hat. However, each person is able to see the color of the hat worn by every person in front of him or her. That is, for example, the last person in line can see the color of the hat on 99 persons in front of him or her; and the first person, who is at the front of the line, cannot see the color of any hat.

Beginning with the last person in line, and then moving to the 99th person, the 98th, etc., each will be asked to name the color of his or her own hat. If the color is correctly named, the person lives; if incorrectly named, the person is shot dead on the spot. Everyone in line is able to hear every response as well as hear the gunshot; also, everyone in line is able to remember all that needs to be remembered and is able to compute all that needs to be computed.

Before being lined up, the 100 persons are allowed to discuss strategy, with an eye toward developing a plan that will allow as many of them as possible to name the correct color of his or her own hat (and thus survive). They know all of the preceding information in this problem. Once lined up, each person is allowed only to say “Red” or “Blue” when his or her turn arrives, beginning with the last person in line.

Your assignment: Develop a plan that allows as many people as possible to live. (Do not waste time attempting to evade the stated bounds of the problem — there’s no trick to the answer.)

There are 2 solutions. One is correct, the other is technically correct, but in violation of the spirit of the rules.

No googling. =)

[Mckma]

I've done the one with like 3 guys and a wall, but I always have the hardest time remembering how to do it...

[Salkovich]

I'm pretty sure this one ends with sacrificing the last dude.

[clockworkjoe]

Obvious thing I thought of without spending any time on it.

[spoiler]First person says the color of the hat directly in front of him. Second person says that color. Rinse and repeat. Minimum of 50 people live. [/spoiler]

Main problem is that there's no information on the probability of hat color distribution. It could be 99 red and 1 blue or 74/26 or whatever. No way of knowing. Second problem is there's no way for people to move information forward easily. I suppose a code could be developed to pass info on so that the first 10 or so people basically answer yes/no questions about the hat distribution: Red - yes blue no.

1. Are the number of red and blue hats even?
2. If hats even - are they in an red/blue pattern? If hats not even is red greater than blue?

and so on - until a pattern is established by the questions then everyone answers according to their best knowledge

[Arje]

Obvious thing I thought of without spending any time on it.

[spoiler]First person says the color of the hat directly in front of him. Second person says that color. Rinse and repeat. Minimum of 50 people live. [/spoiler]

Main problem is that there's no information on the probability of hat color distribution. It could be 99 red and 1 blue or 74/26 or whatever. No way of knowing. Second problem is there's no way for people to move information forward easily. I suppose a code could be developed to pass info on so that the first 10 or so people basically answer yes/no questions about the hat distribution: Red - yes blue no.

1. Are the number of red and blue hats even?
2. If hats even - are they in an red/blue pattern? If hats not even is red greater than blue?

and so on - until a pattern is established by the questions then everyone answers according to their best knowledge

This is a very good first guess.

It is also wrong.

The rest of your questions are immaterial to the problem. They would make it simpler, but are not necessary.

In fact that is a solution that allows 99 of the people to live, and the first person asked (the 100th person in line) has a tossup.

[Ezechiel357]

[spoiler]The strategy is the following: the first person to talk has to count the blue hats in front of him. He will say "blue" if the number is even or "red" if the number is odd. He has 50/50 chance of dying, no way to have a higher chance of saving him.
The second one will count the number of blue hats in front of him, if the number is even and the first one said "blue" - meaning "even", he knows he is wearing a red hat (since the number of blue hat did not change) so he just has to say red. If the number he is counting is odd and the first one said "blue", then he is wearing a blue hat (since the number change from even to odd, he must be wearing a blue hat).
Similar reasoning applies in case the first one said "red".
After that, every guy  has to keep track of the number or red/blue to be able to call the hat's colour he is wearing.
[/spoiler]

With this strategy, you will save 99 guys for sure and you have a 50/50 chance to save the first guy. This strategy works no matter the number of hats, no matter how many guys in row (as long as you can count them all ).

[Arje]

Ding ding.


Winnah Winnah chicken dinner.

[Arje]

Also, Alexander. Deal may or may not be null and void. There is a second solution, although it is cheating.

[beowuuf]

Oooh, very cool solution.

The 'cheating' solution I thought of would be :
[spoiler]You shout the colour of your hat if it is also the colour in front of you, you say it quietly if not. Obviously, this violates the spirit by introducing a secondary axis to communicate through.[/spoiler]

[Zeriken]

Best solution has been posted, and I wouldn't have thought of it. I'd go full on cheating in the spirit, but not in the actuality:

100 pokes 99 once for blue hat, or twice for red, then declares his own color. Etc. etc. Touching wasn't discussed in the rules. 100 has a 50/50 chance.