Hats on a death row!! One of my favorites puzzles!

[roolstar]

If you don't already know this one, I'm sure you will find it very interesting and fun to solve! And if you do find the answer (or already know it) please put it under a spoiler tab so that you don't take the fun from the rest of the intelligent people in this forum....

Here we go....

You are one of 20 prisoners on death row with the execution date set for tomorrow.

Your king is a ruthless man who likes to toy with his people's miseries. He comes to your cell today and tells you:

“I’m gonna give you prisoners a chance to go free tomorrow. You will all stand in a row (queue) before the executioner and we will put a hat on your head, either a red or a black one. Of course you will not be able to see the color of your own hat; you will only be able to see the prisoners in front of you with their hats on; you will not be allowed to look back or communicate together in any way (talking, touching.....)

(The prisoner in the back will be able to see the 19 prisoners in front of him

The one in front of him will be able to see 18…)

Starting with the last person in the row, the one who can see everybody in front of him, he will be asked a simple question: WHAT IS THE COLOR OF YOUR HAT?

He will be only allowed to answer “BLACK” or “RED”. If he says anything else you will ALL be executed immediately.

If he guesses the right color of the hat on his head he is set free, otherwise he is put to death. And we move on to the one in front of him and ask him the same question and so on…

Well, good luck tomorrow, HA HA HA HA HA HA!”

Now since you all can communicate freely during the night, can you find a way to guarantee the freedom of some prisoners tomorrow? How many?

Remark of Site Admin:

Note that solution for this puzzle is already given in the following post by bonanova.

[Guest]

Does this mean we are assuming the colored hats are equal in quanity.. 10 red hats and 10 black hats???

[bonanova]

Does this mean we are assuming the colored hats are equal in quanity.. 10 red hats and 10 black hats???

There is no such assumption. Could be all black for example.

[Guest]

Your reasoning is correct. It was stated that a correct strategy would guarantee the safety of 19 of the 20, with the 20th (first to guess) having a 50% chance.

With no other information present, I don't see how this is solvable. What strategy would allow you to say the word "red" or the word "black" and tell nineteen people which of two colors each was wearing? I believe it is impossible; you cannot convey that much information in a simple binary choice.

I can see a method to save at least 13 of the 20 people:

The first person looks at the two hats in front of him. If the hats are the same color, he says "red". If they are different colors, he says "black". This guarantees the safety of the two people in front of him, since the next guy in line will be able to figure out his own color. Starting with the first, every third person uses this code. There will be two people left at the end; the second-to-last guesses the color of the last person's hat, so the last person will also be assured of survival. If done correctly, only seven of the twenty will be in danger of death. A mathematically average run would see 3 or 4 executions among the 20, a 15-20% mortality rate -- not bad odds for 20 condemned prisoners. At worst, 13 survive, for a 65% minimum survival rate. And there is one chance in 128 that all will survive.

that is a good solution but maybe the king wont put the hat on the next person until you have already given your answer and he could also switch hats between red and black so that they cant just have the first peson say black and if he dies everyone says red

[bonanova]

that is a good solution but maybe the king wont put the hat on the next person until you have already given your answer and he could also switch hats between red and black so that they cant just have the first peson say black and if he dies everyone says red

Hi gelfish and welcome to the Den.

The puzzle states that thin events you mention won't happen.

All the hats are in place before the prisoners speak, and it's implied they won't change afterward.

[Guest]

Hi,

I have another solution to this problem.

20th person should tell the color of hat on the head of 19th person in row with loud voice.(e.g. Red).Now in this way 19th person come to knows that he is wearing Red hat and he has to say "Red" in any case.Now he need to look at the color of hat on the head of 18th person.

1. If 18th person is also wearing Red hat then 19th person will say "Red" again with loud voice.

2. If 18th person is wearing Black hat then 19th person will say "Red" with slow (less loud) voice.

In this way 18th person will come to know whether he is wearing "Red" or "Black" hat and this will keep on going till last person in row.

