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]

The 20th prisoner says the color of the hat in front of him. If he is executed than the rest of the prisoners know that was not the color of his hat if he is not executed it was the color of his hat. Prisoner 19 then says the color of his hat. Prisoner 18 can see all the hats in front of him and now knows the color of the two hats behind him and can conclude the color of his hat. This continues until all prisoners have stated the color of their hat. Thus 19 prisoners survive and prisoner 20 has a 50/50 shot to live.

[Guest]

The 20th prisoner says the color of the hat in front of him. If he is executed than the rest of the prisoners know that was not the color of his hat if he is not executed it was the color of his hat. Prisoner 19 then says the color of his hat. Prisoner 18 can see all the hats in front of him and now knows the color of the two hats behind him and can conclude the color of his hat. This continues until all prisoners have stated the color of their hat. Thus 19 prisoners survive and prisoner 20 has a 50/50 shot to live.

But what if its not a 10/10 distribution?

[Guest]

I'm not entirely sure about this but:

The first man counts the amount of hats. Whichever amount of them is an even amount, he says that hat. he may die. The next man has to count the amounts and if there are odd of both amounts, he has the colour that the first man said, and, if not, he has the opposite colour. The next man then listens to the previous 2 and decides this: If the previous person said the same as the first person, and he sees an even amount of the one that they said, he knows that he has that colour too. If they said different ones, and he sees an odd amount of both in front of him, he knows that he has the same as the first one, and so on.

Man 20 sees 10 black and 9 red in front of him and says 'Black'. He has a 50/50 chance of surviving. Man 19 then sees 9 Black and 9 Red in front of him. He knows that black has to be an even number and says 'Black'.

Man 18 then sees 9 Black and 8 Red. He knows that because man 19 said black, the even amount of blacks would become odd, and black would have to stay at 9, so he says 'Red'.

Man 17 then sees 8 Black and 8 Red. He knows the reasoning for 18, and that he would of had known that blacks were odd for him as he said red, so he must have a black to make black odd again.

This system goes on for the rest of the men

Not sure if this works, or if somebody else already posted it, sorry if it has

[Guest]

100% life saving chance for 19 prisoners.50% chance for last prisoner no 20.

Prisoner 20 after looking at prisoner 19 hat, should say the word loudly red or black(this will decide his fate with 50/50 chance but he will certainly save life of prisoner 19). Now prisoner 19 knows his hat color and also the color of prisoner 18. If prisoner 19 hears red and prisoner 18 also has red hat, he should spell loudly R.E.D. But if 18 has black color hat, 19 should say red (not spell the word). Now prisoner 18 knows from spelling or saying of the word , color of his hat and will repeat the process as stated. The last prisoner 1 ,no matter will either spell or say the word to save his life.

[Guest]

There is a Sure Win Tactic for 19 people that would not technically violate the rules but it would be pretty obvious if you want to make it easy for the prisoners,

The prisoners could use silence to their advantage, well this plan would mean that the 20th person would have to be ready to sacrifice himself, he only says the color of the person in front of himself hoping it is the same color he is wearing.

now let’s say the 18th person has a black hat the 19th person would pause a certain amount of time before answering and saying his hat color that was revealed by the 20th. Then lets say the 17th persons hat is red 18th would answer quickly and say his hat is black which was revealed by the long pause that 19th applied to his answer and so on.

the length of the pause before answering could technically bee as long as they want because it would not violate the rules

Sorry for bad language

[Guest]

100% life saving chance for 19 prisoners.50% chance for last prisoner no 20.

Prisoner 20 after looking at prisoner 19 hat, should say the word loudly red or black(this will decide his fate with 50/50 chance but he will certainly save life of prisoner 19). Now prisoner 19 knows his hat color and also the color of prisoner 18. If prisoner 19 hears red and prisoner 18 also has red hat, he should spell loudly R.E.D. But if 18 has black color hat, 19 should say red (not spell the word). Now prisoner 18 knows from spelling or saying of the word , color of his hat and will repeat the process as stated. The last prisoner 1 ,no matter will either spell or say the word to save his life.

