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.

[Molly Mae]

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

What if the guy behind you says black (indicating that your hat colour is black) but the person in front of you is red?

[Guest]

Some of you guys seem to be missing the point. You cannot guarantee to be saved if you say the color of the person in front of you. In the worst case scenario, every other person is wearing a different color (black, red, black, red, ...). If each person says the color of the person in front of him, then everyone is dead. Although, using this method you can guarantee that 50% will survive (the prisoners standing in the even positions) and the ones in the odd positions have a 50/50 chance, so that's 75%. But the real answer guarantees all will survive except the first one who has a 50% chance. Here how it works:

Before hands the prisoners need to agree that the person at the end of the line counts the red hats in front of him and if even he calls red, and if odd, he calls black. From that point on, everyone needs to keep track of two things:The number of red hats in front, and how many people (aside from the first person) have called red. Then follow this basic logic

If the first person called red and these two numbers are both even or both odd, then call black, otherwise red

If the first person called black and these two numbers are both even or both odd, then call red, otherwise black

Let's go over a simple example to clear this out. Let's say there are 10 prisoners instead of 20 and this is the hat order:

r, b, r, r, b, r, b, b, b, r

The first person sees 4 red hats and calls red (luckily he survives)

Based on the logic above (first line)

The second person sees 4 red hats and 0 other prisoner has called red. Both numbers are even so he calls black

The third person sees 3 red hats and 0 other prisoner has called red. One number is odd and one even, so he calls red

The fourth person sees 2 red hats and 1 other prisoner has called red. One number is odd and one even, so he calls red

The 5th person sees 2 red hats and 2 other prisoners have called red. Both numbers are even so he calls black

The 6th person sees 1 red hat and 2 other prisoners have called red. One number is odd and one even, so he calls red

The 7th person sees 1 red hat and 3 other prisoners have called red. Both numbers are odd so he calls black

The 8th person sees 1 red hat and 3 other prisoners have called red. Both numbers are odd so he calls black

The 9th person sees 1 red hat and 3 other prisoners have called red. Both numbers are odd so he calls black

The 10th person sees 0 red hats and 3 other prisoners have called red. One number is odd and one even, so he calls red

In this case everyone was saved, but the first one was lucky. I'll do another example with odd number of red hats in fron of the first person

r, r, r, b, b, r, b, r, r, b

The first person sees 5 red hats and calls black (dead)

Based on the logic above (second line)

The second person sees 4 red hats and 0 other prisoner has called red. Both numbers are even so he calls red

The third person sees 3 red hats and 1 other prisoner has called red. Both numbers are odd so he calls red

The fourth person sees 3 red hats and 2 other prisoners have called red. One number is odd and one even, so he calls black

The 5th person sees 3 red hats and 2 other prisoners have called red. One number is odd and one even, so he calls black

The 6th person sees 2 red hats and 2 other prisoners have called red. Both numbers are even so he calls red

The 7th person sees 2 red hats and 3 other prisoners have called red. One number is odd and one even, so he calls black

The 8th person sees 1 red hat and 3 other prisoner has called red. Both numbers are odd so he calls red

The 9th person sees 0 red hats and 4 other prisoner has called red. Both numbers are even so he calls red

The 10th person sees 0 red hats and 5 other prisoner has called red. One number is odd and one even, so he calls black

I hope the was clear enough

[Guest]

I'm thinking about this as an information theory problem. It will take 4 bits of information to encode the next 16 possibilities. This means that at best, 16 are saved and 4 have a 50% chance.

[Guest]

like flipping a coin, the answer is a 50/50 guess considering we do not know how many black and red colors are used..

[Molly Mae]

Curious, but what's the best solution for 3 hat colours and 20 prisoners?

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

Yeah, but, you have to guess BEFORE that night. And you can't change your answer after that night.

[Guest]

According to me, The tone of the word plays a major role to save 19 peoples!!! last one can see the one who is standing before him.. Black or red in low tone means the hat is red in color and Black or red in brisk tone the its blacky!!! by this 19 can be saved but worrying for the last one