In this way they can surely save 19 lives and also 20th person life if he is also wearing the same color hat as 19th person.

[Guest]

The first prisoner agrees to answer the color of the hat of the next prisoner. The next prisoner in turn "guesses" with 100% certainty the color of his hat. If every other prisoner acts the like, that is every second prisoner says the color of the prisoners hat in front of him 10 of the prisoners can be saved for certain. furthermore the rest of the prisoners who state the color of the hat in front of them will have a 50% shot of surviving themselves

[Guest]

each prisoner partners up with another so 1 and 2, 3 and 4, etc.

[bonanova]

each prisoner partners up with another so 1 and 2, 3 and 4, etc.

And ... ?

Question is how many can you guarantee will be freed?

[Guest]

Ok, I think I got it.

I'm a newbie so bear with me.

The first prisoner has to choose between Red or Black.

He should say Red if the two prisoners in front of him are wearing the same color hat, Black if they are different.

That guy has a 50/50 shot but now everyone knows what hat they have on based on what the guys before them said.

If everyone pays attention to the progression and no one messes up the logic this should work.

Edited January 31, 2009 by BDidit

[bonanova]

Ok, I think I got it.

I'm a newbie so bear with me.

The first prisoner has to choose between Red or Black.

He should say Red if the two prisoners in front of him are wearing the same color hat, Black if they are different.

That guy has a 50/50 shot but now everyone knows what hat they have on based on what the guys before them said.

If everyone pays attention to the progression and no one messes up the logic this should work.

But can they keep the progression going?

A prisoner can signal to others what he sees, or he can call the color of his own hat.

But he needs to do both.

[Guest]

I don't know for sure if they are close enough for this, but let's say they decided beforehand that the black hat will be represented by the left leg, and the red hat by the right leg. Right before the king arrives to question them, all they have to do is kick the prisoner in front of them on the leg that is equal to the hat color. The only prisoner without a 100% chance of getting out is the last prisoner in the line.

[Guest]

Heres a solution:

The first to go will say the color of the person in front of him

then the second person will know his color

he will wait a few seconds if the person in front of him has a different color hat and then say his color

if it is the same color he will say it immediately

then the third person knows his color and the cycle continues

[bonanova]

The riddle asks that no information be passed other than the word BLACK or RED.

It's fun to think of ways to pass other information, but all that does is get everyone killed.

[Guest]

Your hint about 2 possibilities made it suddenly clear. Try this:

The first speaker counts the number of red vs black hats on the remaining 19. Whichever there are more of, is the color he says his is. Since there are 19 remaining, there must be more of one color or the other.

2nd speaker also counts the number of red vs black on the remaining 18. Based on the first person's pronouncement, he knows which color there should be more of on the 18 plus his own. He compares what he sees and knows which color his own hat must be.

3rd-20th speaker should be keeping track of the the changing number left based on each previous speakers correct pronouncement and can compare that to the number they see in front of themself. They will be able to correctly deduce their own color.

to illustrate as an example:

#1 sees 10 red and 9 black (10R/9B), he says red -maybe gets lucky and survives, if not he is the 1 sacrifice we knew we might have, brave soul that he was.

# 2 sees either 10R/8B or 9R/9B on the remaining 18 in front of himself. He knows there should be 10R/9B including his own so he knows which his must be.

# 3 knows from the original 10R/9B, accounts for the correct answer that #2 gave, then deduces his own color from what he sees in front of him.

# 4 - 20 repeat, keeping track of the running count of R & B vs what he sees in front of himself.

example 2

#1 sees 18R/1B - says R - maybe gets lucky on his own.

#2 two possibilies: he sees 18R/0B and knows he's B or he sees 17R/1B and knows he's R

etc.

This should work no matter what the initial distribution of hats is.

May not work because if all hats are black the first will say black and the second one will not know if his is red or black because, if he is red, the black ones still are majority

[Guest]

