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]

The problem never states what ratio of black hats to red hats there are or will be. Bonanova's solution won't work if the twisted King distributes 15 black hats and 5 red hats, or 19 red and 1 black, or 7 black and 13 red, etc. This would make every prisoner's decision purely random.

The prisoner at the end and moving up the line will have a look at a larger sample size of the hats and might figure out that black and red hats are not distributed evenly, but as you get to the middle of the line, it becomes a wash and the prisoners don't see enough hats in front of them to make an informed decision.

The problem also does not state whether each prisoner will be able to hear their fellow prisoner's answer as to red or black or know the outcome of their answer; if they got it right and they get to live or die. Since they are all facing forward, and the King starts at the back of the line, no one is allowed to look back and see what happens. If the prisoners' answers and outcome are unknown to everyone else, it makes the decisions more of just a random guess.

A lot of flaws to the original problem.

Edited May 10, 2008 by danimal233

[bonanova]

The problem never states what ratio of black hats to red hats there are or will be. Bonanova's solution won't work if the twisted King distributes 15 black hats and 5 red hats, or 19 red and 1 black, or 7 black and 13 red, etc. This would make every prisoner's decision purely random.

The prisoner at the end and moving up the line will have a look at a larger sample size of the hats and might figure out that black and red hats are not distributed evenly, but as you get to the middle of the line, it becomes a wash and the prisoners don't see enough hats in front of them to make an informed decision.

The problem also does not state whether each prisoner will be able to hear their fellow prisoner's answer as to red or black or know the outcome of their answer; if they got it right and they get to live or die. Since they are all facing forward, and the King starts at the back of the line, no one is allowed to look back and see what happens. If the prisoners' answers and outcome are unknown to everyone else, it makes the decisions more of just a random guess.

A lot of flaws to the original problem.

Hi danimal, and welcome to Brainden.

Not to call you out, but either you didn't read and understand the posts in this thread, or you're looking for an excuse [saying the puzzle is flawed] for not coming up with a solution to a challenging riddle.

Here's why I say that ...

[1] The problem never states what ratio of black hats to red hats there are or will be.

Distribution is not implied, and it's not relevant.

[2] Bonanova's solution won't work if ... [there are certain color distributions].

Distribution is not implied, and it's not relevant. You probably didn't understand the riddle.

[3] The prisoner at the end and moving up the line will have a look at a larger sample size of the hats and might figure out that black and red hats are not distributed evenly, but as you get to the middle of the line, it becomes a wash and the prisoners don't see enough hats in front of them to make an informed decision.

This simply makes no sense in the context of the riddle:

• Sample size is irrelevant.
  
• Distribution is irrelevant.
  
• Seeing "enough hats" is irrelevant.
  

[4] The problem also does not state whether each prisoner will be able to hear their fellow prisoner's answer as to red or black or know the outcome of their answer; if they got it right and they get to live or die. Since they are all facing forward, and the King starts at the back of the line, no one is allowed to look back and see what happens. If the prisoners' answers and outcome are unknown to everyone else, it makes the decisions more of just a random guess.

Can they hear? - Where does it say they are deaf?

Do they know the outcome? - They don't need to.

No one is allowed to look back. They don't need to.

The decisions become a random guess. - Nope. Nineteen go free, guaranteed.

[5] A lot of flaws to the original problem.

It's challenging - perhaps both to understand and to solve - but not flawed.

[Guest]

I didn't understand your solution before. Now I get it. You're my hero.

[bonanova]

I didn't understand your solution before. Now I get it. You're my hero.

It's a clever solution - not original with me - and very satisfying to see how it works.

Sometimes I can explain things better than I can analyze them.

[Guest]

This I think is very kinda simple

I think the prisoners should come up with one singnle. Like if the hat is red one prisoner will look to the left. If the hat is black one prisoner will look to the right. Then it does not look like you are doing a signal but you really are.

But you can't signal to the person in front of you (by turning your head) if their back is to you and can't turn around.

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

[Guest]

I will have to agree this was fun to "try" to solve, however there are a few posts that I agree with too...not knowing the future distribution order of the hat's (blk vs. rd),what could the prisiners have possibly disgussed the night before as a possible strategy, they would have been told the hat's were to be divided in to two color groups, how else would they have come to the "odd / even" solution? I'm sorry if I too am missing the big picture. Again, great riddle

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.

[bonanova]

I will have to agree this was fun to "try" to solve, however there are a few posts that I agree with too...not knowing the future distribution order of the hat's (blk vs. rd),what could the prisiners have possibly disgussed the night before as a possible strategy, they would have been told the hat's were to be divided in to two color groups, how else would they have come to the "odd / even" solution? I'm sorry if I too am missing the big picture. Again, great riddle

You're right ... they are told there are two color groups. The OP says ... among other things ...

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.

[Guest]

You're right ... they are told there are two color groups. The OP says ... among other things ...

