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.

[bonanova]

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

This "solution" is amazingly seductive!

It continues to be posted by people who don't even check to see whether it works.

[wolfgang]

Hello....I didn`t read all the answers.but if we concider the colors as 0 and 1

now let us take any random possibilty...e.g

00111000111001110011

the first one(0)has 50% survival chance,,but he will say the color seeing in the front of him,,,in this case (0)

the second one (he knew now his color),at the same time he saw the color in front of him (1),which is different color

so he will wait shortly then he`ll say his color(0).

the 3rd(is sure now that he has (1),because the 2nd didn`t said immediatly,,0).

and as the person infront of him has also (1)in this example,so he will say his color(1) immediatly!

and so on!

so...

1st....(o)

2nd.............(0)

3rd....(1)

4th....(1)

5th.............(1)

6th....(0)

[Guest]

Most people here make a big mistake.The thought that the before guy tells the front's man color is really good...but if everyone tells his front mans color...who tells his color?This plans leaves everything to luck.According to me, the half are guarranted to survive and the other ones will be saved only by luck.My answer is that the prisoner 20 tells the front color.The 19 tells his color.The 18 tells front color.the 17 tells his color.With this plan numbers 19,17,15,13,11,9,7,5,3,1 will be saved by listening their color from the back guy.All the others 20,18,16,12,10,8,6,4,2 will be saved if they get lucky and their hat is the same color with the fronts hat

[Guest]

19 guaranteed to survive if none of them deaf or dumb or blind and correctly follow the rules.

Evey one in the row immediately counts number of Black hats in front of them (so, also red).

Last person acts sacrificial - he shouts "black" if there are odd blacks in front of him. or shouts "red" if there are even blacks (including 0) in front of him. It is signal for others to save themselves from there on.

Lets say 20th shouted BLACK (odd) :

19th person counts the number of blacks and if it is odd, then he knows he must have red hat because 20th didnt count him as black. If he sees even blacks, then his color is also black (so it adds up to odd). He shouts HIS color.

18th: He keeps track of 19th color as well 1-17th and deduce his color based on 20th's clue.

17th: He keeps track of 19-18th as well as 1-16th and considers 20th's clue to deduce his color.

... so on till the 1st person deduce his.

However, if i did read correctly, there is nothing stopping someone to take his hat off or try peek into it at strange angles or reflection etc. [They might not able to see while it was placed on head but no rules to say they shouldn't try to see their color themselves]. They should all shake their heads, get the hat down and ask the king politely if he would put it back

Edited October 18, 2010 by aaronbcj

[Guest]

Thanks .. gr8 question ...

the most simplest solution itself will free 10 people .. alternate guys telling color of hat of person standing in front of him ...

but this one frees 19 people for sure ... ....

u could substitute hat colors with binary value 0 and binary value 1

[Guest]

I have one small question, I may not have understand the riddle properly.

Is it assumed that there is an even number of black and red hats, or does it not matter??

[Guest]

Is it assumed that there is an even number of black and red hats, or does it not matter??

It doesn't matter ...

[Guest]

Hello....I didn`t read all the answers.but if we concider the colors as 0 and 1

now let us take any random possibilty...e.g

00111000111001110011

the first one(0)has 50% survival chance,,but he will say the color seeing in the front of him,,,in this case (0)

the second one (he knew now his color),at the same time he saw the color in front of him (1),which is different color

so he will wait shortly then he`ll say his color(0).

the 3rd(is sure now that he has (1),because the 2nd didn`t said immediatly,,0).

and as the person infront of him has also (1)in this example,so he will say his color(1) immediatly!

and so on!

so...

1st....(o)

2nd.............(0)

3rd....(1)

4th....(1)

5th.............(1)

6th....(0)

I believe , the question meant the prisoners will not be able to communicate by nothing other than saying the hat colour .. Not even by silence also ....

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

