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]

I really enjoyed Bonanova's solution. I have another one, but it only works by taking advantage of the wording of the riddle. It says that you can only say black and red, but not how you say black and red. Thus, my solution, like Bona's is that the first guy is screwed because he will say whatever the color of the guy in front's hat is. From there, the that guy will say the color of his hat (revealed by the first guy's answer) but either stretch out the word or say it very quickly to let the guy in front of him know what color his hat is. For example, he could say blaaaaaaack to indicate the next person's hat is red or a short pronunciation of black say that the next person's hat is black.

Simple e.g.

Color of hats: Person's response:

20. Black 20. Black

19. Black 19. Blaaaack

18. Red 18. Reeeed

17. Red 17. Red

16. Black 16. Etc...

In other words, the person behind you can tell you the color of your hat by whether they respond with an elongated answer or a truncated one.

That would make this answer essentially the same as post #7, #28 and many others after that.

Since that was never the intention of the puzzle, I think that could be the reason that Roolstar in post #8 added the following:

"Now can you find a bullet proof technique, in case the king does not allow us to change the intonation of our voice, or makes us click on the right answer on a giant screen in front of everybody, or makes us push either one of two buttons where the computer says the choice we made....."

"I'm just adding these handicaps because this is what I meant by saying: no communication is tolerated (touch, words...). Communication means no message to be sent by voive or touch or noise or light..."

But other than that... it was a good suggestion.

Edited April 14, 2009 by uhre

[Guest]

Aaaah I see, you're absolutely right. Great riddle though, I've never heard of it before, did you find this or write it?

[Guest]

Sheesh. I spent a good deal of time on working this out and then had a eureka moment. It's all so simple. It has been overthought (is that a word?).

The prisoners agree, overnight, that the first fellow, who can see all the rest, will count the red hats. He will say Red if the count is even, Black if the count is odd. He has a 50/50 chance of being right about his own hat, of course. So let's say the number of red hats is uneven, and guy 1 therefore says "Black."

The next guy—call him guy 2—who can see 18 people in front of him, simply counts the red hats. He, and every one else, knows there is an uneven number of red hats, thanks to the brave first guy.

If guy number 2 counts an even number of red hats in front of him, he knows his hat must be red as well. Guy number three, and everybody else, simply keeps a count of all red hats declared and all red hats in front of them. If any person counts an even number of red hats (3 before, and 7 ahead, for example), then that person must be wearing the red hat that makes the number odd. If they can count an odd number of red hats, they must be wearing a black hat.

This works with 100% accuracy up to and including the last man. Only the first guy has a 50/50 chance of being right about his own hat. The rest walk away with 100% certainty. Very simple.

[Guest]

not sure if this is allowed by the rules, but technically they aren't breaking any. You can guarantee 19 survivors this way. 20th person says the color of the hat of the person infront of him. Let's say it was Red. To signify the person's hat infront, if it's also Red, he'll just quickly say Red. If it's black, he'll elongate the word Red to tell the person in front it's not Red. Then that person will either say black quickly or slowly until they get to the final person. If everyone actually follows these directions, guaranteed 19 survive, 50/50 20 survive.

[Guest]

i think theres an easy way with 1 sacrifice. Since the question is not how to save them all but the most:

the prisonners must agree the night before whos gonna die for the others or that in any case:

THE LAST ONE TELLS THE COLOR OF THE HAT BEFORE HIM>

so, if hes lucky hes got the same color, if not, the next one will know

[Guest]

i think theres an easy way with 1 sacrifice. Since the question is not how to save them all but the most:

the prisonners must agree the night before whos gonna die for the others or that in any case:

THE LAST ONE TELLS THE COLOR OF THE HAT BEFORE HIM>

so, if hes lucky hes got the same color, if not, the next one will know

If you think you've got a solution then chances are its already been suggested in the previous 30+ pages. To clarify, the above solution won't work someone has already explained why.

[Guest]

Hey. i read 12 pages and saw theres more so dont nkow if anyone said this,

heres the solutions i came up with in order

1. The king said they can say only red or black? 19 will live if the person at the back jsut says the colours of the hats of the people in front of him, black black black black black red red black etc,

