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]

BONANOVA

That works flawlessly, but given the average persons attention span and ability to understand parity, very unlikely. I bet real world scenerio the third guy messes up and ruins it for the rest. But that isn't the question is it, the question was how. I give you a 10, flawless logic.

[bonanova]

... given the average persons attention span and ability to understand parity, very unlikely. I bet real world scenerio the third guy messes up and ruins it for the rest.

This exercise guarantees an attention span ...

[Guest]

My solution will be to signal with a loud reply if the person in front is having RED, else reply at a lower voice if the person in front is having BLACK. Each one can reply his own color but with the appropriate volume to code the color of hat of person standing in front. Still the first person has only 50pc chance of survival.

[peace*out]

What about passing notes?? No i guess not......

[roolstar]

I was away from the den a really long time... I don't know anymore if I'm working to live or just living to work!!

I am very happy to see that this puzzle is still getting so much interest

Just jumped in today to give a big THANK YOU to bonanova for maintaining this thread so well!

I really apreciate it mate.

Edited October 24, 2008 by roolstar

[Guest]

grats on the one hundred thousandth view btw!

(cough loudly for black, sneeze for red)

And i've heard this puzzle before somewhere

[Guest]

You choose one of the colors as even (lets say Red) and the other as odd. Since everyone can see the hats in front them, the first person says Red if he sees an even amount of Red hats, and Black if he sees an odd amount. Because everyone knows the color of everyone's hat in front of them, they therefore know that if the first guy says red and they see an even amount of Red hats in front of them, then they have a black hat on and will say so. Based on what each guy before you says, you will then know if you have a red or black hat.

[roolstar]

You ARE right Greg!

And on your first post too..

Good job and welcome to the den

[Guest]

the solution given was an obvious one, except it does not say anywhere in the riddle that there are equal numbers of red and black hats...I think that the originator of the riddle may have meant that to be the case, but it was not stated. Therefore, there is no correct solution as I see it!

[Guest]

the solution given was an obvious one, except it does not say anywhere in the riddle that there are equal numbers of red and black hats...I think that the originator of the riddle may have meant that to be the case, but it was not stated. Therefore, there is no correct solution as I see it!

there have been correct answer for any parity/proportion of coloured hats. Greg just above you has a correct answer for example.

[Guest]

Took me about 80 minutes:

Break the 20 into 5 groups of 4: 1 caller, 3 guessers.

{CGGG}{CGGG}{CGGG}{CGGG}{CGGG}

The caller of each group will call the least common color of the three in front of him. He has a 50% survival rate.

Each of the 3 guessers now knows the other 2 guessers' colors and which color is the most common. Using this method, the only way any of the three would be executed is if all three were the same color hat.

Consider the following possibilities:

BBB

BBR

BRB

RBB

RRB

RBR

BRR

RRR

As you can see, there is only a 2/8 or 1/4 chance that any given 3 will be the same color.

This means that in every group of 4, 2 prisoners are safe, one has a 50% chance of survival and the last has a 75% chance of survival.

The minimum guaranteed saved is 10, the average saved is 16 and the most saved is obviously 20.

[Guest]

there have been correct answer for any parity/proportion of coloured hats. Greg just above you has a correct answer for example.

no, it seems that Liam's answer is closer to correct, I just need to confirm it. Greg's is completely flawed, particularly at the beginning. Well, as far as 19 definitely saved, completely flawed. Say the first 3 hats are red, red, black, red. The 1st and 3rd men are already dead using his method. I can continue the progression and kill more men (fewer as we get farther along) but I can, I believe, kill up to 10 men by stacking the hat colors to go against the plan, although it may be less.

[Guest]

no, it seems that Liam's answer is closer to correct, I just need to confirm it. Greg's is completely flawed, particularly at the beginning. Well, as far as 19 definitely saved, completely flawed. Say the first 3 hats are red, red, black, red. The 1st and 3rd men are already dead using his method. I can continue the progression and kill more men (fewer as we get farther along) but I can, I believe, kill up to 10 men by stacking the hat colors to go against the plan, although it may be less.

oops, I forgot to stipulate that I set this at 14 red, 6 black, just as a starting point. As long as you put a black hat next when an even number of reds show, or a red hat when an odd number of reds show, that man looking ahead will die.

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

I disagree.

This solution will only work assuming that they give the prisoners the colored hats in a patterned order. For example, if the order of the hats is black black red black red black red red red red black black red black black red red black black red

[bonanova]

I disagree.

This solution will only work assuming that they give the prisoners the colored hats in a patterned order. For example, if the order of the hats is black black red black red black red red red red black black red black black red red black black red

Works for any sequence of hats.

Try it; if it seems to fail, post the hat sequence you assumed, and which prisoner [after the 1st] does not survive.

Then we'll discuss it on concrete terms.

[Faizaan]

wat if all the prisoners were facing eachother(not in the same direction.)the puzzle doesnt say anything about that. unless it was mentioned in a previous post.

[Guest]