This is nice except I did not read anywhere in the original puzzle that there had to be the same number of black or red hats. Just that everyone could see the hats in front of them. If all the hats were red, or all but one, or all but two etc, that would ruin any attempt at signaling those ahead of you.

[Molly Mae]

This is nice except I did not read anywhere in the original puzzle that there had to be the same number of black or red hats. Just that everyone could see the hats in front of them. If all the hats were red, or all but one, or all but two etc, that would ruin any attempt at signaling those ahead of you.

The solution doesn't relate the number of black hats to red hats, but each colour to an odd or even number. I think that's the biggest problem people have with understanding this riddle. The solution takes into account any situation: be it 20 black hats, 20 red hats, or any other combination.

[Guest]

Yayyy after several hours pulling my hair I finally solved this very interesting puzzle:

The 1st man counts the number of red hats (or black hats if you dislike red color )

If the number of red hats is odd, then 1st man says "red"

If the number of red hats is even, then 1st man says "black"

(or vice versa, up to you)

And that's it! From then the 2nd up to the last man in the row can figure out what is the color of his hat.

It's quite shocking to me how simple it is... At first I came up with methods like subtracting/dividing berween red and black hat, but some problems emerged . But in the end it all boils down to odd/even, because with the mere signal of Black/Red it's the only feasible way that works for any type of distribution of hat colors.

PS. Have fun guys. And please forgive my bad English

[Guest]

I thought of a solution right away that would save 19 definately, and maybe the first one. It has nothing to do with math.

The first guy says the color of the hat of the man in front of him. He has a 50% chance of it being his own color. The next man says the color of his own hat as indicated by the man behind him. But when he states the color, he will either say it as a statement, or with the inflection of a question. So if man number 2 says "black?" with his voice rising as if asking a question, man number three knows his own hat is red. If man number 2 says "Black!", man number 3 knows his hat is black. Kinda funky, but it would work....

[Guest]

There are 3 possible answers : 1. ''BLACK'' or ''RED''

2. BLACK

3. RED

The outcome of each answer will be as follows:

1. If the 20th man answers ''BLACK'' or ''RED'' all will be freed as per the statement. Any other reply apart from

black, red and ''Black or Red - all prisoners will be executed.

2. When the answer is 'black' and if it turns out to be correct, his life will be spared but not the lives of the remaining

19 prisoners. If this answer is wrong, then he will be executed and the next man (19th) will face the question and so on.

3. When the answer is 'red', the results will be same as in 2 ( same as above ).

The conclusion is : any one answers ''BLACK''or ''RED'' , then all the remaining prisoners will be freed.

[Guest]

I thought of a solution right away that would save 19 definately, and maybe the first one. It has nothing to do with math.

The first guy says the color of the hat of the man in front of him. He has a 50% chance of it being his own color. The next man says the color of his own hat as indicated by the man behind him. But when he states the color, he will either say it as a statement, or with the inflection of a question. So if man number 2 says "black?" with his voice rising as if asking a question, man number three knows his own hat is red. If man number 2 says "Black!", man number 3 knows his hat is black. Kinda funky, but it would work....

I believe that the solution posted by Bononova is very gracious to the 20 death row inmates assuming that they are all capable of counting and determining odd or even and then making logical decisions based on that information, it may be a bit much for them to go through, especially under a tense situation like this. I believe Mrs. Magoo's solution to be the best answer and it is one that I also thought of within about 2 minutes of reading the riddle. Guarantees 19 are saved and the 20th still has a 50/50 chance. Very simple riddle.

[Guest]

There are 3 possible answers : 1. ''BLACK'' or ''RED''

2. BLACK

3. RED

The outcome of each answer will be as follows:

1. If the 20th man answers ''BLACK'' or ''RED'' all will be freed as per the statement. Any other reply apart from

black, red and ''Black or Red - all prisoners will be executed.

2. When the answer is 'black' and if it turns out to be correct, his life will be spared but not the lives of the remaining

19 prisoners. If this answer is wrong, then he will be executed and the next man (19th) will face the question and so on.