[Guest]

The people are standing in a single file line, all facing one direction. The person in back is seen by noone. I'd say it's up to a test of memory. The guy in back has to spoit off as many colors, in order, as he possible can and be sent to death. While the people in front of him have to remember the order. When memory fails. It's your turn to spoit off the order of hats. Hopefully saving the maximum amount of people. There's really no solution to save the poor basterd in back. Unless he takes his chances with a 50\50 guess. Thus leaving the person in front of him with the same chances...

Edited November 3, 2011 by Laws

[Guest]

Ah... I love the tone idea. good one!

[Guest]

I heard a similar one on khan academy

[Morningstar]

Is this actually still being discussed? It was started at the end of 2007!

[Guest]

easy one come on

19 and 50% for the first

the night before they agree that the first will count lets say the red hats, if the number is odd he will say red, if the number is even he will say black

lets say he says black and dies, the 2nd will cound how many hats he has in front of him. since the 1 said black it means that there is 0,2,4,6,8,10...... red hats, soo the 2nd counts the number of hats in front of him, if he finds an odd number it means that he has a black one if its an even number it means he has a red one . and it continues until the last .

Edited November 23, 2011 by plainglazed

[Guest]

I do have another solution skipping the math. Although, the odd/even solution is quite nice.

I would love to get some feedback on my solution:

The first guy that is being asked, simply tells the color of the man in front of him, if he is lucky he lives, if not, oh well he did it for the team.

Now, the next guy has already heard his color (black or red) and he is guaranteed freedom, but to help the next guy, here is my idea

If his color matches the one in front, he says the color without hesitation, if it's different, he pauses and thinks and then says his color.

The next guy listening, will consider the pause as a negation of the prevoius color and continue this process ...

Good one ?

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

I see but knowing prisoners.....

they will find a way of comminicating the colours through coughing, sneezing etc. this will mean that only one prisoner will have a chance of death resulting if he cooperates the 19 others an almost guarrentted escape

[Guest]

Sorry. I must have missed something in the instructions. This solution only works when there are 10 black hats and 10 red hats. No where in the instructions does it say this. The solution fails if there are different numbers of black and red hats. There could be 19 black hats and 1 red hat.

[Guest]

All 20 prisoners will be freed

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20

Prisoner 20 will start first. Since he can see everyone in front of him, he knows and will shout the color of his hat (if he sees 9 black 10 red that means he is wearing black, and vice versa)

Prisoner 19 will also be able to shout the color of his hat (if he sees 9 black 9 red and prisoner 20 shouted black, that means he is wearing red)

Prisoners 18 to 2 repeat the same steps.

Prisoner 1 having heard all the color shouted before his turn will also know his color (if 9 shouted black and 10 shouted red that means he is black)

[Guest]

Here's my solution, not sure if it's allowed or not...

You can save the 19 ahead of you by stretching out how long you say the color. The guy in the very back (20th in line) would say the color of the individual (19th) in front of him in 1 second. (Red.) He's got the 50-50 chance. The next person, if 18 is red as well, he says it in one second. If not, he counts off the number of people until he sees another red and that's how long it takes him to say "Red." So if the person 3 (number 16) ahead of him has a red hat, he says "Reeeeeed" over 3 seconds. This way, everyone knows counts the number of seconds for the word and knows that if it skips them, they are the opposite color. If you get close to the end and there are 3 people left with red hats and yours is black, you extend it to 4 seconds for saying red, telling the three of them they are all black.

How's this one?

one wrong timing and all are gone !!

[Guest]

1.If the last person is right you say the opposite color if he is wrong you say the same color

2.You all say the same color and hope your right

[vivekkumarjha]

well, nice one

but the slightest mistake and all would be executed

Edited June 13, 2012 by vivekkumarjha

[vivekkumarjha]

Sorry. I must have missed something in the instructions. This solution only works when there are 10 black hats and 10 red hats. No where in the instructions does it say this. The solution fails if there are different numbers of black and red hats. There could be 19 black hats and 1 red hat.

