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]

Would this be allowed?

It says that you can only say red or black, not how many times you can say them. Why couldn't you just call out the color of hats in front of you, in order, and just sacrifise yourself? If you guess your hat as well, you might save everyone. This is my first post, and I joined specifically to post this. Is this anwser allowed?

or am I missing a crucial part of the question?

Edited July 22, 2008 by Immortas

[Guest]

Well ok, so lets use the same example 11R 9B.........What's the "odd" one? there both odd.

But the guy in back sees only 19 of those 20 people. So he sees either 10R 9B or 11R 8B. In either case one of the two colors in front of him has an odd count.

And in fact it doesn't matter if one is odd or not. All that really matters is that Black is either odd or even. If he sees an odd count of Black hats, he says Black, if Black is even he says Red.

The easiest way (for me) is visual, so I drew 20 prisoners standing in a line and randomly chose which ones would wear the red hats and which ones would wear the black hats, (using the famous 11R 9B theory) you will be able to see right away there is no possible way for P1 to make a logical determination, he looks down the line and see's for example 10R and 9B (his own hat would make 11R, however he doesn't know that)

He doesn't know his own hat, so he gets a 50/50 chance of survival, he does see the count in front of him and that is what he uses to make the determination, not the total count of RandB which he doesn't know.

so he see's an odd # of black hats, using your example he would say "black" and then get beheaded .

Poor guy in the back has a 50% chance of survival, the way you placed the hats is one of those times he dies... but his sacrifice is everyone else's gain.

Even if he were to have chosen to say the even # of hat color, all it would have been was a "lucky guess" because there would be no logical explanation to back it up.

As noted, the guy in the back has a 50/50 chance and nothing helps that. But he says Black because he sees an odd number of Black hats.

The guy in front of him either sees an even number of Black hats or an odd number of Black hats. If he sees an odd number of Black hats, and he knows the guy behind him saw an odd number of Black hats, then he knows his hat is Red. On the other hand, if he sees an even number of Black hats and he knows the guy behind him saw an odd number of Black hats it must mean that his hat is Black. Let's assume his hat is Red.

The third guy in lines knows this:

Guy1: Says Black so there is an odd number of Black hats in front of Guy1

Guy2: Says Red so there is an odd number of Black hats in front of Guy2

Sees: An even number of Black hats in front of himself

Knows: He has a Black hat

And so on down the line.

If you are in line (and not the last guy thank goodness)

Each time someone says 'Black' then you change your hat accordingly.

If Guy1 says Black, and you see an even number of Black hats, then you think "I have a Black hat"

Every time you hear the word "Black" you reverse your decision, so Guy3 says Black and you think "I have a Red hat", and when Guy4 says Black you think "I have a Black hat" etc...

Edited July 23, 2008 by Steve Luke

[Guest]

THIS IS A VERY GOOD QUESTION.

the logic based on the answer given is simply PARITY CHECK. It is i think the best solution.

It can just be visualized as a binary signal (high or low) where if parity changes (odd to even or even to odd), i.e. a transistion in signal is treated to be ONE COLOR.

no change in parity i.e. no change in signal level is treated as OTHER COLOR.

very simple.

[Guest]

19 it is. With 20th having 50% probability.

Had solved it long time ago. One of my favs.

Anyway .. my logic is that:

20th says Red if the no. of Red hats he see is Even. Says Black if its Odd.

Rest is simple!

If 19 sees no. of even Red hats in front of him and he heres Black from the 20th he knows he's got to be Red. if he heard Red, then he knows he got to be Black and so on ....

I agree. Without being given more information and the fact that all men are standing one in front of the other (queue) I assume that each man can hear the one behind him. It would then be a matter of trusting the man behind you to tell the truth. As being the man to explain it you must also be willing to sacrifice yourself for the others and be the last man. Assuming that the other prisoners believe what you tell them the night before then you will be the only man at risk. Also, anyone believing what the king has said to you but not trusting you can be offered the chance to be the last man. You would then just need to cover the doubter that lies and is killed behind any other man if the doubter is not the last man and he is killed. The next man must then start the chain over by proclaiming the color of the hat in front of him and hope that his is also that color (50% chance). This seems pretty straight forward. I'm afraid I don't understand what everyone's algorithms are for seeing as how the exact number of colors is not given and the man in front of any other man does not have to specify the color of hat of the men behind him. He needs only to guess his color of hat.

[Guest]

I agree. Without being given more information and the fact that all men are standing one in front of the other (queue) I assume that each man can hear the one behind him. It would then be a matter of trusting the man behind you to tell the truth. As being the man to explain it you must also be willing to sacrifice yourself for the others and be the last man. Assuming that the other prisoners believe what you tell them the night before then you will be the only man at risk. Also, anyone believing what the king has said to you but not trusting you can be offered the chance to be the last man. You would then just need to cover the doubter that lies and is killed behind any other man if the doubter is not the last man and he is killed. The next man must then start the chain over by proclaiming the color of the hat in front of him and hope that his is also that color (50% chance). This seems pretty straight forward. I'm afraid I don't understand what everyone's algorithms are for seeing as how the exact number of colors is not given and the man in front of any other man does not have to specify the color of hat of the men behind him. He needs only to guess his color of hat.

