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]

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.

Hi Admiral, and welcome to the Den.

This answer is temptingly straightforward, and many have offered it previously in this thread.

And it would work, if all that was required is to know the color of your hat.

Unfortunately, you're required to say your own color, correctly, or you die.

So you see this solution does not guarantee survival for any of the prisoners.

[Guest]

Being a programmer, the parity solution came to mind immediately, however, the king likes to toy with his people's miseries, the prisoners could reasonably be sufficient distance away from each other that not all prisoners will hear every other prisoner's replies; after all the king likes to toy with them yes? And he did say they would not be able to communicate together in any way, what's to stop him from ensuring that the line is long enough to accomplish this? Or indeed keeping the onlooking crowd riled up and yelling/cheering, or make the line weave through/around buildings etc ? What of the added sitpulation, that the solution must guarantee maximum prisoner survival rate for any number of prisoners? A long line from a large number of prisoners may prevent some replies being heard...the parity method will only work if all prisoners can hear all replies. It is a reasonable assumption that at least, each prisoner will hear the reply of the prisoner behind them, otherwise there is no puzzle to move forward to a solution haha, so, as much as I like it as it fits my initial assumptions, I must take issue with the parity solution as it does not guarantee survival of all but one prisoner for large numbers of prisoners and side with those that posed the notion that some form of answer modulation was needed (alteration of tone or duration) to allow each prisoner to say the colour of their own hat and save themselves while at the same time conveying the (same or opposite hat colour) information to the next prisoner so they may do the same and so on. I held my breath while typing this hehe but even dizzy this makes sense to me, it guarantees any number of prisoners will survive, minus the first one who takes a guess, and he even has the choice to guess whether or not his hat is the same or opposite to the one in front of him!

[bonanova]

Being a programmer, the parity solution came to mind immediately, however, the king likes to toy with his people's miseries, the prisoners could reasonably be sufficient distance away from each other that not all prisoners will hear every other prisoner's replies; after all the king likes to toy with them yes? And he did say they would not be able to communicate together in any way, what's to stop him from ensuring that the line is long enough to accomplish this? Or indeed keeping the onlooking crowd riled up and yelling/cheering, or make the line weave through/around buildings etc ? What of the added sitpulation, that the solution must guarantee maximum prisoner survival rate for any number of prisoners? A long line from a large number of prisoners may prevent some replies being heard...the parity method will only work if all prisoners can hear all replies. It is a reasonable assumption that at least, each prisoner will hear the reply of the prisoner behind them, otherwise there is no puzzle to move forward to a solution haha, so, as much as I like it as it fits my initial assumptions, I must take issue with the parity solution as it does not guarantee survival of all but one prisoner for large numbers of prisoners and side with those that posed the notion that some form of answer modulation was needed (alteration of tone or duration) to allow each prisoner to say the colour of their own hat and save themselves while at the same time conveying the (same or opposite hat colour) information to the next prisoner so they may do the same and so on. I held my breath while typing this hehe but even dizzy this makes sense to me, it guarantees any number of prisoners will survive, minus the first one who takes a guess, and he even has the choice to guess whether or not his hat is the same or opposite to the one in front of him!

Perhaps, but twenty prisoners [as specified in the OP] in a line before the executioner are well able to hear the replies. If there is crowd noise, or if there are millions of prisoners [not provided in the OP] these impediments would be overcome by the 10MW PA system and giant projection displays [also not provided in the OP ]. The OP could have been more crisp on what's allowed, but the consensus seems to be that "not communicating" other than to say RED or BLACK precludes stamping, shouting, whining, singing, whispering, altering pace, or in other ways offering information additional to the color guess.

[Guest]

Twenty prisoners [as specified in the OP] in a line before the executioner are well able to hear the replies. If there is crowd noise, or if there are millions of prisoners [not provided in the OP] these impediments would be overcome by the 10MW PA system and giant projection displays [also not provided in the OP

]. The OP could have been more crisp on what's allowed, but the consensus seems to be that "not communicating" other than to say RED or BLACK precludes stamping, shouting, whining, singing, whispering, altering pace, or in other ways offering information additional to the color guess.

Edited July 18, 2009 by Matou

[Guest]

ok I have replied twice and the posts aren't showing...I think some of the witty ones need to get together and fix this forum

the spoiler thing is broken or something

I'll say it one more time and if the forum loses my post again it loses me too lol

The king made it very clear in no uncertain terms the prisoners would not be able to communicate together in any way. No group effort. in any way.

there is also the later stipulation that it must work for any number of prisoners. I had the same idea as you Bonanova and I didn;t want to give it up either and maybe the OP was looking for that answer but it doesn't fit.

Edited July 18, 2009 by Matou

[roolstar]

