100 Hats - Aussie Stock Forums

1. ## 100 Hats

This looks like another interesting math problem. I've been sent the link to the problem on the web, which also has the solution, which I haven't read yet. Let's see if we can figure it out here ourselves, without recourse to searching for it on the web. I'm out for a few hours, but will look at it later.

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.)

One additional piece of information from the web site that was added after some initial responses were given is that "red" or "blue" cannot be said in such a way that the manner in which it is said (speed, pitch) is used to convey additional information.

2. ## Re: 100 Hats

This is just a a partially thought through strategy to get the ball rolling. I'll put more effort in later. This should get on average a 75% survival rate if my math is correct.

The last in line should say the colour of the hat worn by the first in line. The 2nd last in line should say the colour of the hat worn by the 2nd in line etc. right up to the 50th last in line (=51st in line) saying the colour of the hat worn by the person immediately in front of him or her, who is the 50th in line.

Now, up until that point, each person has a 50% chance that the colour they stated is also the colour of their own hat. But the first 50 in line will know the colour of their hats when their turn comes, so they have 100% survival chance. This equates to a 75% survival rate overall on average

3. ## Re: 100 Hats

Is there 50 of each colour hat to start with? Or any such distribution?

4. ## Re: 100 Hats

I'm guessing that was a stupid question, right?

OK - if they meet beforehand and agree to say the colour of the hat of the person immediately in front, then 99 will survive. The last person in line (i.e. the first to speak) has only a 50-50 chance of survival though.

5. ## Re: 100 Hats

Originally Posted by Timmy
I'm guessing that was a stupid question, right?

OK - if they meet beforehand and agree to say the colour of the hat of the person immediately in front, then 99 will survive. The last person in line (i.e. the first to speak) has only a 50-50 chance of survival though.
If the hat in front is not the colour of your hat would you sacrifice your life for them?

6. ## Re: 100 Hats

Originally Posted by Wysiwyg
If the hat in front is not the colour of your hat would you sacrifice your life for them?
LOL!

If my solution is right then I think we should all meet up on the weekend and do it. My prize is picking the first person to speak (and I'm bringing a green hat for that special someone )

7. ## Re: 100 Hats

Originally Posted by Timmy
I'm guessing that was a stupid question, right?

OK - if they meet beforehand and agree to say the colour of the hat of the person immediately in front, then 99 will survive. The last person in line (i.e. the first to speak) has only a 50-50 chance of survival though.
Doesn't that mean you are assigning your strategy to randomness?

100 will guess their colour and might die. Assuming he/she dies, no new information is passed into the chain for the 99 to refine their guess and has the same odds as the 100 when requested for their guess.

I like the answer provided by bellenuit, 50% noble

8. ## Re: 100 Hats

Originally Posted by sinner
Doesn't that mean you are assigning your strategy to randomness?

100 will guess their colour and might die. Assuming he/she dies, no new information is passed into the chain for the 99 to refine their guess and has the same odds as the 100 when requested for their guess.

I like the answer provided by bellenuit, 50% noble
I dunno? Still thinking about other possible solutions too.

And I think my stupid question may need answering before I try for any other solutions.

9. ## Re: 100 Hats

Originally Posted by Timmy
Is there 50 of each colour hat to start with? Or any such distribution?

There is no hint as to the distribution of the hat colours to begin with. Could be 99 reds for the first 99 person, and blue for the 100th.... just so that he will guess blue and face a certain death.

10. ## Re: 100 Hats

Originally Posted by skc
There is no hint as to the distribution of the hat colours to begin with.
Yes, that's right, no hint at all. I don't know if it is important/relevant?

11. ## Re: 100 Hats

I think 75% is about right. If the second 50 point out the correct colour to the first 50, the first 50 live, and the second 50 have a 50% chance. This assumes no mistakes are made!

12. ## Re: 100 Hats

When they are discussing stratergy, count how many red and blue hats. The person at the back has a 50% chance of living. Everyone else has a 100% chance as they simply have to count the hats that are left in front of them and find the missing number.

13. ## Re: 100 Hats

Originally Posted by sammy84
When they are discussing stratergy, count how many red and blue hats. The person at the back has a 50% chance of living. Everyone else has a 100% chance as they simply have to count the hats that are left in front of them and find the missing number.
Everyone else only has a 100% chance as long as the first guy guesses correctly. Like Timmy, you are assigning your strategy to randomness. 100 could guess wrong and then 99 would need to guess and if no new information is passed into the chain then everyone can die. You need to feed information into the chain as quickly as possible.

14. ## Re: 100 Hats

Originally Posted by Timmy
Is there 50 of each colour hat to start with? Or any such distribution?
Doesn't say. Just the information I entered above.

15. ## Re: 100 Hats

Originally Posted by sinner
Everyone else only has a 100% chance as long as the first guy guesses correctly. Like Timmy, you are assigning your strategy to randomness. 100 could guess wrong and then 99 would need to guess and if no new information is passed into the chain then everyone can die. You need to feed information into the chain as quickly as possible.
Do people ahead in the line know if the person behind them is shot? If the second to last person hears the guess and then the gun shot (or not) s/he knows the colour of the hat behind and all those in front.

16. ## Re: 100 Hats

Wow
A interview question for entry level quant positions

You can save 99 people
The first one has a 50/50 chance

There's another version of this question with 3 men: one blind

17. ## Re: 100 Hats

Originally Posted by bellenuit
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).
I may be missing something here ...but in all this strategy talk, why can't they just turn to each other and say, "you are wearing a red hat", "oh really, thanks, you are wearing a blue hat"

18. ## Re: 100 Hats

Originally Posted by sammy84
When they are discussing stratergy, count how many red and blue hats. The person at the back has a 50% chance of living. Everyone else has a 100% chance as they simply have to count the hats that are left in front of them and find the missing number.
Interesting, but it assumes they are able to see how many of each colour are there. The sequence from the question is......

One hundred persons will be lined up single file, facing north. Each person will be assigned either a red hat or a blue hat......

Before being lined up, the 100 persons are allowed to discuss strategy,

I would assume that they cannot tell how many of each colour are there when discussing strategy, as they are lined up before they are allocated hats going by the sequence above and discussion is before they are lined up.

Even if they did know, wouldn't everyone be able to work it out including the first? He would just subtract what he sees from the total of each.

19. ## Re: 100 Hats

Originally Posted by milothedog
I may be missing something here ...but in all this strategy talk, why can't they just turn to each other and say, "you are wearing a red hat", "oh really, thanks, you are wearing a blue hat"
As I understand it, they are not wearing the hats at the time of discussion, and that 99 can't be saved.

20. ## Re: 100 Hats

Originally Posted by Timmy
OK - if they meet beforehand and agree to say the colour of the hat of the person immediately in front, then 99 will survive. The last person in line (i.e. the first to speak) has only a 50-50 chance of survival though.
Nope. That was my first thought too. But you are forgetting that they need to say what their hat colour is to survive. Using a strategy of letting the next person know what the next person's hat colour is means that you are ignoring the information passed to you by the previous person. Only the last person would be able to say what their own colour is. I would assume that that strategy only brings the total slightly above 50% (average of 99 at 50% and 1 at 100%).

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•
Aussie Stock Forums