Jumping the gun. I am in error. I misspoke and realize the error of my ways. Having come back to the site I realize that any man speaking his color of hat now puts the man in front of him in jeopardy. I am a retard.

[Guest]

Would calling out the colour of the hat of the person in front of you be considered cheating? The guy at the back of the queue (answer first) has a 50% chance of getting it right? Or would that be considered communication?

Because technically, being able to see the hats in front of you is a form of communication you already ruled out (light).

[Guest]

Would calling out the colour of the hat of the person in front of you be considered cheating? The guy at the back of the queue (answer first) has a 50% chance of getting it right? Or would that be considered communication?

Because technically, being able to see the hats in front of you is a form of communication you already ruled out (light).

The object of this riddle is to try and save as many prisoners as possible, the strategy of saying the color of hat in front of you could potentially result in EVERYONE getting beheaded, lets say for example the hat placement is red, black, red, black, red, black, red, black....etc do you see how this will just not work, if every one says the color of hat in front of him, it will be wrong all the way down the line, and all will die

[Guest]

The object of this riddle is to try and save as many prisoners as possible, the strategy of saying the color of hat in front of you could potentially result in EVERYONE getting beheaded, lets say for example the hat placement is red, black, red, black, red, black, red, black....etc do you see how this will just not work, if every one says the color of hat in front of him, it will be wrong all the way down the line, and all will die

in the example you mentioned before 11red 9black (or something like that), 11+9=20, however the first guy can only see 19, he can't see the color hat he's wearing. So going with what I talked about before, he guesses his hat is the odd number of hats he sees in front of him. Therefore, if he sees 10 red and 9 black, he guesses red, and the guy ahead of him would know 1. the color the first guy saw as the odd number, and 2. the color of the first guys hat.

I really hope that helps.

[bonanova]

Would calling out the colour of the hat of the person in front of you be considered cheating? The guy at the back of the queue (answer first) has a 50% chance of getting it right? Or would that be considered communication?

Because technically, being able to see the hats in front of you is a form of communication you already ruled out (light).

No it's not considered cheating.

Everyone gets a shot at saving his own neck by guessing [loudly enough that everyone else hears] a color.

The prisoners may employ any strategy that depends only on what each prisoner, in turn, says for a color.

But no other communication is permitted.

Just saying the color of the hat in front of you is perfectly permissible.

But it's a lousy strategy for saving lives.

[Guest]

The person at the back says...

eg. if he sees three people with black hats (sacrificing himself.... aww) in front of him he says bl-A-ck (and guesses his own)and puts the emphasis on the 3rd letter and 3 people in front say black, the person in front sees one person in front of them is red and know that they are red so they say R-ed and the person in front knows that they are red and if there are two people infront with black hats then they say red with no emphasis and so on.....

[Guest]

The person at the back says...

eg. if he sees three people with black hats (sacrificing himself.... aww) in front of him he says bl-A-ck (and guesses his own)and puts the emphasis on the 3rd letter and 3 people in front say black, the person in front sees one person in front of them is red and know that they are red so they say R-ed and the person in front knows that they are red and if there are two people infront with black hats then they say red with no emphasis and so on.....

Or maybe they could just tap on the shoulder of the person in front of them and say "hey buddy, the color of your hat is black" or "Hey dude, your hat is red" I mean, why not? if you dismiss the #1 rule of this riddle "no communication in any way shape or form" (including code) then my theory would work just as well, right?

[Guest]

Hi first of all excuse me because english is not my main language.

i dont read in any place to the king say that the hats will be 50-50 i dont see where its say "it will be 10 red and 10 black" what if the king put only one red?

[bonanova]

Hi first of all excuse me because english is not my main language.

i dont read in any place to the king say that the hats will be 50-50 i dont see where its say "it will be 10 red and 10 black" what if the king put only one red?

Hi AdrianSecci

Welcome to the Den.

You're absolutely correct.

Each hat can be red or black without regard for the colors of the other hats.

[Guest]

The first prisoner says 'Red' if there are an even number of Red hats, and 'Black' if there are an odd number of red hats among all the other prisoners. He has a 50% that this happens to match his own hat color.

After that, each subsequent prisoner can deduce from the original odd / even number of red hats, the answers he has already heard, and the odd / even state of the hats in front of him what his hat color must be.

I think I have a solution for guaranteeing 19 free with the first prisoner having a 50% chance. It relies on the assumption that each prisoner is able to hear all the answers of those answered previously, but does not rely on loudness of voice, etc.

Edited August 15, 2008 by ShawnInToronto

[Guest]

White or Black ....

Both is a Bi-syllable word....

Which can be said in 2 ways....

Black can be said simply Black - Which means the next one has a Black hat too or

Black can be said Bl-ack (ack in a higher tone) which means the next one has White.

and

White can be said simply White - Which means the next one has a White hat too or