3. When the answer is 'red', the results will be same as in 2 ( same as above ).

The conclusion is : any one answers ''BLACK''or ''RED'' , then all the remaining prisoners will be freed.

He is not allowed to answer "Black or Red". If you notice in the puzzle it states they are only allowed to answer "Black" or "Red". Since these words are individually in quotation that means that answering with both would immediately result in the death of all the prisoners since they are only allowed to say one of the words and nothing else.

Edited January 20, 2011 by TheJMan211

[Guest]

I might be going out on a limb here, but the best solution would be for the group to decide that the person beeing asked about the colour of his/her hat to simply state the colour of the hat of the person in front. Then there's no need to determine odd or even number of hats in front. The life of the first guy, assuming the king does not have 10 hats of each colour, is still a coin toss however. The solution also assumes that all hats in front are visible.

[bonanova]

I might be going out on a limb here, but the best solution would be for the group to decide that the person beeing asked about the colour of his/her hat to simply state the colour of the hat of the person in front. Then there's no need to determine odd or even number of hats in front. The life of the first guy, assuming the king does not have 10 hats of each colour, is still a coin toss however. The solution also assumes that all hats in front are visible.

Hi 1up, and welcome to the Den.

How many prisoners will be saved in your scenario?

Is it a better result than 19?

[Faizaan]

Wow, I haven't been here forever... and since I've replied to this topic before, I've gotten about 30 (checks) 160 emails notifying me of replies to the topic. Anyways, this bombardment of emails has driven me to come back, if only for this one post.

So...

Considering all other factors/variables are constant:

Black heats up much faster than Red. The knowledge of this fact can increase the chances of the first-prisoner-to-answer's survival. Since the prisoner must not answer immediately (at least this was not stated in the OP) he can wait. If his head starts to heat up relatively quickly, he can assume that he has a black hat. Also, for good measure, the second-in-line prisoner can start to breathe heavily when his head starts heating up. I #1's head is getting hot at about the same time as #2's, and #2 has a black hat, #1 can assume he has a black hat. If #1's head gets hot quicker than #2's, and #2 has a red hat, #1 has a black hat again.

All the prisoners can do one of two things typically done before giving an important answer. This will notify the next prisoner of his hat color. The prisoner can either sigh (to signal red) or clear their throat (to signal black) before saying his hat color.

I think this gives 19 people a definite survival and one person an 80-90% chance of survival.

[bonanova]

Wow, I haven't been here forever... and since I've replied to this topic before, I've gotten about 30 (checks) 160 emails notifying me of replies to the topic. Anyways, this bombardment of emails has driven me to come back, if only for this one post.

So...

Considering all other factors/variables are constant:

Black heats up much faster than Red. The knowledge of this fact can increase the chances of the first-prisoner-to-answer's survival. Since the prisoner must not answer immediately (at least this was not stated in the OP) he can wait. If his head starts to heat up relatively quickly, he can assume that he has a black hat. Also, for good measure, the second-in-line prisoner can start to breathe heavily when his head starts heating up. I #1's head is getting hot at about the same time as #2's, and #2 has a black hat, #1 can assume he has a black hat. If #1's head gets hot quicker than #2's, and #2 has a red hat, #1 has a black hat again.

All the prisoners can do one of two things typically done before giving an important answer. This will notify the next prisoner of his hat color. The prisoner can either sigh (to signal red) or clear their throat (to signal black) before saying his hat color.

I think this gives 19 people a definite survival and one person an 80-90% chance of survival.

Black hats also

radiate more efficiently than red hats, so they also cool off faster ...

[Faizaan]

Black hats also

radiate more efficiently than red hats, so they also cool off faster ...

...by radiating/conducting the heat away to the air around it and the air inside it (the hat), which would heat up your head, no?

I'm not a whiz at Physics yet, so if I'm missing an important point... well, let me know.

[bonanova]