Each prisoner shouts out the colour of the hat of the prisoner who is standing directly in front of him. This guarantees that 19 prisoners will be saved. The prisoner who starts (#20) has a 50/50 chance that he is wearing the same colour hat as prisoner #19, so he is the only one with a 50% chance of survival.

[Guest]

Each prisoner shouts out the colour of the hat of the prisoner who is standing directly in front of him. This guarantees that 19 prisoners will be saved. The prisoner who starts (#20) has a 50/50 chance that he is wearing the same colour hat as prisoner #19, so he is the only one with a 50% chance of survival.

Not really, this is wrong because then all the prisoners must have the same color.

the prisoners can only guess their own color but they can not give the color the person in front of them as well

[Guest]

the real answer is that there is no foolproof plan to save even only 19 people the most you can estimate out is 15 and can only really garentee 10

[bonanova]

the real answer is that there is no foolproof plan to save even only 19 people the most you can estimate out is 15 and can only really garentee 10

Nope.

[Guest]

Is the answer still not discovered (I could not go over all the posts). Here is my reasoning:

Man no 20 at the end of row calls out the color which is say an EVEN Number count. Of the 19 hats he sees, one color has to be even.

Guy no. 20 can live or die - up to his luck. But from then on every person can get the correct color if :

1. He remembers the first guy's answer

2. He diligently ticks of all the successive answers coming from guys behind him.

HOW:

Say guy 20 says BLACK (means Black was in Even Number Red was odd number count)

Guy 19 - if he sees Even no. of Black in front, he himself is RED. Otherwise he calls BLACK and lives

Guy 18 - If 19 called RED and he sees EVEN number of Black in front of him , 18 is RED else he is Black

.. but if 19 called BLACK and after he called correctly there would remain now an ODD number of Blacks, excluding no. 19. Now if no. 18 sees ODD Blacks in front , he is RED otherwise 18 knows he is black.

So every guy remembers which color was Even at the beginning and then keeps modifying the count with each call, and lives to drink beer with his buddies except perhaps guy no. 20, to whose memory in the worst case they will all be drinking gratefully.

[Guest]

19 is the best solution with the last guy having a 50-50 chance assuming there are no errors or jerks. When the first prisoner guesses he can use an auditory signal to the person in front of him such as a high pitch answer for a red hat in front of you and low pitch answer if a black hat is in front of you.

I'm assuming that most of the prisoners wouldn't be able to do anything major mathematical calculations in such a high-stress scenario.

[Magic_luver101]

my idea only has a 50/50 change of killing 1 person the person will state his colur as a question if the person is ahead of him has a red hat and an exclamation if they have a blach hat the first person to go has a 50/50 chance

[Guest]

one of the great riddles!!! Hope I would have tried it before looking at the solution.

[Guest]

Can't ya just accept the terms of the story ? We can guarantee the survival of 1-19, with a 50/50 chance for #20.

There are 4 possibilities for n and n+1 (in order, ex 19 & 20): RR, RB, BR, BB.

When #20 speaks, seeing #19's color, he says R or B. Assume #20 says R:

If #20 says R and is executed, then #19 knows that #20's was B, so RR and BR are excluded, leaving RB or BB. But then when #20 said R, he must have excluded BB, so #19's hat is R.

If #20 says R and is *not* executed, then #19 knows that #20's was R, so RB and BB are excluded, leaving RR or BR.

Assume it was RR: then #20 saw R. But if he saw R then RR was true and #19 is R.

Assume it was BR: then #20 saw B. But if he saw B, then RB is excluded, and BB was excluded already. So BR is not possible. So RR was true again and #19 is R.

Since #20 is R, #19 can conclude that his is R. If #20 says B, then substitution will show that #19's is B also. So all the hat's except possibly #20's are the same color, and 19 find out which after the first case. QED.

[Guest]

scratch that last error...wait a bit... <_<

[Guest]

If the person in the back says the color of the person in front of him/her, then the person in front will know the color of his hat and will be able to set himself/herself free. Right?

I liked this one. Message me the answer please? Thank you!