apparently, there are fairly smart criminals on death row these days, if any of them were to miscount and mess up everyone else would die unless they were lucky! I think they should shout out the color of the hat in front of them, therefore saving half of the prisoners for certain. assuming they are nice enough to tell you the right color =)

[Guest]

this is my answer

1 st one has to sacrifice . out of 19 if he sees even number of blacks (then automatically reds will be odd) he will say "black" , if even reds then he ll say "red", now if black was the answer and the next one has black on he will see odd number of blacks and if he has a red on he will see even number of blacks

he can say safely what his color is now , now keeping track of these two results , the next prisoner knows the odd , even situation of the black - red mixture.

0 has to be taken as even

[Guest]

Very cool. I was leaning towards a sound or wording clue but the solution is great. Added to my top 10 list. THANKS ! (SAVES 19 + 50/50 CHANCE OF 1)

[Guest]

apparently, there are fairly smart criminals on death row these days, if any of them were to miscount and mess up everyone else would die unless they were lucky! I think they should shout out the color of the hat in front of them, therefore saving half of the prisoners for certain. assuming they are nice enough to tell you the right color =)

Simple and it works. I like it. ha.

[bonanova]

Simple and it works. I like it. ha.

What if you and all your friends had even numbers?

What if everyone would be executed if any of the last nineteen gave the wrong color?

[Guest]

Ok... so i read the first 6 pages or so.... (got tired of reading same crap over and over with different words). But the whole time I had a different idea than everyone else.

First of all, even if ur counting even hats and odd hats and wut not and saying colors based on that... who's to say that that will guarantee ur hat color? what if theres 5 hats of the same color in a row, or more for that matter, I really don't think that counting evens and odds would help much in that situation. I think ppl just need to "guess" the color of the hat thats in front of them. Now that only guarantees survival for half of the prisoners, BUT!

The king never mentioned that they would have only ONE guess, sooo on the night that they can communicate, they can all come to an agreement that the first color to come out of their mouths will be the color of the person in front of them. And THEN they could "change" their minds and say their own color. For example: #20 says "red" seeing that #19 has a red hat, from there he can decide to be like "no wait, black" if he wishes to change his mind about his own color since he's the one with the fifty fifty shot. And so #19 would say the color of the person in front of him of course (since they agreed on that already) but then do the thing where he changes his mind to say his own color. Now if the person has the same color as him, then they wont need to worry about saying any other color.

Ill make this a little more understandable if someone doesn't get what i'm saying.

#20 says "red" (because thats 19's color)

#19 says "black, no wait, red!" (cuz 18 has black)

#18 says "black" (cuz 17 also has a black hat)

#17 says "red, wait, black!" (cuz 16 has a red hat)

and so on...

That to me is the perfect solution. What do u all think?

[bonanova]

Ok... so i read the first 6 pages or so....

First of all, even if ur counting even hats and odd hats and wut not and saying colors based on that... who's to say that that will guarantee ur hat color? That's the job of the first prisoner. And you're right, it doesn't guarantee his own color. But it does save everyone else ... read it again here.

The king never mentioned that they would have only ONE guess, [actually, he did say that - see below]

#20 says "red" (because thats 19's color)

#19 says "black, no wait, red!" (cuz 18 has black)

#18 says "black" (cuz 17 also has a black hat)

#17 says "red, wait, black!" (cuz 16 has a red hat)

and so on...

That to me is the perfect solution. What do u all think?

Hi Charlie, and welcome to the Den.

In your solution, the first prisoner would only have a 50/50 chance - no one gives him any guidance so he can only guess.

That is a necessary characteristic of any solution.

While your solution helps the other 19 with their colors, so does the parity-based solution.

So it's only "just as good."

But actually your solution gets everyone killed. So it really can't be called perfect.

The OP stipulates that ...

He will be only allowed to answer “BLACK” or “RED”.

If he says anything else you will ALL be executed immediately.

A simpler alternative solution, if saying more than just BLACK or RED were permitted,

would be to have the first prisoner simply recite all nineteen of the other prisoners' colors.

[Guest]

Hehehe.... i suppose ur right bonanova

After reading the parity solution a couple of times last nite, it did finally start to make sense to me. I guess we can only hope the prisoners aren't completely retarded and they don't lose count.

I have a really fun riddle for you guys too. Its about 3 cannibals and 3 humans trying to cross a river on a little boat that carries only 2 ppl at at time. Ill have to figure out how to post it, I'll post it today its really good.

[Guest]

It s really simple. The 20th person in the row can not guess his hat color. So, he is against a 50-50 decision. there is not any difference to him to call "RED" or "BLACK". Therefore, when the king asks him about his hat color, he can reply the color of the person just in front of him. in this way he has a chance of 50 percent and the person just in front of him has a chance of 100 percent. In this way the 20th, 18th, 16th, ... persons tell the color of 19th, 17th, 15th, ... persons in the row. so, all odd persons will save and all even persons have the chance of 50 percent to save. at least 10 persons will save in this way.

good luck

just ask me ur questions because I HAVE ALL SOLUTIONS