no the solution doesn't fail.

suppose there are 19 black and 1 red hat

then 20th last prisoner shouts black (key word for black being odd)

he does not know his own hats colour so he may or may not be saved

but the 19th prisoner knows that including his hat there are odd number of black hats, now if he sees even black hats, his hats colour is black, but if he sees odd black colours, his hat colour is red

now suppose he sees odd black colour, then he shouts red

the others keep on counting, this red means red is now odd (key word for red being odd)

the others would keep a note of it and carry on like wise

Edited June 13, 2012 by vivekkumarjha

[GaneshJJ]

THE last person can see 19 hats in front of him. 19 is an odd number. So it is the sum of an even and an odd number. Let us assume that there are 12 black and 7 red hats. The Last man will say the color of the hat of which there are even numbers, in this case black.

 

The person in front of him can count the number hats he sees.

CASE 1 - He is wearing a red hat. So he sees 12 black hats and 6 red hats. Since he knows that black hats are in even numbers. He discovers that he's wearing a red hat.

 

CASE 2_ HE is wearing a black hat. So he sees 11 black and 7 red hats. The last guy has told that black hats are in even numbers. 
So he discovers that he is wearing a black hat.

 

Similarly the people in front can find out the color of their hat and thus can save themselves.

 

The last man can either be wearing a red or a black hat. So that is 2 possibilities and he says one color. So he has a 50% chance to live.

 

THANK YOU

[sw121290]

The answer is zero for the following reasons:

 