but another one...it doesnt say you cant do this

"the colour of the hat you're wearing"

this way all live, but the king will prob get pissed and still kill you

just take your hat off, look at it, put it back on lol, say the colour of the hat you're wearing

Edited April 28, 2009 by Guitarist

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

Thats gr8!!!But what if:a)The prisoner in front is to move further away or wisper his colour such that the next person doesn't hear?b)the prisoners aren't won the hat in alternating manners(ie:red,black,red...)?

[Guest]

Why don't we add a bit of game theory in this? Right before the whole process starts the king goes up to the last person in secret and tells him that his hat is black. However, according to the plan, he is supposed to call out red?

Will he save himself and allow the rest of the prisoners get killed?

[Guest]

Doesn't only one have to die in the end?

The king said the prisoners could only say red or black, but he never stated how many times a prisoner could say red or black.

So couldn't the very first prisoner just name off all the colors in front of him in a row? Like Red, Red, Black, Red, Black, Black, etc? He would die, but the rest would live because of him, and it would be the fewest casualties.

[Guest]

Well, the last person in the line can answer by giving the colour of the hat on the guy in front of him and that might or might not save him (#20) but it will save the guy in front (#19). Then #18 would guess by calling the colour of the hat of #17 and that would enable #17 to know and speak out the colour. Continuing this process, half the group is saved for sure, some of the other half saved maybe by chance.

G'night. I'll probably dream up anotehr solution.

------------------------------

I am one of 20 prisoners on death row with the execution date set for tomorrow.

We will all stand in a row (queue) before the executioner and they will put a hat on our head, either a red or a black one.

Of course we will not be able to see the color of our own hat; we will only be able to see the prisoners in front of us 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…

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?

[Guest]

Well, the last person in the line can answer by giving the colour of the hat on the guy in front of him and that might or might not save him (#20) but it will save the guy in front (#19). Then #19 is "set free" ... free to go and free from the restriction to not look back or communicate together in any way (talking, touching.....). ... he could then call out in order the colours of the remaining 18 hats to the ones in line, and enable them all to be set free ...

G'night. I'll probably dream up another solution.

------------------------------

I am one of 20 prisoners on death row with the execution date set for tomorrow.

We will all stand in a row (queue) before the executioner and they will put a hat on our head, either a red or a black one.

Of course we will not be able to see the color of our own hat; we will only be able to see the prisoners in front of us 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,

[Guest]

This is an awesome riddle btw I voted 5 stars ;D

ok so here wat i think is the solution to this puzzle...

But the problem is that only 10 of the 20 prisoners survive...

Here's how it is done...

1) The night before the prisoners decide to name the colour of the hat that the prisoner infront of him is wearing..so the person infront knows the colour of the hat..

2) Like this all the alternate prisoners know the colour of their hat and they survive and also if the colour of the hat of the remaining prisoners matches the colour of the hat of the prisoner infront of him..then he too survives...this atleast guarentees the survival of half of the prisoners..

I know this is not the perfect solution and its worth a try..

P.S - I am new to this community..so hi ppl!!

[Guest]

The 20th man in line has a 50/50 chance but if each man shouts his color when called the next man will know he has a red hat and if he wispers his color the next one is black and so on till the last one.

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

There is an obvious oversight.. The assumption that the King will use an even number of Red and Black hats. Is it possible he could put all black hats except one?

[Guest]

"10" The last (first) who see all 19th on the front of him will say the correct color of the hat of his body on the front of him to safe him (her). Prisner # 18 will correctly give the right color of the hat of # 17 and so on...

This will guarantee a freedom for 50% of the prisners.

[bonanova]

There is an obvious oversight.. The assumption that the King will use an even number of Red and Black hats. Is it possible he could put all black hats except one?

Read the OP again. Even number is not mentioned.

The King is free to use any number of Red and Black hats totaling 20.

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

i have to disagree with that..coz it says "can you find a way to guarantee the freedom of some prisoners tomorrow? How many?" and it also doesnt say taht there's goin to be 10 red hats and 10 black hats so that solution is not a guarantee...a guaranteed way is to save 10 prisoners...every other prisoner will yell the color of the hat the person infront of them is wearing...doin thsi you guarantee the freedom of 10 prisoners..and they got the night to think about this plan...thats the only way i can see you can GUARANTEE the freedom of some of the prisoners

