100 Hats

[milothedog]

Ahhh, the devil is in the detail......BANG.....:ak47:

 

[bellenuit]

It may be just there to put us off, but the fact that we are told they can hear all the responses and all the gunshots when they occur may be significant.

 

[Mr J]

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

No, that strategy would give 75%. 50 can inform the other 50, and those first 50 still have a 50% chance (assuming equal distribution of colours, although from their perspective it's still 50%).

but the fact that we are told they can hear all the responses and all the gunshots when they occur may be significant.

It is if distribution of colours isn't random.

 

[doctorj]

If they don't know what the distribution looks like (i.e. how many red or blue hats in the total population) and all they know is their hat could be red or blue, then its impossible for any information to be passed down the line without somebody behind sacrificing themselves by prearrangement.

 

[bellenuit]

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

How?

 

[bellenuit]

No, that strategy would give 75%. 50 can inform the other 50, and those first 50 still have a 50% chance (assuming equal distribution of colours, although from their perspective it's still 50%).

I don't agree. If the strategy is to say what the colour of the hat of the person in front is, the information is still irrelevant to the person in front. They cannot act on it, as they must say what the colour of the hat of the person in front of them is too. Otherwise they are not following the strategy. So that strategy is still 99 X 50% with 1 X 100%.

Your strategy could be that each even numbered person says what the colour of the hat of the person in front is and each odd numbered person uses that information when they hear it. So the 100th says the colour of the 99th and the 99th repeats that colour and survives (the 100th has just 50% survival chance). The 98th does the same, saying the colour of the 97th and the 97th repeats the colour he has been told and survives (the 98th has a 50% survival chance). That ends up being 75% overall, but is really just the same answer I gave in my initial post with half being informed and surviving and the other half doing the informing and hoping their colour is the same.

 

[doctorj]

I don't agree. If the strategy is to say what the colour of the hat of the person in front is, the information is still irrelevant to the person in front. They cannot act on it, as they must say what the colour of the hat of the person in front of them is too. Otherwise they are not following the strategy. So that strategy is still 99 X 50% with 1 X 100%.

I don't think you've read it right. The way I see it, he's suggesting everyone split into pairs. The first in the pair will say the colour of their partner's hat. Their partner is guaranteed survival (as they use that information when it's their turn) and the first has a 50/50 chance of survival if they're fortunate enough to be wearing the same colour hat.

 

[Wysiwyg]

Before venturing down this strategic path, is there a good chance of it working?

The last person counts how many of the even numbers in line have predominantly red or blue hats. Out of the even numbers if there are more than 25 red hats they will call red and if more than 25 blue hats they will call blue. So then it is known that the evens in line have more red or blue. The first person then calls the predominant colour and lives or dies. If they live means there are at least 25 or more (add colour here) hats with the evens.

The second last person (who is an odd) counts how many of the odd numbers in line have predominantly red or blue hats. Out of the odd numbers if there are more than 25 red hats they will call red and if more than 25 blue hats they will call blue. So then it is known that the odds in line have more red or blue. The second last person then calls the predominant colour in the odds and lives or dies. If they live means there are at least 25 or more (add colour here) hats with the odds.

So what is now known by everyone is the predominant colour of hat in both odd and even numbers.

I will add more after further contemplation ....

 

[mazzatelli]

How?

I prepped for this question for interviews few years ago, except i got 3 hat colors instead. It can be the first or last guy that gets popped depending on assignment of variables &/or wording of the question

Try reduce the working solution to 2-10 people.

WYSIWYG is on the right track by assigning odd and even numbers to the hat colour.
The first one will call parity, with the next in line deducing the difference between their count and the previous prisoner to obtain their hat colour.

 

[Timmy]

Wow
A interview question for entry level quant positions

Which helps explain why I am not a quant (of any level ).

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

The blind one would be teaching the others EW, right? :hide:

 

[Taltan]

Took a while but than I think Mazatelli gave it away. The 100th person can see 99 hats so he yells out whatever colour there is of odd hats (there will be one colour as there are 99 hats in front of him). 99th than sees hats 1-98 and based on what 100 said and whether he lived he knows his colour hat because of whether blue/red is even or odd numbered.

e.g. if 100th shouted red (odd number) and 99th only counts an even number of reds than he must be red to make red an odd number. If he counts an odd number he must be blue. 98th knowing that red was originally odd can than also live by tallying up what he sees in front of him and whether 99 has been shot or not.

As long as everyone keeps this in their head whilst concurrently tallying who has been shot and when, they will live. Obvioulsy whoever is 100th only has a 50% chance.

 

[Mr J]

So there is a 50% distribution of reds and blues? That's a vital clue that's missing from the question.

 

[Wysiwyg]

If they live means there are at least 25 or more (add colour here) hats with the evens.

A correction here is the fact that if the last person lives then the number of red or blue hats in even is at least 26. The last person knows there are more than 25 of one colour in evens but the other evens don't know how many, but if the last person lives then there is at least 26 evens with that colour.

The original (at least) 25 plus the last person who lived = 26. That is the minimum number of one colour in the evens out of 50.

 

[mazzatelli]

The blind one would be teaching the others EW, right? :hide:

Shhh...you're definitely a quant :. Taltan

So there is a 50% distribution of reds and blues? That's a vital clue that's missing from the question.

The question is solved independent of any distribution

Bellnuit - assigning 0 = red and 1 = blue is an alternative, w.r.t binary is not necessary

 

[Wysiwyg]

So there is a 50% distribution of reds and blues? That's a vital clue that's missing from the question.

How does it matter if the number of hat colours are the same?

 

[bellenuit]

The best strategy I can come up with gets me to 96.5% survival rate on average. It guarantees at least 93 will survive and requires the first seven to be altruistic and possibly say a colour that they know to be wrong in their own case.

The last person in the line can count the number of reds and can know there will be a maximum of 99 reds (he cannot see his own). 99 expressed in binary is 1100011. So it takes 7 binary digits to express the maximum possible number of reds that can be seen by the last person.

Their strategy is that the last 7 in the line will express the number of reds seen by the last person as a binary number with red denoting one. They express it from left to right (the last person's answer expressing the most significant digit of the number of reds in binary).

So the last in line counts the number of reds he can see. If equal to or more than 64 he says Red (=binary 1xxxxxx). If less than 64, he says blue (binary 0xxxxxx). The 2nd in line counts the number of reds he can see. If he heard the shotgun after the last in line answered he adds 1 to his answer if the last in line answered blue. If he didn't hear the shotgun he adds 1 to his answer if the last in line answered red. Otherwise he adds nothing. The resultant answer is now the same as the count made by the last in line. He then says Red if this number expressed as a binary number requires a 1 in the 2nd position of the 7 digit binary number. This gets repeated for the 3rd through 7th last person in the line, with the number of reds they see in front of them incremented by one for each previous respondent who got shot for answering blue or didn't get shot for answering red. Each answers red if the resultant number requires a 1 in the digit position they represent when expressed in binary.

The 8th last person then has enough information to compute what his colour is. By the binary number expressed through reds being 1 and blue 0, he knows the total number of reds seen by the last in line. From the answers given by the previous 6 (last in line is irrelevant to this part of his computation) and whether they got shot or not after each answer, he can compute the number of red hats worn by the 6 people before him. Subtracting this number from the the total seen by the last in line gives the total of reds left including his own hat. He then counts the number of reds he sees and if it is the same as that number, he says blue. If one less, he says red. Each subsequent person who will have done the same calculation as the 8th did and arrived at the same total just deducts 1 from that total for each answer red that they subsequently hear. If they see the same number of reds in front of them as the running total, they say blue, otherwise if one less, they say red.

Since the last 7 in the line must answer according to the binary number they are expressing, they should each have a 50% chance of being right. The remaining 93 will be right 100% of the time.

This brings the overall survival rate up to 96.5% on average

 

[bellenuit]

Took a while but than I think Mazatelli gave it away. The 100th person can see 99 hats so he yells out whatever colour there is of odd hats (there will be one colour as there are 99 hats in front of him). 99th than sees hats 1-98 and based on what 100 said and whether he lived he knows his colour hat because of whether blue/red is even or odd numbered.

e.g. if 100th shouted red (odd number) and 99th only counts an even number of reds than he must be red to make red an odd number. If he counts an odd number he must be blue. 98th knowing that red was originally odd can than also live by tallying up what he sees in front of him and whether 99 has been shot or not.

As long as everyone keeps this in their head whilst concurrently tallying who has been shot and when, they will live. Obvioulsy whoever is 100th only has a 50% chance.

Yes, that seems correct. While I was describing what I thought was the best answer, a much more elegant and better solution was posted. Good work. I'll check on the site to see what they have.

 

[bellenuit]

Yes, that seems correct. While I was describing what I thought was the best answer, a much more elegant and better solution was posted. Good work. I'll check on the site to see what they have.

That's the solution on the web site too. The first answers Red if the number of Red hats is odd and the rest have sufficient information to work out their own colour by whether they see an odd or even number of reds (and adjusting the odd/even count for each previous answer given).

For those who want to torture your mind a bit more, from the same website:

The Puzzle of the Three Hats

Three wise men are told to stand in a straight line, one in front of the other. A hat is put on each of their heads. They are told that each of these hats was selected from a group of five hats: two black hats and three white hats. The first man, standing at the front of the line, can’t see either of the men behind him or their hats. The second man, in the middle, can see only the first man and his hat. The last man, at the rear, can see both other men and their hats.

None of the men can see the hat on his own head. They are asked to deduce its color. Some time goes by as the wise men ponder the puzzle in silence. Finally the first one, at the front of the line, makes an announcement: “My hat is white.”

He is correct. How did he come to this conclusion?

 

[doctorj]

He is correct. How did he come to this conclusion?

I'll start off... probably more to it, but I'll think as I type. We already know there's a 60% chance that the first guy's hat will be white.

The guy at the back would immediately know his hat was white if the both in front were black. Given he didn't call out straight away, the two in front must be BW or WB. That information gives the guy in front a 67% chance his hat is white.

 

[doctorj]

That information gives the guy in front a 67% chance his hat is white.

Actually... if the guy in middle realises that the guy at the back hasn't said anything, it must be BW or WB. If he sees the hat in front is B, he would know his must be W, but because he didn't call out, it leaves two possibilities - WW or WB. Which tells the guy in front his must be white.

How can the poor guy in the middle guess correctly?