Being a programmer, the parity solution came to mind immediately, however, the king likes to toy with his people's miseries, the prisoners could reasonably be sufficient distance away from each other that not all prisoners will hear every other prisoner's replies; after all the king likes to toy with them yes? And he did say they would not be able to communicate together in any way, what's to stop him from ensuring that the line is long enough to accomplish this? Or indeed keeping the onlooking crowd riled up and yelling/cheering, or make the line weave through/around buildings etc ? What of the added sitpulation, that the solution must guarantee maximum prisoner survival rate for any number of prisoners? A long line from a large number of prisoners may prevent some replies being heard...the parity method will only work if all prisoners can hear all replies. It is a reasonable assumption that at least, each prisoner will hear the reply of the prisoner behind them, otherwise there is no puzzle to move forward to a solution haha, so, as much as I like it as it fits my initial assumptions, I must take issue with the parity solution as it does not guarantee survival of all but one prisoner for large numbers of prisoners and side with those that posed the notion that some form of answer modulation was needed (alteration of tone or duration) to allow each prisoner to say the colour of their own hat and save themselves while at the same time conveying the (same or opposite hat colour) information to the next prisoner so they may do the same and so on. I held my breath while typing this hehe but even dizzy this makes sense to me, it guarantees any number of prisoners will survive, minus the first one who takes a guess, and he even has the choice to guess whether or not his hat is the same or opposite to the one in front of him!

So, we meet again MATOU (ESP Puzzle)!! And this time on my turf!!! HAHAHAHAHA

Just kidding. I like the way you think. Many puzzles on this forum require such lateral thinking solution, but this puzzle does not! In fact this was specified in one of my first posts (first page) in this thread.

It's like an unwritten (and sometimes written) rule in this forum to limit ourselves to the Original Post (OP).

PS: Your remarks do make a lot of sense and the only line I would add to the OP is: "Each prisonner sees everybody in front of him in the line and everyone can hear the answers."

[Guest]

The perosn in the back would have to be sacrificed, but he can simply start the series of telling the person ahead of him the color of their hat. He has a 50 50 chaonce of getting his too. so as few as ten or as many as twenty.

[Guest]

<div style="margin:20px; margin-top:5px">

<div class="smallfont" style="margin-bottom:2px">Spoiler for Here's my idea: <input type="button" value="Show" style="width:45px;font-size:10px;margin:0px;padding:0px;" onClick="if (this.parentNode.parentNode.getElementsByTagName('div')[1].getElementsByTagName('div')[0].style.display != '') { this.parentNode.parentNode.getElementsByTagName('div')[1].getElementsByTagName('div')[0].style.display = ''; this.innerText = ''; this.value = 'Hide'; } else { this.parentNode.parentNode.getElementsByTagName('div')[1].getElementsByTagName('div')[0].style.display = 'none'; this.innerText = ''; this.value = 'Show'; }">

</div><div class="alt2" style="margin: 0px; padding: 6px; border: 1px inset;"><div style="display: none;">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>

The puzzle doesn't say that the hats will be distributed in an alternating sequence.

Edited July 22, 2009 by kevclincar

[bonanova]

The puzzle doesn't say that the hats will be distributed in an alternating sequence.

No, it doesn't, and no one else does, either.

But that's not a solution.

Try harder.

[Guest]

Hello people,

I've read most replies and I didn't find this solution but a close one. Sorry if already proposed:

Any number of prisoners greater or equal to two:

The last prisoner counts the number of (let's say) black hats. Then he risk his life by telling red for a odd number of hats and black for even.

In this very moment every prisoner before him is able to know his colour.

The 19th one counts black hats before him. If it's an odd number and the 20th prisoner said red (odd), he knows his hat is red. Otherwise it would be an even number of black hats. He is saved.

The 18th prisoner counts the number of black hats just like the previous one. But he sees an even number. Then, his hat has to be black to make an odd number. Taking into account that 19th said his hat is red. And knowing before hand this method assures the colour of every prisoner but 20th.

Then the process repeats for the rest.

The second prisoner to be asked knows the answer quickly because he counts all the hats but his. The rest hast to keep counting how many blacks responses hears behind him. Then add the number of black hats before him and check parity.

This method seemed to work for any number of prisoner in paper.

[Guest]

The 20th person declare the color of the 1st, 19th person declare the color of the 2nd ... 11th person declare the color of the 10th. 10 persons know their colours. From the 20th to the 11th - as will luck

Edited July 30, 2009 by jean216

[Guest]

First prisoner says "green"

Does anyone else have a problem with helping people get out of death sentences? Assuming that the king is only ruthless and not unjust, a flawed justice system (barring corruption) will only convict a fraction of a percent of the innocent. And only a fraction of those will receive the death penalty.

Now, if the system is corrupt or there is plainly no justice, then see the link in the OP for the correct answer.

[Quantum.Mechanic]

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

To add to bonanova's reply...

You would only be replacing one sequence of bits with another. To compute a given bit, the parity of <the given bit and all remaining bits> is combined with the parity of <all remaining bits>.

An interesting twist on the puzzle: If each prisoner could only see the one immediately in front of him, and allowing for some simple (binary) communication, is there a solution?

[Guest]

To add to bonanova's reply...

You would only be replacing one sequence of bits with another. To compute a given bit, the parity of <the given bit and all remaining bits> is combined with the parity of <all remaining bits>.

An interesting twist on the puzzle: If each prisoner could only see the one immediately in front of him, and allowing for some simple (binary) communication, is there a solution?

If it hasn't already been done, you could start a new thread with the modified problem. As this is a very popular problem, you might get a large response.

[Guest]

There is another, simpler way to guarantee 19 survivals. Given that there are 19 people in line and that they are in a stressful situation, it is possible that one of the 19 would miscount and give a wrong cue. This would throw off all the line, and cause more executions. As well, the first person in line will have to count all the other hats, and would have to bend out of line to see (what if he was short?). This may draw attention from the guards, and they all might be executed.

So, a simpler way: The 1st person looks at the hat in front of him (the 2nd's hat) and says its color. This gives the 1st a 50/50 chance. But the 2nd in line now knows their color! If the 3rd person has the same color hat as the 2nd, then when the 2nd announces their number, the 2nd announces the color of his hat loudly (shouts). If not (2nd and 3rd hats are different), the 2nd announces his quietly (normal).

This way, each person apart from the 1st will know their color, and there will be no math and no visual difficulties. The differences in volume could easily be attributed to different people's reactions to stressful situations.

Sample:

1: R/B Says B

2: B Says B (loud)

3: B Says B (soft)

4: R Says R (loud)

5: R Says R (soft)

6: B Says B......

Take lemons and make lemonade.

[Guest]

You can save at least 10 but will need to sacrifice some people. The 20th person says the color hat of 19th person. Person 20 has a 50/50 chance of living but person 19 lives. You repeat this down the line and 10 will people live and everyone else has a 50/50 chance.

Edited August 6, 2009 by Kriil

[Guest]

Wow, this one has been going on for a long time. i was surprised nobody has gotten it yet. I came up with an idea and skimmed through previous posts (sorry, not all 37 pages though). Way back in post #76 on pg. 8, bandvbending had the same idea i had but it seemed noone replied why it would be wrong.

use a nonverbal signal since they cannot speak to eachother. Prisoner #20 would have to guess his own color so he would only have a 50/50 chance. As he says his color, he taps his foot for the person in front of him - once for black and twice for red. Each person will then know what color hat he has on based on the number of taps from the person behind them and they will be able to accurately say their own color. 19 people are guaranteed to survive

[Guest]

(this will work is repeating answer is allowed).

the first man will be a sacrifice. instead of guessing the color of his hat, he will tell the color of the hat of the man in front of him.

thus the man next to him already know whats the color of his hat. he will then look at the color of the hat of the man infront of him. but with a twist. if the color of the hat in front of him is the same as the hat he is wearing, he will tell the color twice, and if he will say once,it mean that the hat of the next man is opposite color to his hat .

the next man will then listen, if he hears the color is said twice. that means they have the same color of hat, now he knows the hat he is wearing, he then look at the hat in front. and do the same as the second man.

this style will only have i casualty provided repeating an answer is allowed.

example a sequence of 6 men having an order of red | black | black |red | red | black

they will say:

first man ="black"

second man = "black black"

third man ="black"

fourth man ="red red"

fifth man ="red"

sixth man ="black"

in above scenario only the first man will be executed.

can you guys get the picture?

[Guest]

yes every one can set free ,as 1st prisonar can see every ones hat execpt his.so if he can see 9 white hat and 10 black hat he is wearing white hat if he can see 10 white hat and 9 black hat he wears black hat and tis way all the prisoner can fine out color of hat on their hat...

[Guest]

In the original riddle the number of red vs. black hats is not supplied.

It could be that there is a total of 6 black hats and 14 red hats.

Perhaps it is taken for granted that there is an even ratio of red hats to black hats.

Please reply if I have missed something.

[bonanova]

In the original riddle the number of red vs. black hats is not supplied.

It could be that there is a total of 6 black hats and 14 red hats.

Perhaps it is taken for granted that there is an even ratio of red hats to black hats.

Please reply if I have missed something.

You haven't missed anything.

The OP does not specify the relative numbers of red and black hats.

Nothing about their relative numbers is taken for granted.

You are correct in stating there could be 6 black and 14 red hats.

The solution must apply for any numbers of red and black hats.

[bonanova]

yes every one can set free ,as 1st prisonar can see every ones hat execpt his.so if he can see 9 white hat and 10 black hat he is wearing white hat if he can see 10 white hat and 9 black hat he wears black hat and tis way all the prisoner can fine out color of hat on their hat...

Re-read the OP.

The first prisoner is not able to determine the color of his own hat.

[Guest]

yes every one can set free ,as 1st prisonar can see every ones hat execpt his.so if he can see 9 white hat and 10 black hat he is wearing white hat if he can see 10 white hat and 9 black hat he wears black hat and tis way all the prisoner can fine out color of hat on their hat...

This makes the assumtion that there are ten hats of each colour. I say assumtion, because it was not stated in the OP that there were ten of each hat colour, there could be any number of each colour, as long as there were a total of 20 hats. And if you go making a silly assumption like that, then alot of prisoners are liable to end up dead ...

[Guest]

The answer is very simple........THE ANSWER is RED its very simple............

[Guest]

red = 0 black = 1 prisoner 20: total the number before him and announce.(red for even, black for odd) his life is a gamble in all cases... prisoner 19: total the sum in front of him and decide his color and announce.. all the rest keep track of the score and save their live..