[Guest]

bonanova two thumbs up 4 u

@buloyman: bona's way will save min 19 prisoners.

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.

Only the first guy to choose (the 20th prisoner) is not 100% save. It's a lucky 50-50 chance...

In this example, bona uses odd black parity as the start. Of course we can also use odd red parity, even black parity, or even red parity.

According to the system you choose, let say, odd black parity, the 20th prisoner will count the black hats in front of him, because he can see what 19 prisoners in front of him are wearing.

ANY number of black hats will work. From 0-20. The point is, if number of black hats in front of the 20th is an even number, he should say BLACK, to make it odd (even number + 1 = odd number). If the number of black hats is already odd, he should say RED, to keep it odd. If he lucky, he will survive... If not, at least all his friends are alive.

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.

(this is only a simulation)

R B B B R B B B B B R B R B R R B R R X(20th)

1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0

The system used -> odd black parity

20th sees 11 black hats, already odd, he shout RED (if he is lucky, he survive, if he wears black, he died)

black shouted = no, parity still odd

19th sees 11 black hats, already odd, he shout RED

black shouted = no, parity still odd

18th sees 11 black hats, already odd, he shout RED

black shouted = no, parity still odd

17th sees 10 black hats, parity odd, but the number is even, so it means he is wearing BLACK

black shouted = yes, parity changed to even

16th sees 10 black hats, already even, he shout RED

black shouted = no, parity still even

15th sees 10 black hats, already even, he shout RED

black shouted = no, parity still even

14th sees 9 black hats, parity even, but the number is odd, so it means he is wearing BLACK

black shouted = yes, parity changed to odd

and so on....

This way is dynamic, unrelated with how many red or black hats used by the king...

Edited May 13, 2009 by folg3nd

[Guest]

Two booleans must be compressed into one statement. This can be done with tonality. The 20th prisoner has a 50/50 chance of dieing. The night before the prisoners agree that the 20th prisoner will say the color of the 19th prisoner’s hat, for example red. The 18th prisoner has a red hat as well. In the lowest tenor voice possible, the 19th prisoner says red. The 18th prisoner (knowing from the night before that LOW means SAME) is now aware he also has a red hat on. 18 can see that 17 is wearing a black hat. 18 must say red to live. He says red in the highest falsetto he can, to communicate to 17 that his hat is different than red. 17 knows his hat is black. I believe this is the simplest way to guarantee 19 and a half live.

[Guest]

since the prisoners can talk throughout the night they should develop a word code. They aren't allowed to say anything besides red or black so they should turn those words into codes. For example, the first guy has a 50 50 chance and has to guess black or red for his own hat, however when saying the word he should be taking into account the guys hat in front of him. Say he guesses red for his own hat and the hat in front of him is black, he should say reeed and drag the word out a little bit. This could be code to the man in front of him that a drawn out word means black and he knows his hat is black. Then when the next man is saying black for his own guess he sees the man in front of him has a red hat so he would say black short and quick which would symbolize red for the next man. and so on to the end of the line.

[Guest]

YOU COULD JUST ASK YOUR OTHER CELLMATES, "WHAT COLOR IS MY HAT???" IF YOUR CELLMATES AREN'T SICK AND CRUEL, THEY WOULDN'T LIE, GUARANTEEING YOUR SURVIVAL.

ummm.... they don't have the hats while they are in the cell...

[Guest]

You're right ... they are told there are two color groups. The OP says ... among other things ...

bonanova your solution does not work if all are given black hats!!!

[Guest]

I would say its possible to save 10 prisoners with 100% chance and 10 prisoners with 50% chance like this.

IF last prisoner in the row says the color of the one in front of him making sure the prisoner in front (the 19th prisoner) has a 100% chance of getting it right, then 19th prisoner names the color of his own hat the hole thing starts over again with 18th prisoner having 50% chance to get it right by saying the color of the 17th prisoners hat wich then would be getting 100% chance etc etc....

[bonanova]

bonanova your solution does not work if all are given black hats!!!

Which prisoner will say Red?