After thinkin about it for awhile, you would just have to naturally "assume" that the king, although ruthless, will have to at least be fair for it to be an exciting "head game" for him, hince the two evenly matched color groups. Sorry to be so nit picky, (everyone's a critic ya know : )

thanks

[bonanova]

After thinkin about it for awhile, you would just have to naturally "assume" that the king, although ruthless, will have to at least be fair for it to be an exciting "head game" for him, hince the two evenly matched color groups. Sorry to be so nit picky, (everyone's a critic ya know : )

thanks

It's not said that they are evenly matched. Just that there are two colors, red and black.

[Guest]

Why can't each prisoner just say the colour of the hat of the man in front

[Guest]

just realized why this is wrong!!

[Guest]

The King doesn't say there are an equal number of red and black hats, so I don't see how Bonanova's solution works - or maybe I just don't understand it well enough.

Obviously the last in line says the color of the guy in front of him.

After that, my thought was to have an indicator that would tell the person in front of you whether their hat was the same or different from the color of your hat. You are only allowed to say "black" or "red" - anything else and you're all killed.

But, you can change the volume of your voice. Your color said loudly means the person in front of you is the opposite of the color you say.

Said in a normal voice, they're the same color.

Or volume can just be a direct indicator of the next person's color: loud is red, soft is black.

[Guest]

Note : the riddle said "you will not be allowed to look back or communicate together in any way (talking, touching.....) + also "guarantee the freedom of some prisoners tomorrow?" So, with that in mind, if everyone guess all black or all red 50% of the people (or 10) will set free. This is guaranteed and is done without communication with anyone.

[Guest]

I get ten saves.

Each person says what is on the one in front. 2nd one knows his color so he says it. Third one is not sure but says the color of the one in front. Fourth one knows his color and says it. If you follow this progression than you get 10 sure saves and 10 50/50 saves.

[Guest]

ummm... did u forget to add that there are 10 red and 10 black hats?

if not then...

10 people are guaranteed to be saved. The first one sacrifices himself by telling the colour of the second person, and second person saves himself. The third person sacrifices himself and saves the fourth and so on. However, if the second prisoner has the same colour as the third prisoner, then both of them could be saved. However, this method is not guaranteed, since the king is cruel and is probably going to place the hats in an alternating pattern, so that no two consecutive prisoners could be saved.

[Guest]

Ano, I have a question about some of the guesses that everyone's put up... Mainly the one that's chosen as mostly-correct.

Ano, what do they do if they see, say, 11 red and 11 black hats..? Ano, what color does the first prisoner say then..?

[Guest]

the answer is simple and you can save n-1 out of n people.

To do this you use a binary coding red is 0 black is 1. Now the problem says that you cannot communicate with the men behind you, but you can communicate with the one in front. So the last one should just shout out the outcome of the XOR function usind everyone in front of him. The last man in the group has a 1/2 probability to survive since he has to guess the color of his hat.

Now the men in front calculates the xor function for the ones in front of him and knowing the outcome of the function with him and without him in the equation he can tell his hat color. And the rest will do the same.

Example

10101 si the combination of them all, therefor the last one can calculate the xor function for 1010 witch is 0.

the 4'th one now can calculate the xor function for 101 and his outcome is 0, that means that his hat must be 0, since the outcome with his hat is still 0.

the 3'rd one can caluculate xor 10 and his outcome is 1, the xor with him is 0, witch means that he must be 1

the second knowing that him and the one in front have an xor outcome of 1, and the one in fornt has 1 he knows that he is an 0

and the first one knowing that the xor with the one behind and him is 1, and that the one behind was an 0, can say for shure that he is an 1.

The xor function has this table of truth

0 xor 0 =0

0 xor 1=1

1 xor 0=1

1 xor 1=0

Hope i was clear enough.

[Guest]

Hi, Surely the easiest and most simplistic approach to this would be for all the prisoners simply to declare the correct colour of the hat in front. Thus ensuring 19 prisoners are set free with the first (20th) prisoner having a 50/50 chance of his colour hat matching the prisoner in front.

[Guest]

Bonanova is a very patient person. The answer has been offered and explained, yet debate continues. A basic understanding of odd and even numbers is all that is required. Just read Bonanovas posts.

A brilliant and simple solution.

[Guest]

i dont think that you would be able to get the person in the front because he wont be able to hear every thing

[Guest]

I do not see any statement that there are an equal number of Red and Black hats. There could be all Red or all Black or any other mix.

The person at the end of the line would have to state how many were black, how many were red and the color in front of him knowing he would sacrafice his own life for the rest. "All Red", "All Black" "5 Red, front black" -- with that, the other 19 could be saved.

[Guest]

I think this should save at least 19 out of 20 with a 50% chance of saving all 20:

I haven't heard this one before, but I think I've got it. If the first person sees an even number of red hats, he says red. Otherwise, he says black. That way, the second person can see how many red hats are ahead of him and work out whether his own hat is red or black, and then each subsequent person can count how many red hats have been given out and work out whether there are an odd or even number of red hats left, including his own. Example with fewer people:

(first guy to talk) R B B R B R R R B R

First guy (Red) sees B B R B R R R B R in front of him (5 red hats, which is odd), so he says "black," which is wrong and gets shot. Everyone else now knows that there are an odd number of red hats.

Second guy (black) sees 5 red hats in front of him, meaning his own hat must be black. Same for third guy.

Fourth guy sees only 4 red hats, knowing that there are an odd number of red hats left including himself, his must be red.

Fifth guy knows that fourth guy's hat was red, so there are now an even number of red hats left. He sees 4 red hats in front of him, so he says "black"

And so on and so forth, and assuming everyone goes with the plan, all but one person (the first) is guaranteed survival.

Edited June 2, 2008 by Chuck

[Guest]

19 guaranteed. The prisoners all must agree to speak the color of the hat in front of them. The first has fifty percent probability because he has no way of knowing what hat he has, but will still not be deterred from participating because he sacrifices nothing. If the first man lives, the second knows that what he spoke is right; if he dies, the second man will know to say the other color. From then on they are all right.

[Guest]

This solution is a little difficult because they would need to be synchronized. The first person to answer will still have 50% chance but he can guarantee the survival of the rest if he can communicate how many black hats there are overall. After the question is asked, they should all count the seconds that pass(hopefully they are able to practice the correct interval). If the first person answers after X seconds then there are X black hats. The next person who answers will know that if he sees there are X-1 black hats then his hat is black. Otherwise it is red. The rest wil just have to keep track of the answers to know how many black hats are left by the time they need to reply.