It has to be said in the same manner, with no different tones, like just practically pushing a button.

[Guest]

There is a Sure Win Tactic for 19 people that would not technically violate the rules but it would be pretty obvious if you want to make it easy for the prisoners,

The prisoners could use silence to their advantage, well this plan would mean that the 20th person would have to be ready to sacrifice himself, he only says the color of the person in front of himself hoping it is the same color he is wearing.

now let’s say the 18th person has a black hat the 19th person would pause a certain amount of time before answering and saying his hat color that was revealed by the 20th. Then lets say the 17th persons hat is red 18th would answer quickly and say his hat is black which was revealed by the long pause that 19th applied to his answer and so on.

the length of the pause before answering could technically bee as long as they want because it would not violate the rules

Sorry for bad language

The point of the puzzle was that no pauses or changes in speech were allowed.

[Guest]

You can guarantee that 10 will be freed. The prisoners chat the night before and agree on the following. The prisoner on the back of the line tells everybody the color of the hat immediately in front of him. So prisoner #20 says, "red". Now prisoner #19 knows his hat is red. He in turn says, "red" and is freed. Prisoner #18 sees that #17 is wearing black. So he says, "black". Now #17 says "black" and is freed. #16 does this favor for #15. #14 does this for #13 and so on.

[Guest]

First guy is a coin toss - let's wish him good luck.

His job is to establish the parity of black hats visible to him.

He says "Black" if he sees an odd number of black hats; "Red" otherwise.

By paying attention to what has been said, each prisoner will know his hat's color.

Example:

Second to speak hears "Black" and sees an even number of black hats.

He knows his hat is black [odd changed to even - must be his is black] and says "black".

Third guy has heard "black" and "black" and sees an even number of black hats.

He knows his hat is red [even stayed even - his hat can't be black] and says "red".

And so on, to the front of the line.

General algorithm:

The first time you hear "black", say to yourself "odd".

Each time your hear "black" after that, change the parity: "even", "odd", ... etc.

When it's your turn, if the black hats you see match the running parity, you're Red; Black otherwise.

Call out your color.</div></div></div>

Nice!

[Guest]

[spoiler=stomp the yard ]the last prisoner has a 50/50 chance of survival. he guesses his own and stopmps once(red) or not at all (black) and so on....until the first prisoner just states his own color. my solution saves only 19 prisoners but im sure the king and the guards would notice if prisoners started stomping randomly

[Guest]

i dont know if i am right but 100 percent chance that 10 of them will survive and 50% chance the other ten will survive, if each prisoner lets say teams up with the other, so it would be prisoner 20 with 1, 19 - 2, 18 - 3, 17 - 4, 16 - 5, 15 - 6, 14 - 7, 13 - 8, 12 - 9, 11 - 10 and the teaming stops if each prisoner bellow number 11 looks at his team mate and remembers the color of his hat he would say the color of his team mates hat when he is asked. and his team mate would remember what he said so that when he is asked he would answer correctly. that leaves the prisoners bellow number 11 with a 50% chance of getting the color of their own hat correct. but at least 4 of them would get it correct for them selves.

[Guest]

Actually there's an easier, non-mathematical way to do it. The question was, and this is important, what's the minimum number of prisoners that can be GUARANTEED to survive. The answer SHOULD be 19 of the 20, but, as with all things in life, there is a catch.

The king said they can only say "red" or "black", but he DID NOT put any restrictions on HOW they could say it, and he also didn't say in what order they would be placed in line, so while the last one in line has only a 50/50 chance of survival, the rest can be guaranteed to survive, as long as everyone plays along. HOWEVER (here's the catch), if there is any animosity between the prisoners, any one of them could foul up the person in front of him, thus ensuring their swift execution, so in reality, the answer to the question is NONE OF THE PRISONERS IS GUARANTEED SURVIVAL.

