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]

red = 0 black = 1 prisoner 20: total the number before him and announce.(red for even, black for odd) his life is a gamble in all cases... prisoner 19: total the sum in front of him and decide his color and announce.. all the rest keep track of the score and save their live..

you can speak color only not no

how ever you can save 19 for sure and the first one is on his own

one way is

Color Volume/Pitch... Infrence

RED high I SEE RED HAT

RED low I SEE BALCK HAT

BLACK high I SEE BLACK HAT

BLACK low I SEE RED HAT

so if i hear loud red then i will speak red in low volume and if i see BLACK else i will also speak RED loudly

so if i hear low volume red then i will speak BLACK high volume and if i see BLACK else i will also speak BLACK in low volume

.......

[Guest]

bonanova's reply is quite good but there can be a slight difficulty to prisoners to count no. of hats in front of them, may be if prisoners in front of him are of uneven height or any thing like that.

I have got 1 more solution and would like to ask you people if that can be feasible, though i think it is.

The last person (20th) is surely a coin toss and its his luck if he is saved or not. Every person will tell the person in front of them the color of their hat, in such a way that king doesnt notice. Lets keep a code of 'RED' and 'BLACK' in the tone of voice. To tell that color is 'RED', speak in a loud voice, and to tell that color is 'BLACK', speak in lower tone. So the perosn in front will have to notice just the tone in which the person behind him is speaking and not the color he is saying.

Exmaple: If 19th person has RED hat, than 20th person will say the-guess-of-his-own hat's color in loud voice so that 19th person comes to know that he has RED hat on his head. Now if 18th person has BLACK hat, then 19th person will say RED (his own hat color) in lower tone (to notify 18th person that he has balck hat on his head).

This will go on and lives of 19 people can be saved surely.

Howz dat?

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

so cool

[Guest]

its lack of information.. you should list how many red hat, how many black hat..

if we dont have that number, it could be all red or all black.

[Guest]

Here is the bulletproof solution to save 19 prisoners with a probability of 50% that the 20th prisoner would also be safe. Since there are only two colors, and total of 19 hats, either of the two color hats has to be an odd number. So the 20th prisoner would count the number of red color hats that other 19 prisoners are wearing. If the number of red hats are odd, he would speak red and I am assuming every other prisoner can listen to what he said. Now, the 19th prisoner would count the no. of red hats in front of him, and if he finds it to be an even no., then surely he is wearing a red hat otherwise a blue. Accordingly he would speak out the color of his hat and the other 18 prisoners would listen to it. Thus the chain would continue and every one would keep telling the color of their hats.

[Guest]

I think that there is a way to save all 20 people... 19 are saved for sure.

To save 19 is easy: if the last one sacrifice himself, he could just say the color of the hat in front of him (the 19th). So the 19th prisoner will just know which color is his.

BUT, we also know that the king is evil, so the king will probably know that the last guy will use this trick to save the 19 in front of him.

In this way, the king will put color A to the 20th prisoner and B to 19th, expecting the 20th to say the color of the 19th.

IF we invert the spoken color, the king would be tricked - or at least the last prisoner survive with 50% chance as usually.

So, if 20th has hat of color X and 19th has color B, the 20th will just say "not B", (that is A).

If the king is really evil, the 20th is saved, because - as we all know - evil is stupid and the king won't think about this option

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

...But the riddle states: "He will be only allowed to answer “BLACK” or “RED”. If he says anything else you will ALL be executed immediately."

So that wouldn't work.

[roolstar]

...

To save 19 is easy: if the last one sacrifice himself, he could just say the color of the hat in front of him (the 19th). So the 19th prisoner will just know which color is his.

...

Not that easy...

