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.

[unreality]

I just want to acknowledge that this topic has gotten over a quarter of a million views - that's impressive

SirRonnie123: the problem is that this only saves 10/20 for sure, 15/20 on average. There are more life-efficient methods, as seen over these 28 pages

[randro]

what about putting your head really close to the other guy so you can see if it reflects red on the persons shirt then you have a red hat and it it doesnt or barely reflects black its black.

[Guest]

how are they suposed to be killed if there killed by some sort of reflective object they could look into that and see there hat color so 20/20 could survive.

[bonanova]

how are they suposed to be killed if there killed by some sort of reflective object they could look into that and see there hat color so 20/20 could survive.

OP states that ...

Of course you will not be able to see the color of your own hat

[Guest]

OP states that ...

Of course you will not be able to see the color of your own hat

oh sorry

[bonanova]

oh sorry

No problem.

If fact, in some puzzles it's exactly that kind of thinking that gets to the answer.

That's why the wording of the OP is important.

The solver has to see what's in the wording, and what is not, to arrive at valid solutions.

In this particular problem, only the words red and black -nothing else,

and not how the words are said - are to be used to find your own hat's color.

[Guest]

Aren't you assuming that there are the same number of black and red hats (e.g 10 red, 10 black) which is not specified in the puzzle?

[Guest]

It seems to me that the first person would just say the hat color of the person in front of him. If his matched, he's okay, but from that point on everyone would just do the same thing. If we're lucky all twenty live!

[bonanova]

Aren't you assuming that there are the same number of black and red hats (e.g 10 red, 10 black) which is not specified in the puzzle?

Hi Lori, and welcome to the Den.

A solution that has been posted a few times now, does not make any assumptions.

For example.

[bonanova]

It seems to me that the first person would just say the hat color of the person in front of him. If his matched, he's okay, but from that point on everyone would just do the same thing. If we're lucky all twenty live!

Ouch.

If the colors alternated every prisoner would say the wrong color.

[Guest]

yelling the color of the hat in front of you saves at least 19 men. the first guy has to get lucky.

[bonanova]

yelling the color of the hat in front of you saves at least 19 men. the first guy has to get lucky.

If color alternates, you save only 1 while dooming 18. <_<

[Guest]

Good thinking you guys, and there are even more ideas to solve it this way: there is the tone of voice (high or low pitch), the volume (screaming or normal), timing (suggested)....

But we wanted to stay restricted to a system where a simple and neutral "BLACK" & "WHITE" will provide a bullet proof technique to save ALL BUT ONE of the prisoners (one of them will have a 50-50 chance of surviving).

And here's my final challenge:

FIND A WAY THAT WILL SOLVE THE PROBLEM FOR ANY NUMBER OF PRISONERS (20 or 19).

PS: Bonanova already found it... And you are very close: just twist the most successful technique for a bit.

Well, I think we can do like this.

Lets name the persons Pn through P1.

The first person (the sacrificing man) (P1) to answer will look at the total number of Red Hats in Front of him and Say

"Red" if the total no. of Red hats is even and "Black" if the total no. of Red hats is Odd.

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

Smart peoples can now directly jump to smarts: section.

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

Now, the next person P(2) to answer will look at the total no. of Red hats ahead of him and

Case 1: if it is even and the sacrificing man(P1) had said "Red" indicating presence of even no. of Red hats ahead of P1 , then he must be wearing Black hat, so he says "Black".

Case 2: if it is even but the sacrificing man(P1) had said "Black" indicating presence of odd no. of Red hats ahead of P1 , then he must be wearing Red hat, so he says "Red".

Case 3: if it is odd and the sacrificing man(P1) had said "Red" indicating presence of even no. of Red hats ahead of P1 , then he must be wearing Red hat, so he says "Red".

Case 4: if it is odd but the sacrificing man(P1) had said "Black" indicating presence of odd no. of Red hats ahead of P1 , then he must be wearing Black hat, so he says "Black".

Now, lets move a step further.

Lets assume Case 3: occured with the P2.

Then next person P3, now knows, P1 ( he had said "Red") sees even no. of Red hats ahead him and P2 (he had said "Red") is wearing Red hat.

If now P3 sees even no. of Red hats ahead of him also, then, he must be wearing a Red hat too.[ because only then p1 would have seen even no. of red hats]

if p3 sees odd no. of Red hats ahead of him, then, by similar logic he must be wearing Black hat.[because only then p1 would have seen even no. of red hats]