White can be said Whi-ite (ack in a higher tone) which means the next one has Black.

In short, if the ending Tone is High, the next one has the other color. This will ensure at least 19 will be saved

[Guest]

IF the last guy can only answer red or black, answer has to be "red or black"

[Guest]

19 prisoners could be set free if everyone wore a mirror or some type of reflective material on their back. Prisoners 1-19 would be able see the color of the hat that they were wearing and answer correctly. The 20th prisoner(person in the front)would have to guess.

[Guest]

bonanova that was genius

[Guest]

this method is very similar to the others' solution but this would be easier to hear, remember and calculate, especially for the prisoners upfront.

count how many times black was said and add the number black hats in front of you. completely disregarding of p20's answer for his own hat color.

*p20 = prisoner number 20 at the end of the line that has the chance to count how many black hats there are.

p20 will count black hats and say the code for even or odd number of black hats he has counted.

color code:

if even = red

if odd = black

prisoners count how many times black has been answered, when it's their turn, they then add the number of the black hats in front of them.

For example:. p11 has heard black 5 times (not including hearing p20's "black" because p11 is judging the odd and the even from p20's point of view) and in front of p11 are 6 prisoners with black hats. 5+6=11 > odd.

logically, since p20 seen an odd number of black hats and p11 heard and seen the rest of the blacks, p11 cant have a a black one as well (or else p20 would've seen an even number of black hats). he has to answer red then for his hat.

if it adds up to even, then he has to have the remaining black hat to make the sum of odd number of black hats.

p20's purpose is purely set on determining the code of how many black hats he saw and counted from all the prisoners. whether he has a red or a black one is irrelevant to the other prisoners.

my note: spent 3 hours thinking on this, so i hope it at least makes sense. i didn't try exchanging the colors for the odd and even codes but i doubt it would make a difference to the outcome, it's only lucky for p20 to have to say the color code that matches his own hat color. cheers.

[Guest]

There are so many answers which have been said to be "right" or "close to right" i'm confused... which is the right answer? at least the most right answer so far? You can just point me to whose post

If all the men decide the following, 19 out of 20 can be saved for certain:

They will pause more than 5 seconds to say their hat color if the one immediately in front of them is wearing black. If red, they must say their own hat color within 3 seconds.

Now the way the 19th person knows his hat color is that the 20th says it. The 20th one has nothing to lose since he has 50% chance either way.

Suppose 19th has a red hat, 18th black and 17th red.

1. The 20th person says the colour on the hat of the 19th. ie red

2. 19th knows his hat is red, so he waits >5 sec and says red (this saves his life and tells the next person the color of his hat)

3. Since the 19th person took more than 5 secs to say, the 18th knows his is black, but since the 17th one has red, he says black quickly before 3 sec and so on...

[Guest]

They could look into the eyes of the guard standing in front of them to see the color of their own hat

[Guest]

[i am certain that the prisoners are not allowed to mumble or mutter any other word than "black" or "red". Kings are NOT that stupid. Chances are he'll be looking for reasons to kill anyways; and to bring about all the prisoners failure, and demise.]

You could save up to 10 individuals I think, if not more, as long as 10 other individuals (the other half of the group) volunteered and swore to say the color of the hat of the person in front of them in line (this still gives the volunteer a 50/50 chance of survival as at first, but at least in this manner he guarantees the survival of another, which already improves the odds of the pack greatly.)

*note: they'd have to cue in line in the following manner: volunteer-survivor-volunteer-survivor-....

Also, something to keep in mind: if this King is ruthless, and strives on the misery of others, if too many get it right, he'll probably choose to kill them all anyways, because he finds the situation extremely embarrassing for a man in his position, and thinks his power has been put in question. So the prisoner's would have to think of conning him somehow- not only how to figure out the color of their hats.

[Guest]

in the example you mentioned before 11red 9black (or something like that), 11+9=20, however the first guy can only see 19, he can't see the color hat he's wearing. So going with what I talked about before, he guesses his hat is the odd number of hats he sees in front of him. Therefore, if he sees 10 red and 9 black, he guesses red, and the guy ahead of him would know 1. the color the first guy saw as the odd number, and 2. the color of the first guys hat.

I really hope that helps.

Except, your assuming every one of the prisoners are intelligent beings, with perfect hearing, and perfect sight in any circumstance. What if, say, they're questioned in a loud, crowded, angry mob area? Or if a few guys down the line, mumble from fear of not having calculated even, odd, even, odd correctly (these men are in a slightly traumatizing situation: mistakes do occur, so the 20th guy down the line, will have to keep up with "even, odd...", anybody's accidental mistakes...).

Nevertheless, it's not a bad solution of course. The odds are though, that many wouldn't survive, and that most that do, will be the first one's to be questioned, not the last.

[Guest]

You assume that the prisoners can hear the guesses.

But this violates the rule: "You will not be allowed to look back or communicate together in any way (talking, touching.....)."

In other words, the prisoners must answer silently.

Sorry. Half will die. Or more, depending on the King's whims...

tOM

[Guest]

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?