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]

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.

Wow! Bonanova, I am impressed by your explanation.

[Gambit]

Wow! Bonanova, I am impressed by your explanation.

yes. Good stuff!! Solid answer from bonanova

[Guest]

Is there and equal number hats? (10 red 10 black)

[Guest]

The only problem with the solution is that you are assumng that there are an equal number of black and red hats. Nowhere in the puzzle does it stipulate the ratio of hats

[Guest]

I agree that the first prisoner is going to have a 50/50 chance, but the whole even and odd deal is a little tricky in my opinon. I'm not saying that this solution is wrong. I agree with it. I just feel I have a much more simple solution.

As I said before, the first dude is going to have to guess, sucks to be him/her. But depending on how he says it, he can tell the others(or really the dude in front of him) what their hat color is. i.e.---If they say their color in a loud, clear voice. The dude in front of him has a black hat. If they simply mutter or try not to say their color loudly at all, then the one in front has a red hat. This way, they is no counting of the hats, and less possibility of a mass execution. But this is only my opinion. The even and odd thing is correct in my book. WEEEEEEEEE

[bonanova]

The only problem with the solution is that you are assumng that there are an equal number of black and red hats. Nowhere in the puzzle does it stipulate the ratio of hats

Nope.

No such assumption. They can be all black, all white, anything in between.

[Guest]

stil debating after 6+ months?!

Good buzzle roolstar!!

[Guest]

I'll admit to not reading all eleven pages, but I think I've got an answer that's probably already been posted.

First, assign each color either one or zero; here let's call red one and black zero.

The first prisoner will total the number of red hats. If the number is even, he will say "Black." If it is odd, he will say "Red." The second person in line should be able to figure out his own hat color by adding up the total in front of him, and seeing if his total correlates to what the first person said; eg, if the first guy says "red" (odd), and their are eight red hats in front of him, he knows he has a red hat. Assuming everyone is paying attention, they should all be able to work their way down the line by adding up the number of red hats in front of them and the number of people who answered "red" behind them, excluding the first guy, of course.

Hope that made sense!

[Guest]

If they wear 10 black and 10 red hats then all of them will be free.

[bonanova]

If they wear 10 black and 10 red hats then all of them will be free.

Really ... ?

How will the first to speak know his color?

[Guest]

My first solution before i came across the even/odd logic was able to save half of the people. This takes far less intelligence to understand =P but w/e. The first person says the color of the hat of the guy ahead of him so he can save him. However the third guy must do for the fourth guy what the first guy did for the second guy. So every other guy would be saved.

Oh, and it may save more than half if an odd guy happens to call out his own color while warning the guy ahead of him.

Edited June 11, 2008 by Austin CG

[Guest]

The first person calls out the 19th person's hat color, saving #19's life and giving himself 50% odds for survival. #18 does the same saving #17's life and taking 50% odds on his own life. When it is all over 10 people will be saved and 10 will have 50% odds. The possibility of all 20 being saved is there but the likelyhood of that is not very good. 10 for sure and anywhere from 0 to 10 more may also be saved.

[Guest]

Ok i hate to be simplistic, with all the people below me doing crazy math and such, but in the riddle it clearly states the guy in the back can see all of the people in front of him. If he can see 19 other people, he will know the color of his hat. if the 19th person can see the 18 in front of him and the person behind him just said the color of his hat, then he also knows his color. i dont know if thats the answer or bad wording on the riddles part, but if its how its supposed to be, then that is the obvious answer. and all 20 would live.

[Guest]

The first person in the back will say the color of the hat in front of him. It's a 50% chance for the first guy however. (No matter what, the first guy has to say red or black depending on what the next person in line has on.) Now the second guy knows that his hat is in fact red. Here is where you must have a dual meaning with only saying one or the other red or black. It's now how you say "red" or "black" is the key. If the next person has to say red knowing that the next guy in line is wearing black he should yell "red" saving his life because in the case of course he has a red hat on. By yelling out loud “RED” he now will not be killed and the next person will know that he is wearing a black hat.

Code:

Say black normal meaning the next guy has a black hat