[[difficult to catch up??? here is help: Total no. of red hat seen by P1= Total no. of Red hat seen by P3 + Total red hats among P2 and P3 ]]

Having known his hat's color by this way P3 answers correctly to save his life and also leaves the information of his hats color for left members.

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

smarts:

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

In general every person ahead the sacrificing man, knows

---> (?) if odd red hats or even red hats is visible by the sacrificing man

---> (a) total red hats behind him (leaving the hat of the sacrificing man)

---->(b) total red hats ahead him

then certainly he knows the color of his hat because

if (a) + (b) is odd, and (?)=ODD, his color is Black

if (a) + (b) is Even, and (?)=ODD, his color is Red

if (a) + (b) is Odd, and (?)=Even, his color is Red

if (a) + (b) is Even, and (?)=Even, his color is Black

Proceeding this way all except P1 can certainly save their lifes.

[Guest]

My above method can save all except the last on the row. And it works for any no. of person just as the questioneer demanded.

[Guest]

Is it fairly simple in that at least 50% will go free. Prisoner 20, shouts out what prisoner 10 is wearing, prioner 19 shouts out what prisoner 8 is wearing etc?

Edited March 10, 2009 by Wiggy74

[bonanova]

Is it fairly simple in that at least 50% will go free. Prisoner 20, shouts out what prisoner 10 is wearing, prioner 19 shouts out what prisoner 8 is wearing etc?

Guessing gets 50% on average.

Your method guarantees 50%

Can you guarantee 19?

[Guest]

I have already submited the method to save 19 out of 20 or even (X-1) out of X (--->LooK at 4 post before this). Why don't you see?. Is it wrong?

Edited March 11, 2009 by the-genius

[bonanova]

I have already submited the method to save 19 out of 20 or even (X-1) out of X (--->LooK at 4 post before this). Why don't you see?. Is it wrong?

Your solution is the correct one.

Actually, the solution has been posted more than once.

Probably because the thread is so long [ca 300 posts] new solvers don't always read it from the start.

[Guest]

Bonanova, your solution works and would save 19 lives, with a 50-50 chance on the 20th guy in the line. But so does the solution that was brought up by Carolyn (I think that was the name) many, many pages ago. She said (to paraphrase) The first one just names off the color of the hat in front of him. That solution is much simpler and ends up with the same odds for survival. I may have missed your response to this although I did try to read most of the posts. Why all the odd/even mumbo jumbo when the result would be the same by simply naming the color of the hat in front of you?

uggh, never mind. I just realized why that solution wouldn't work. DUH! I think I must be sleep deprived. Sorry for the post!

Edited March 13, 2009 by iam

[Guest]

there was no mention of how many red hats or black hats are to be given.

[bonanova]

there was no mention of how many red hats or black hats are to be given.

That's information the prisoners don't need.

[Guest]

Here is another solution that guarantees 19 people live, and it is easier than the odd/even thing.

Last person says the color of the person in front of him and hopes he has the same color.

The next person is free to say what color they have been told, but how they say it tells the next person the color of their hat. A shout tells the next person their hat is black, a normal voice tells them their hat is red.

All you have to do to know what color your hat is, is listen for a shout or a normal voice.

You then say your color based on the shout/normal voice thing in either a shout or a normal voice to tell the next person the color of their hat.

They work out the difference between a shout and a normal voice the previous night.

Edited March 27, 2009 by b_stackhouse

[bonanova]

Here is another solution that guarantees 19 people live, and it is easier than the odd/even thing.

Last person says the color of the person in front of him and hopes he has the same color.

The next person is free to say what color they have been told, but how they say it tells the next person the color of their hat. A shout tells the next person their hat is black, a normal voice tells them their hat is red.

All you have to do to know what color your hat is, is listen for a shout or a normal voice.

You then say your color based on the shout/normal voice thing in either a shout or a normal voice to tell the next person the color of their hat.

They work out the difference between a shout and a normal voice the previous night.

Question:

Why not set up 2¹⁹ combinations of

• tones of voice
  
• loudness
  
• speed
  
• pitch
  
• tap-dance steps
  
• language
  
• giggling
  
• clearing one's throat
  
• etc.
  

that the first person uses in guessing his own color?

The others can then immediately know their color.

Answer:

Because all of those things violate the terms of the OP,

in which it is said no means of communication is allowed other than saying black or white..

[Guest]

A well placed mirror might help...

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