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]

Which prisoner will say Red?

You are right! I read it again and it makes sense. Great work.

[Guest]

Ahh i only managed to have 10 people survive

i did it so that whoever is an even number would die since they told the person infront of them what the color of their hat is guarenteing their life. And then the odd numbered person would be able to say the colour of his own hat with certainty........ ofcourse this is replying upon the fact that the even numbered people wont lie on purpose.

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

thats what I came up with too

[Guest]

but how do we know there is an even number of black and red hats

there could be only one red hat and nineteen black hats.

the king never said there was only 10 black and 10 red

Edited June 14, 2009 by izzyc2

[bonanova]

but how do we know there is an even number of black and red hats

there could be only one red hat and nineteen black hats.

the king never said there was only 10 black and 10 red

Correct. No one said that.

The solution accounts for any distribution.

[Guest]

I still do not understand. How can you tell how many people have black hats, and tell the color of hat at the same time. It is a good idea to help predict, however I do not see how you can say BLACK or RED and specify the number of people who have that in front of you at the same time.

[Guest]

I still do not understand. How can you tell how many people have black hats, and tell the color of hat at the same time. It is a good idea to help predict, however I do not see how you can say BLACK or RED and specify the number of people who have that in front of you at the same time.

You don't, it just says weather it is even or odd, and if the first person says the code word for even, and you see odd, then you're therefore the extra one.

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

In the original scenario, Prisoner N has 50/50 chance of surviving, while prisoners [1, N-1] are 100%

Now:

1) Assume that the king tells prisoner n the hat color truthfully (i.e. the king doesn't say "red" when it is "black")

2) Assume that the execution on an incorrect answer is immediate (i.e. prisoner 10 knows if prisoner 11 said the incorrect answer immediately).

In this scenario, there are two possible outcomes:

In the first outcome, prisoner N is given the hat that matches the parity bit that he was supposed to say. In this case, all N prisoners will survive.

In the second outcome, prisoner N is given the mismatch. He now has two choices:

Prisoner N is can ignore the king and say the correct parity, with 100% chance of death, but 100% chance of 19 survivals.

Or, he can state the incorrect parity, with 100% chance of survival. In this situation, prisoner N-1 is guaranteed to be killed. He is operating on the assumption that the parity given is correct. Since it is incorrect, he will be killed, because he can never have the correct answer. In addition, if we operate on the assumption 2 above (that execution is immediate), prisoner N-2 will know that the parity bit was incorrect and can thus correct the parity, guaranteeing the survival of prisoners [1, N-2].

(examples:)

1 2 3

B R R P4 sees 1, should say "black," but says "red". P3 sees 1, thinks he should say black (BANG). P2 knows "even, switch" should have been "odd, stay", and says red (stay odd)

B R B P4 sees 2, should say "red," but says "black." P3 sees 1, thinks he should say "red" (BANG). P2 knows "odd stay" should have been "even, switch". He sees one and says "red (stay odd)"

B B R P4 sees 2, should say "red" but says "black". P3 sees 2, thinks he should say "Black (BANG). P2 knows "odd switch" should have been "even stay". He sees 1 and says "black (stay even)"

R R B P4 sees 1, should say "black" but says "red". P3 sees 0, thinks he should say "red" BANG. P2 knows that even, stay should have been odd, switch. He sees 0 and says "red (stay even)"

Soo, I would not want to be prisoner N or N-1, because those are the two positions that contain a chance of dying.

In any of the scenarios, we still guarantee (with the assumptions listed above) that at least N-1 prisoners will survive. I don't have time to work out the overall probability, but they can be derived from the above statements if someone wishes to do so

[bonanova]

It's entirely up to the King: 20 are saved or 19 are saved.

Since the OP asks for the number that are guaranteed, that's as far as it goes.

If you want expectation, then it's 20p + 19.5[1-p] where p = probability the king's choice obeys parity.

What value p has, we of course do not know; but if the king acts randomly, the expectation is 19.75.

[Guest]

i wanted to see if could solve this without looking at spoiler.

the first person calls out "red", if he sees an even number of red hats, and black if he sees an even number of black hats.

the next person then would know by looking at the rest whether his hat is red or black.

etc. for example, let's say the arrangement is

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

there are 11 black hats, and 9 red hats.

prisoner 1 will call out black, as he sees 10 black hats.

since prisoner 2 will see odd red as well as odd black, he can conclude that he is wearing a black hat and will say so.

since the first prisoner called out black, and second prisoner called out black, and he sees even red, and odd black,

he can conclude that he is wearing a red hat, as the first person indicated an even number of black, and therefore an odd number of red.

the forth prisoner heard 2 blacks, and sees black is odd, therefore, his hat must be black.

in short, by keeping track of number of calls of red and black, each person can know whether his hat is red or black.