Say BLACK shouting meaning that if you are in front you are wearing a red hat.

And vice versa

[Guest]

18 will have a guaranteed chance at survival; those would be the middle 18

the first and last would have 50% chances because the front cant look back and the second to last person cant look behind himself

[Guest]

Cconeus:

Being simplistic is good but...

You are assuming that there is 10 red hats and 10 black hats, which the riddle did not state. So no one person knows what their color of hat is in the beginning.

Edited June 12, 2008 by Austin CG

[Guest]

Cconeus:

Being simplistic is good but...

You are assuming that there is 10 red hats and 10 black hats, which the riddle did not state. So no one person knows what their color of hat is in the beginning.

ok true. i realized that today while thinkin about it. but then i thought about this statement...

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

so on the first sentence, i thought to myself today... it would be slim odds (sense i dont wanna do the math atm, someone else will ) sense everyone would be executed if ONE person got the answer wrong. yet on the second sentence it seems that the single person would be put to death. i kinda need to know which one it is. and lookin at it again, it says "can you find a way to guarantee the freedom of some prisoners tomorrow? How many? " so that being said, i would say ONE, because you could only really guarentee one person surviving, if everyone said black, or everyone said red, depending on if one person dies or all of them die.

[Guest]

I GOT IT......LOLZ

[Guest]

The person in the back of the line sees 19 hats in front of him. Of those 19 hats, some number (say n) are red. Either n (the number of red hats) or 19-n (the number of black hats) is even. He names the color of the even number of hats. Suppose for example he sees an even number of red hats.

Person 19, in front of him, sees either an even of red hats or an odd number of red hats. If he sees an even number, he knows that all the red hats #20 saw are still there, so his own must be black. If he sees an odd number, one that #20 saw is missing, so his own is red.

Later people know the colors of the hats behind them, because they've heard what others said.

If the total number of prisoners were odd, the system would need to be modified. In this case, either both numbers would be odd, or both would be even. The last prisoner should say "red" if both are odd, "black" if both are even. If he says "black" (for example) the prisoner before him names the color of which he sees an odd number, and later prisoners iterate the system in the obvious way.

The major flaw in my method is that it has no error correction. If anybody screws it up (assuming the king is bright enough not to supply extra information by executing those in error right away) the whole system is thrown off.

[Guest]

Oh, wow, I found the "turn the page" button, ha ha, yeah, lots of people beat me to the solution.

Now, a question: can we expand this solution to three colors of hats? Larger numbers?

I'm quite sure there's no winning strategy with 20+ possible hat colors, of course. What's the limit?

(Says the mathematician fascinated by the specialness of small numbers...)

[Guest]

Sigh. Just spotted that I posted a solution that was stupid.

Edited June 13, 2008 by Racaroodle

[bonanova]

Oh, wow, I found the "turn the page" button, ha ha, yeah, lots of people beat me to the solution.

Now, a question: can we expand this solution to three colors of hats? Larger numbers?

I'm quite sure there's no winning strategy with 20+ possible hat colors, of course. What's the limit?

(Says the mathematician fascinated by the specialness of small numbers...)

Yes, three colors can be done.

Good question ... what do you think?

[Guest]

From what I can tell, this solution only works if the hats are placed in a certain order. It seems like a very straightforward way of solving it (if all the prisoners are able to converse the night before) would be to come up with a system like this:

The last guy in line would still be a fifty-fifty shot, but if the person in front of him had a red hat and his guess for his own hat was also red, then he could emphasize the beginning of the word. If the prisoner in front of him had a black hat, then he could emphasize the end of the word. Rrred or reD.

So, basically you would emphasize the beginning of the word if it was the same color, and the end of the word if it were a different color.

This could also ensure that those who were poor with math or could not hear those toward the back of the line, would only have to rely on hearing the person directly behind them and discerning the answer then.

[Guest]

From what I can tell, this solution only works if the hats are placed in a certain order.

By "this solution" I was talking about the algorithm on the first page of answers...I didn't see all the other answers after that.

[Guest]

geez we saw this last month!