...by radiating/conducting the heat away to the air around it and the air inside it (the hat), which would heat up your head, no?

I'm not a whiz at Physics yet, so if I'm missing an important point... well, let me know.

It depends.

A black object will radiate to and absorb from its surroundings, eventually reaching the same temperature.

That is also true of a red object. The difference is that a black object will do it more quickly.

The slowest to equilibrate with their surroundings are white or reflective objects.

That's why igloos sustain elevated interior temperatures, and shiny coffee pots keep their contents warm.

If the prisoners' ambience is warmer than body temperature, a black hat will more quickly feel warm than will a red hat.

Similarly it will more quickly feel cool than will a red hat, if the ambient temperature is below body temperature.

But for this to be a life-saving color indicator, the head of each prisoner would have to have excellent temperature acuity,

and each prisoner would have to know how fast a red hat would equilibrate, in order to know whether his [black?] hat had equilibrated more quickly.

But even this would not suffice if the ambient temperature were the same as the prisoners' body temperature, or close to it.

Then there would be no warming or cooling to perceive.

And we haven't even touched on other mitigating factors related to temperature such as varying amounts of perspiration,

a likely prospect for persons facing execution, if, as it evaporated, it cooled a prisoner's head more efficiently than a black hat might warm it.

By comparison, keeping track of running parity seems simple and reliable.

Isn't it the method you would choose?

[Guest]

I think bonanova's solution is brilliant....too brilliant. It's too easy to screw it up when your life is on the line. Why not just speak loudly if the guy in front of you has a red hat and softly if he has a black hat. I don't see anything in the wording of the problem to exclude this answer. Atleast 19 survive...reliably.

Has this answer already been given?

[bonanova]

I think bonanova's solution is brilliant....too brilliant. It's too easy to screw it up when your life is on the line. Why not just speak loudly if the guy in front of you has a red hat and softly if he has a black hat. I don't see anything in the wording of the problem to exclude this answer. Atleast 19 survive...reliably.

Has this answer already been given?

Yes, this answer and variants have been given.

I agree that this is a good "engineering" solution, being an engineer myself, I must agree that it works, and in the real world that's really all that matters.

The OP leaves us with only this restriction on the solution, and it's ambiguous enough, IMHO to admit this one. namely,

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

It's clear to some of the problem solvers, but not to all, that the intent is to give a binary response, not embellished by differences in tone, loudness, time delay, voice pitch, or ... well or anything else. To other solvers, these embellishments are permitted, and the response is no longer binary. So there are two classes of solutions. Yours belongs to the latter.

Welcome to the Den!

[Guest]

It seems the answer is already here, but i'll throw in my opinion ( too lazy to read 43 pages of posts for the right one )

since you have a binary choice(black or red), think binary ( computer programmers might understand this a lot easier ).

Consider black as value 0, and red as value 1.

The last guy sees all the 19 in front. He will add these values and come up with a sum. Take the sum, divide it by 2 and take the remainder. If the remainder is 0 he will say black, if the remainder is 1, he will say red. This guy has a 50% chance to live. All others will walk away free if they follow this rule ( checksum principle).

They can hear what the guy before them said, and what the last guy said. Each prisoner will hear the first sum, and he can calculate the sum of the hats before him. All he has to do is subtract the 2 and he will obtain 0 or 1 which will give him the color of his hat.

The guy in front of him will then take that into account, and estimate the last sum before him, and from that , subtract the sum he obtained from the guys in front of him.

[Guest]

When i read the hats on death row text, I didn't assume that there would be an even number of hats distributed ie 10 black 10 red. So on that basis, I thought that the first guy could say what colour the third guy had on his head. The second guy could say the fourth. Then the 3rd guy goes free, so does the fourth and the cycle begins again with the fifth saying the 7th etc.

Can i first say, i'm a new poster so forgive me if i make some assumptions or mistakes and please feel free to point em out.

A lot of sacrifices in my solution!

Edited February 13, 2011 by Graciemay