1. Prisoners are selfish. They will not willingly sacrifice themselves to save the others. The only scenario in which there would be a sacrifice is if the he/she was forced to be the sacrifice. Given there is a one-night time frame and advance technology has not been invented (an era where there is one absolute king?), we can safely assume the impossibility of outside threats (ie. I'll kill your family if you don't sacrifice yourself). Even if such threats were possible, would I be able to trust such a person (see #3). Maybe it'd be better to just screw the answers and hope the other prisoners die.

 

2. Prisoners are stupid. It took me a couple read through to even understand the solution. We have people posting on this forum who claim the solution does not work simply because they misinterpreted it. For this solution to work, the prisoners must first understand the solution, pay full attention in a stressful environment, and keep count of details. One flaw and the entire group dies. It is probably better to just guess with 50/50 chance then to rely on the stupid.

 

3. Distrust among prisoners are common. The solution forces the one in front to depend on the one in back. As we already established, prisoners are selfish. If they the prisoner feels he is confident to live, who is to say he won't betray the person in front due to some past/current grudges? Not only will the back prisoner have this option, the front prisoner may suspect something of the sorts. Worst comes to worst, the distrust leads to the false answer and thereby snowballs everyone to their deaths.

 

4. The solution changes uncertainty into certainty. Thereby, any mistakes in the process can turn the situation into certainly dire and potentially cause more deaths. Therefore, if I were a prisoner, I'd rather "take my chances".

[Rainman]

The answer is zero for the following reasons:

 

1. Prisoners are selfish. They will not willingly sacrifice themselves to save the others. The only scenario in which there would be a sacrifice is if the he/she was forced to be the sacrifice. Given there is a one-night time frame and advance technology has not been invented (an era where there is one absolute king?), we can safely assume the impossibility of outside threats (ie. I'll kill your family if you don't sacrifice yourself). Even if such threats were possible, would I be able to trust such a person (see #3). Maybe it'd be better to just screw the answers and hope the other prisoners die.

 

2. Prisoners are stupid. It took me a couple read through to even understand the solution. We have people posting on this forum who claim the solution does not work simply because they misinterpreted it. For this solution to work, the prisoners must first understand the solution, pay full attention in a stressful environment, and keep count of details. One flaw and the entire group dies. It is probably better to just guess with 50/50 chance then to rely on the stupid.

 

3. Distrust among prisoners are common. The solution forces the one in front to depend on the one in back. As we already established, prisoners are selfish. If they the prisoner feels he is confident to live, who is to say he won't betray the person in front due to some past/current grudges? Not only will the back prisoner have this option, the front prisoner may suspect something of the sorts. Worst comes to worst, the distrust leads to the false answer and thereby snowballs everyone to their deaths.

 

4. The solution changes uncertainty into certainty. Thereby, any mistakes in the process can turn the situation into certainly dire and potentially cause more deaths. Therefore, if I were a prisoner, I'd rather "take my chances".

 

1. Nobody needs to sacrifice himself. The first prisoner to guess has a 50/50 chance of survival, regardless of whether he adheres to the strategy or not. Nothing he can do can improve his chances of survival, so he might as well help the others (not assuming any grudges).

 

2. Well, yes, the average prisoner most likely is more stupid than the average non-prisoner. But this being a math/logic puzzle, aimed at people who are more intelligent than average, the general assumption is that the prisoners would be intelligent enough to understand the solution proposed by the puzzle solver. And anyway, in this fictional setting with a king who likes to toy with his people, it is plausible that these prisoners have survived through similar challenges before and thus are far more intelligent than regular prisoners, through the survival of the fittest.

 

3. I could apply the same argument as for point 2, that this is a math/logic puzzle and we should not assume distrust unless explicity told to do so. And I could also argue that in this fictional world with an oppressive king, the people might have developed more trust towards each other.

 

4. The OP's description of the procedure seems to imply that each prisoner's judgment is carried out before they move on to the next prisoner. So unless you have heard a prisoner die before you (except the first one who might die due to random chance), you would have no reason to assume that a mistake has been made. And again, if we were supposed to account for the possibility of mistakes, we would have been explicitly told to do so, and possibly even have been provided with the exact probability of a mistake being made.

 

5. Finally, even with all that being said, all it takes for one mistake/betrayal to be canceled out is another mistake/betrayal. Maybe the first prisoner intended to betray you, but was too stupid and accidentally gave the "good" answer. So even if the prisoners were indeed selfish, stupid, distrusting, and prone to betrayal, it would boil down to a crap shoot anyway, even if you did follow the strategy. So once the strategy has been proposed, there is really no reason to deviate from it (unless you have heard people dying before you as I mentioned earlier).

[bonanova]

The answer is zero for the following reasons:

 

Hi sw121290, and welcome to the Den.

 

I'm wondering what question you are answering.

Roolstar has asked, "Can you find a way to guarantee the freedom of some prisoners ...?"

 

Technically I guess the question calls for a yes/no answer.

If it's No, then there is no algorithm to discuss -- you cannot find one.

But if, and only if, your answer is Yes, he then asks how good your algorithm is: how many prisoners will it save, with certainty?

 

By answering "zero" are you saying you found an algorithm, and it guarantees the survival of zero prisoners?

It would seem that would require (a) determining with certainty the colors of all the hats (b) communicating to each prisoner the color of his hat and (c ) convincing each prisoner to give the wrong answer. All three of these tasks are formidable. Just to focus on (a), it seems the first prisoner to speak cannot know the color of his hat under any strategy, and so he can't be effectively persuaded to give the wrong answer. That is, it would not be possible to guarantee his answer is wrong.

 

Or by answering "zero" are you saying there are "zero" (no) algorithms that guarantee the lives of even a single prisoner? But several algorithms have been given that guarantee 19 survivors.

 

Or by answering "zero" are you saying that prisoners are dumb, selfish or untrustworthy to the extent that there is "zero probability" that they can or will correctly follow a procedure, even if it gives on average a 97.5% (19/20 + 1/2 x 1/20) instead of 50% survival probability? Selfish prisoners would take those odds, even if it requires them to think.

 

Anyway, and Rainman addressed this, the question isn't about the IQ or character of prisoners; it's about about the effectiveness of algorithms.

 

 

Honorable Mention, anyway, for clearly thinking outside the box!

 

I hope you have some puzzles for us to solve.

Give us a try!

[franz liszt]

"A SACRIFICE MUST BE MADE!!!"