Now, assuming all the prisoners are acting ethically and there is no animosity among the prisoners, everyone, save the last in line, will know their hat color without memorizing odds/evens or doing math etc, thus 19 of the 20 could survive. Here's how it works:

The first to guess will just make a guess (he has no other option), so let's say he guesses he's wearing a black hat. If the color of the hat in front of him is also black, he will YELL out "BLACK", letting the person in front of him know his hat is also black. If the color of the hat in front of him is red, he will SOFTLY say "black", letting the person in front of him know his hat is NOT black, i.e., it is red. here's an example, using 5 prisoners, starting from the back of the line:

5:BLACK(by YELLING "BLACK", lets #4 know that his hat is also black. unfortunately, #5 only has a 50/50 chance of survival. Good luck to him!)

4:black(says this SOFTLY, letting #3 know that his hat is NOT black, i.e., it is red, and #4 survives)

3:RED(knowing his own hat is red and seeing #2's hat is also red, he YELLS "RED", letting #2 know his is also red, and #3 survives)

2:RED(knowing his own hat is red and seeing #1's hat is also red, he YELLS "RED", letting #1 know his is also red, and #2 survives)

1:RED(knowing his own hat is red he says "red" however he wants to, and #1 survives)

Edited April 5, 2011 by JesusChrysler

[Guest]

hi all, im new to this site, and somewhat stumbled onto this interesting puzzle... i read the answer by bonanova - n its awesome 0_o

anyways, before seeing that, i came up with another solution (kinda lame, now that ive read the one mentioned by bonanova ), which is as follows:

the first guy to answer choses the color he wants to say (50% chance of him surviving, if im not wrong )

he also notices the color of the hat of the next guy, ie the one in front of him

if the color the first guy says is the same as the color of the hat of the guy in front of him, then he immediately says the color, ie, he doesnt pause or anything...

if it isnt, then he takes lets say a second or 2 to say the answer, and the other guy then knows whether the color of his hat is the same as the one the first guy said or not, and thus continues this...

kinda lame, but meh

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

If the people agreed before hand that the 20th person would say, "Black" if the number of black hats is even in front of him, and "Red" if the number of black hats in front of him was odd.

This would tell #19 to look for odd or even numbers of black in front of him. If #20 says "Black," #19 will know that there should be an even number of black hats to count. If there is not an even number, then he would be wearing a black hat. This will save 19 people and leave #20 a 50/50 chance.

Unless I missed something, I think that would work.

[Guest]

The group agrees that if # 20 sees an odd number of black hats he says "black" to tell #19 that if he adds his hat to the black hats he ends up with and odd number (or says "Red" if it's even or vise versa.. whatever they agree on). so #19 looks at the black hats and knows what his hat's color is. Same goes for #18 after he factors in what #19 said.

[Guest]

u can save all 20 u just need good memory

for the first 19 we all know how to save them

but u keep saying that prisoner 1 has a 50% chance but he could easily survive

how?

We all know that there is 20 prisoners

So there is 10 hats of each colour

so all he needs to do is count how many times red or black is shouted out.

If you choose red to count and it is shouted out nine times by the time they get to him the his hat is red and if it is called out 10 times it is the other colour.

You can use the same method if you chose black just replace red with black.

[Guest]

u can save all 20 u just need good memory

for the first 19 we all know how to save them

but u keep saying that prisoner 1 has a 50% chance but he could easily survive

how?

We all know that there is 20 prisoners

So there is 10 hats of each colour

so all he needs to do is count how many times red or black is shouted out.

If you choose red to count and it is shouted out nine times by the time they get to him the his hat is red and if it is called out 10 times it is the other colour.

You can use the same method if you chose black just replace red with black.

Bear in mind, it's not stated anywhere that there are exactly ten hats of each.

If this was the case, everyone'd survive with ease (the first one would know if he saw 9 reds and 10 blacks his color was red, the next would be able to use the previous information and so forth). The mystery here is that it's unknown whether there are 2 reds and 18 blacks, or 20 blacks and no reds at all.

[Guest]

i say the 20th prisoner can just count the colours thats if there is 10 black and ten red than he'll know his color

[Aaryan]

It is not 10 black and 10 red, it is any combination of the two to equal 20.

[bonanova]

First guy is a coin toss - let's wish him good luck.

His job is to establish the parity of black hats visible to him.

He says "Black" if he sees an odd number of black hats; "Red" otherwise.

By paying attention to what has been said, each prisoner will know his hat's color.

Example:

Second to speak hears "Black" and sees an even number of black hats.

He knows his hat is black [odd changed to even - must be his is black] and says "black".

Third guy has heard "black" and "black" and sees an even number of black hats.

He knows his hat is red [even stayed even - his hat can't be black] and says "red".

And so on, to the front of the line.

General algorithm:

The first time you hear "black", say to yourself "odd".

Each time your hear "black" after that, change the parity: "even", "odd", ... etc.

When it's your turn, if the black hats you see match the running parity, you're Red; Black otherwise.

Call out your color.</div></div></div>

After two and a half years, I see that my algorithm is incomplete.

General algorithm:

Say to yourself "even"

Each time your hear "black," change the parity: "odd," "even," ... etc.

When it's your turn: if the running parity matches the black hats you see, say Red; Black otherwise.

Call out your color.

This covers the case where, at your turn, you have not heard "black" said at all.

[Guest]

they discuss it earlier in prison, the previous night by communicating through signs/signals

and/or

there can a possibility of everybody wearing reflector as a necklace/ornament/.... and in the case of the #1prisoner, the next prisoner can make a sign (eg., rubbing his' shoes in the ground, sighing, etc....)

so finally there is 100% possibility of everyone escaping

Note: you have never given any possibilities... so this might be the answer

[Guest]

19 will be guaranteed to set free, the 20th prisoner will just shout the 19th hat color, so 19th knows his hat color ... if 19th see a different color to 18th, he need to pause for 5 seconds after the question before he shout his hat color signalling the 18th prisoner's hat color is the other color shouted by the 19th. if the 19th shouted right after the question it means they have the same hat color. and this goes up to the 1st prisoner.

the 20th prisoner has a 50% chance to set free.

[Guest]

Kindly let me know the answer to this mind boggling brain teaser, for some unknown reason the spoiler does not show itself even after several clicks . .

[Guest]

Ok, this is my first puzzle on this site and my first reply, so here goes.

I hope I do this spoiler thing right, but if not, ***spoiler alert below***

The prisoners agree the night before to choose a hat color to use as their marker, for this example let's use red.

They then decide that when the first prisoner says "red" or "black" it will only be a code for "odd" or "even", as in the # of red hats among the 19 in front of him is either odd or even. Let's say they choose red = odd since they both have 3 letters, and that will be easy to remember when you have a gun pointed at your head.

They line up, and the first prisoner sees x red hats in front of him, let's say it's 8. Since 8 is even, and black is the code for even, he yells out "black". At this point, he lives or dies based on luck alone.

The 2nd prisoner now knows the total # of red hats remaining in line is even. If he counts only an odd number in front of him--in this case 7--he knows his hat must be red, since he would have to be the 8th to make it even, and there's no one else behind him.

The next prisoner proceeds in the same way, he now knows there are an odd number of red hats left in line. If he sees only an odd number, he knows his hat must be black The prisoners obviously must listen and keep track of how many "reds" are called out behind them so they know whether their hat must keep it odd or even.

Am I right?!

[Guest]

cant the first person tell the person in front what colour hat they are wearing and so on... then so long as they are all truthfull all should be saved exept the first one who only has a 50/50 chance.

Thank you! I was wondering if I was the only one who thought of that.

The questions are "...find a way to guarantee the freedom of some prisoners tomorrow? How many?"

So I agree 100%, the best answer is:

Each person simply states the color of the person's hat in front of them.

If they are honest, that guarantees 19 live and the first person has a 50% chance!

Pretty good odds, but I still wouldn't want to be the first person in line, or in front of someone who had it out for me. 8^)

-Ken