Develop a plan that allows as many people as possible to live.

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.

Develop a plan that allows as many people as possible to live.

4 comments:

Abhishek Kumar said...

99 people out of 100 will live.
The plan will be something like this :
1.If the 100 person see odd no. of red hats he will say red.
2.otherwise he will say blue.

Now suppose 100 says red => that means there are odd red hats in front of him .
Now 99'th can see the hats on other 98 people , so he knows that including himself there are odd number of red hats so if he sees even no. of red hats he knows that his hat is red otherwise his hat is of blue color.

From now on every body will keep track of the color --> Suppose 99 said red that means 98 will come to know that now even no. of red hats are remaining (all others also know this same thing).So he will decide accordingly.

Admaya said...

We would like to inform you about the launch our new Admaya Indian advertising network text and banner ads available on pay per click basis.

www.admaya.in

JohnFlux said...

Abhishek, wouldn't that be an average of 99.5 people that live then?

Didierdrogba said...

Hi

I like this post:

You create good material for community.

Please keep posting.

Let me introduce other material that may be good for net community.

Source: Yahoo interview questions

Best rgs
Peter

Your Title

My Blog List