[bonanova]

It's entirely up to the King: 20 are saved or 19 are saved.

Since the OP asks for the number that are guaranteed, that's as far as it goes.

If you want expectation, then it's 20p + 19.5[1-p] where p = probability the king's choice obeys parity.

What value p has, we of course do not know; but if the king acts randomly, the expectation is 19.75.

I have to disagree with my last conclusion.

If the king acts randomly, he communicates no reliable information.

That is, prisoner N could simply imagine the king had acted one way or the other.

That cannot raise the expectation above 19.5.

[Guest]

They could all make an agreement the night before that whomever is at the back of the queue call out the most number of one color that he can see, this way he can surely save a majority of them from being killed... It doesn't say in the riddle that the colors are in a certain order (eg, red, black, red, black etc)... So I guess this would be a more logical way to do it rather than by chance... Thats just my opinion anyway...

[Guest]

19 Prisoners can be guaranteed a stay of exicution and the 20th prisoner has a 50% chance of survival.

Here is my opinion which works out solid:

They could all make an agreement the night before that whomever is at the back of the queue call out the most number of one color that he can see, this way he can surely save a majority of them from being killed... It doesn't say in the riddle that the colors are in a certain order (eg, red, black, red, black etc)... So I guess this would be a more logical way to do it rather than by chance... And they don't know which order they are being put in... Thats just my opinion anyway...

[Guest]

this is the no math system for minimum 19 going free, the guy at the end, poor fellow, it's just not his day

the guy at the end of the line can guess what his is, based on what he sees, so he might live

the rule

the man at the back of the line looks at the hat color of the person directly in front of him

let's say that the person in front of him is wearing a black hat

if he too is going to guess black, he shouts black!

if he is going to guess red then he simply says red

19 says black because they know the color thanks to lucky or unlucky 20

saying only black and not shouting black

this lets #18 know that their hat is not black and is in fact red

this continues down the line till 19-20 people walk free

if anyone has a solution that frees all 20 100% of the time i'm very interested in this method

[Guest]

i tried editing my above post but it no worky

[Guest]

there is a guarentee to save 10 persons, and rest 10..just luck.

As 20th can see all 19..standing before him. so 20th says 1st person hat color, 19th ..2nds; ..18th..3rd, 17th..4th; 16th.. 5th; 15th..6th; 14th..7th; 13th..8th; 12th..9th; 11th..10th. so 10th - 1st able to know their hat colors.

and 20 -11 is luck..so problity in this solution can 50% -10ppl can be saved surely

[Guest]

Amarnath_Caterpillar

The next day 20th person will say the 19th person hat color. So the 20th person has 50% probability of survival. Then 19th person hat color is what 20th prisoner says. Then the 19 prisoner looks at 18 th and says it either loud/slow voice (loud is code assigned for same color and slow is different color)to give a clue to the 18th prisoner about his hat color. In the same way it goes on till number 1 prisoner.

So ffinally 20th prisoner has 50% probability and remaining 19 prisoners will have 100% probability to survive.

[Guest]

19 lives can be saved. The twentieth may "guess" correctly, in which case all would be saved.The prisoners must make a pact, each to inform the prisoner immediately before him, his hat colour.

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

Smart.

[Guest]

How about this as an alternative to bonanova's solution:

For an even number of prisoners, first to speak says color of odd hats. If an odd number of prisoners, add a hat to the end to make it an even number. I'm posting from an iPhone, so I'll leave the rest as previously described.

Edited July 4, 2009 by Bamafan

[Guest]

Probably not - you're only specifying parity of one of the types, not the sequence itself.

If you're interested, there's a simple compression technique called run-length coding;

starting with one of the values, you list the number of consecutive values in the string.

For example, [if red and black became 0 and 1] you might have 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0.

That would reduce to 3 2 1 4 3 1 2 2 1 1 4 2 1 3 2 reducing 32 values to 15.

Run length coding can be very efficient if the "runs" are long [tens or hundreds] but inefficient if there are many runs of length 1 and 2.

Data compression [and encryption] techniques are extremely interesting fields of study.

Check out Wikipedia here and here or do some Google searches on them.

- bn

[Guest]

i think you can save 10 prisoners. #20 will say the color of the hat in front of him. #19 will know his hat color. #18 will say the color in front of him and #17 will know his color. #16 will say the color in front of him and #15 will know his color and so on and so forth. So Numbers 19,17,15,13,11,9,7,5,3and 1 will all know their colors for sure. The rest will have a 50 50 chance

[Guest]

you dont know for sure how many red hats and how many black hats theere are.

[Guest]

Edited July 12, 2009 by thicko

[Guest]

The first guy to speak is the only one taking a chance. He simply says the color of the hat on the guy in front of him so the next guy knows what color hat he's wearing, and so on and so forth.