Rethink your logic with an example and you will see the gap. (prisoner 18 will be in the same situation as prisoner 20 all over again...

However, your system is smart regarding the inverting of hats colors and may increase the chances of prisoners getting saved (a bit more than the 15 average of your method)

Edited October 21, 2009 by roolstar

[Guest]

I don’t know about the algorithms involved but how I see about the easiest way to solve this is this way:

The first person who will be asked (the last person at the queue who can see the hats of all those in front of him) has the 50-50 chance.

If he gets the color right for himself (which will be a guess), 19 people will be saved. If he gets it wrong, all 19 will be dead.

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

Here’s how to have that chance.

The night before the death row, they will discuss that the person who can see the hat in front of him will mention it’s color. So if he sees black hat in front of him, he will say “BLACK”. This is a signal to the person in front of him that his hat is colored black. But this is tricky. If the next person was signalled what color his hat is, he should say black so he can save himself. However, he should give the signal to the next person on what color the next person’s hat is. If he knows that his hat is black, then the person in front of him has a red hat, this is a problem. The solution is that he should have a strategy in saying the color of his hat. He can say long “BLAAACK” which they can discuss would signal to the next person that the next person’s hat is “red” and at the same time he said “black” as the answer to his own hat’s color. If the next person’s hat color is black as same as his, then he can just plainly say “BLACK”. Next turn, if the person knows his hat is red, he can say the long “REEEED” which will signal that the person’s hat in front of him is not red but black.

Edited October 24, 2009 by Sunkissed

[Guest]

I saw lots of right answers, but none that really simplified the problem to the point where it is something I would expect 5th graders to be able to line up and act out. So here is my attempt.

1. Prisoners agree on a number value for each color. Let's say 1 for black and 0 for red. They also agree on a parity value for each color that must match the number value. So since Black is worth 1 point and 1 is odd, then black also means odd. Likewise, red also means even.

2. Prisoner number one looks at the hats in front of him and adds them up using the number value of their colors. He then determines the parity value of the sum and calls out its corresponding color. If he sees 7 red hats and 12 red hats, the sum is 7, which is odd, so he will call out Black.

3. Prisoner number two looks at the hats in front of him and adds them up using their number values. He then determines the parity color of what he sees and compares it to the parity called called out by Prisoner 1. If the parities are the same, he is wearing the even parity hat (red). If different, his hat is odd.

4. For each subsequent prisoner, the trick is to listen to all colors named before him and keep track of the parity number. They will compare the parity number of the guesses they heard to the parity number of what they can see. If the two are the same, his they are wearing an even-parity (red) hat. If they are different, they are wearing an odd-parity hat.

Example: I am prisoner six. The five guesses I heard were: Black, Red, Red, Black, Black. They have a sum of 3 which is odd. Now I look at the 14 hats in front of me. I see 8 red and 6 black which have a sum of 6 or even. I am therefore wearing a black hat since the two parities are different.

As correctly stated, 19 prisoners can be saved and the first has a 50% chance of guessing correctly.

[Guest]

First of all, I agree with the solution of a surviving 19 prisoners and the last one having the 50% of living. But I think you're all over thinking your methods.

A simple solution I would choose would be to assign the left and right shoulders of each person a colour. Let's say the right shoulder would be red and the left one would be black. The last person (20) would place their hand on whichever colour hat the person in front had and so on and so forth. In this way, every person would know what colour hat they had by which shoulder the person behind them placed their hand upon (with the obvious exception of the last person who would have no one behind him and leaving him with the choice of guessing).

[Guest]

I don't know if a solution has been found yet - but I'm going to give it a shot.

The odd/even theory can't be correct, in the puzzle itself it didn't mention that there would be an equal number of red or black hats - only that all prisoners would be given a hat that would be either black or red. So there could even be 19 black hats and only one red for example. There is no way for the first guesser to know for sure the color of his hat simply by looking at everyone elses.

So it has to do with the communication the night before. Maybe I'm overthinking this - but I have a theory that would work depending on the circumstances of the row. If the prisoners are positioned close enough together the 19th person must be wearing glasses with metal frames, or attach something that is a tiny bit reflective to the part of the frames that goes behind his ear - anything just enough to show a slight reflection for the 1st guesser to KNOW what color his hat is. From there on it would simply be communication.

If the first guessers hat is red and the person in front of his is also red, he would simply say "Red" however if his is red and the person in front is black he would have to say "RRed" as though he is not sure but only guessing. The hesitation would be a hint for the next person that his hat is NOT the color that was said. And so on - however, the king may pick up on the pattern

So there would have to be differences in the hints. For example other than hesitation to indicate the person in fronts hat is different than your own they could have have extra definite ending sounds "reddd" "blackkk" the key would be if the person in front has the same to always say with confidence and not dragging any sounds just "red" or "black" ... Then it would just be up to the prisoners not to say it wrong or hear it wrong!!

I don't know lol - but without knowing how many of each color that's what I came up with.

[Guest]

“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…

The puzzle can be improved. One can use N color for hats. This is little harder in solution, but if you solved such puzzle you will completly undrstand situation. That's why I like puzzle with N types of hats more.

P.S. Too many spoilers (which are not hidden) in this thread - can someone clean it?

Edited January 2, 2010 by alanklm

[Guest]

What's about numbers of the hats? How many black and how many red hats there? because you can have 13 black and 7 red, then what's gonna happen?

[Guest]

What's about numbers of the hats? How many black and how many red hats there? because you can have 13 black and 7 red, then what's gonna happen?

Any possible numbers - (0,20) - (10,10)

[Guest]

all the answers are very good and exactly what I thought, but has anyone thought about that an executioners hat is always black. What if the warden didn't actually change the color. I mean he seems very sadistic to do such a thing. So if inmate # 20 sees that all the others have a black hat it would be almost a given that his hat is black as well.

[Guest]

the first prisoner is again a coin toss, he just has to look forward.

If he sees a red hat, he shouts either black or red very loud.

The prisoners have told eachother that if you hear the guy behind you shout very hard, than you have a red hat.

if he speaks normally than the guy in front of him is wearing a black hat.

This way everyone can say the color of his own hat AND let the guy in front of him know wich color hat he has.

And i think its a lot easier to remember than the odd/even solution.

i think i have another solution which could also save 19 prisoners. (possibly 20)

[Guest]

All of the respondents seem to be ignoring the rule that if any one person guesses wrong then *all* will be executed. So, if the first person guesses wrong - which is 50/50, then NONE survive. No guarantee exists.

[Guest]

The first person is a 50/50 proposition, we've established that. His job will be to establish how many "black" hats there are. He will say BLACK if there are an odd number of black hats, and RED if it's even. Here's how it will work: If the second guy hear's BLACK and he sees an even amount of black hats in front of him, he knows his hat must be black because odd changed to even. By alternating whether the black hats remaining are odd or even, each person should be able to determine what his color hat is, by counting the remaining hats. So the first time you hear BLACK, it indicates an odd number of black hats, but next time switches to even, and back and forth. Make sense?

[Guest]

i understood the logic of the answer but in theory i couldnt work it out easily in my head, until i shuffled it round a bit. i found it easier doin it this way. anyone else agree.

given the answer, i still had to figure it out my own way. thats what makes the difference between just knowing and understanding the answer.

Replace ODD & EVEN with 1 & 2

so..

black = 1

red = 2

then, to find out your color hat, do as follows...

add up the sum of the odd and even numbers (red&blacks) before your turn.

if the answer is an ODD number then your hat will be black, if EVEN it will be red.

(ps this is my 1st time answering, i know its an old one but would appreciate any feedback.esp if this answer made it easy to understand. i stared at my computer screen for an hour to find the easiest way to understand this problem. if i was a prisoner i wouldve got everyone killed so i owed it to everyone to understand. ta)

[Guest]

All of the respondents seem to be ignoring the rule that if any one person guesses wrong then *all* will be executed. So, if the first person guesses wrong - which is 50/50, then NONE survive. No guarantee exists.

no. there is the fact that if the first prisoner guesses wrong he will be executed. maybe, straight away. even if u couldnt turn around u may hear a deathly scream. or atleast a gunshot. thats how i see it. i think it mentions that in the original riddle - that if they answer wrong or say anyhting other than the right answer, then they will be executed.

this is the only clue to the rest of them to whether the first man is right or not. his death. so the man with the fisrt right answer starts off the lucky run. so a maximum of 20 can be saved but only if the first guy is right (lucky) with his 50/50 guess.

[Guest]

Wonderful riddle, succinct and simple solution. Can't believe it took me two hours to get it.

The man at the end counts the number of red hats and says "Red" if there is an even number of red hats, and "Black" if there is an odd number.

If even, the next man counts the number of red hats he sees, if he sees an even amount he knows he wears a Black hat, because the man behind him also saw an even amount and so he says "Black", if there is an odd amount he knows he wears a Red hat because the man behind him saw an even amount, which means that an odd + him = even amount, and so he says "Red". All the other prisoners then know that there is an odd number of red hats remaining. It continues like this until the last guy who knows that if there is an even number of red hats remaining, he is wearing a black hat, if there is an odd number of red hats remaining, he is wearing a red hat.

The same can be said if the first man says "odd".

Edited July 28, 2010 by Chaknow

[Guest]

Wonderful riddle, succinct and simple solution. Can't believe it took me two hours to get it.

The man at the end counts the number of red hats and says "Red" if there is an even number of red hats, and "Black" if there is an odd number.

If even, the next man counts the number of red hats he sees, if he sees an even amount he knows he wears a Black hat, because the man behind him also saw an even amount and so he says "Black", if there is an odd amount he knows he wears a Red hat because the man behind him saw an even amount, which means that an odd + him = even amount, and so he says "Red". All the other prisoners then know that there is an odd number of red hats remaining. It continues like this until the last guy who knows that if there is an even number of red hats remaining, he is wearing a black hat, if there is an odd number of red hats remaining, he is wearing a red hat.

The same can be said if the first man says "odd".

but if the 2nd person says red,that means there are even number of red hats.

solution is not correct bro.!

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

[Guest]

Answer to Hats on death row...begins with the first person to "state" the color of hat he thinks he is wearing...instead he says the color of the hat in front of him, then every other will be saved unless his hat is the same color as the person in front of him, then he would be spared too.

. Think of sacrifice...