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]

This is confusing

Edited April 3, 2008 by Nebukhadnezzar

[Guest]

Where did it say that the prisoners are whereing either red or black hats. The King is known for toying with the people so the prisoners chances are slim to none

[bonanova]

Where did it say that the prisoners are whereing either red or black hats. The King is known for toying with the people so the prisoners chances are slim to none

Part of the OP:

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

[Guest]

I don't understand how you can come up with a solution when the king never said how many red or black hats he was going to use. there could be 19 red hats and only 1 black one.

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

WHAT IF THERE ARE 19 RED HATS AND ONLY 1 BLACK HAT? Does it work then?

since they can't communicate within eachother, couldn't the person in the back just tell whomever is doing the executioning the color of the hat on the person in front of them loud enough for the person in front to hear?

Edited May 2, 2008 by vee0315

[bonanova]

I don't understand how you can come up with a solution when the king never said how many red or black hats he was going to use. there could be 19 red hats and only 1 black one.

That's correct.

It looks like you've read and understood the problem.

Now read the solution and think about that for a bit.

Take your example of 19 red and 1 black.

Assign the black hat to one of the prisoners [to the first prisoner, the second, or one of the others]

and work out the solution.

If something specific doesn't seem to work, come back with a question.

------------------

You suggested:

couldn't the person in the back just tell whomever is doing the executioning

the color of the hat on the person in front of them loud enough for the person

in front to hear?

The OP requires each prisoner to name the color of his own hat.

A prisoner who gives the color of another's hat risks his own execution.

The solution guarantees 19 prisoners will survive. Would your solution do that?

[Guest]

I dont think I understood your puzzle correctly.

EDIT : Never mind my stratagy doesnt require every prisoner to see everyone elses hat

But assuming that one prisoner can see everyone else's hat:

The night before they devise this strategy : If the prisoner says their hat is red, then it is a signal that the next persons hat is black. Vice-versa. They have a 50% chance of not dying and the next person will know what color their hat is

Edited May 2, 2008 by Dumbb

[bonanova]

I dont think I understood your puzzle correctly.

EDIT : Never mind my stratagy doesnt require every prisoner to see everyone elses hat

But assuming that one prisoner can see everyone else's hat:

The night before they devise this strategy : If the prisoner says their hat is red, then it is a signal that the next persons hat is black. Vice-versa. They have a 50% chance of not dying and the next person will know what color their hat is

Yes, but the point is, if each prisoner signals the next one's color, he can't correctly give his own color.

Since each one has to tell the next one their color, no one can call his own color.

So there's no point knowing it.

Everyone ends up a coin toss, and you already have a 50-50 chance, without any strategy at all.

The trick is to say your own color [correctly] AND provide the needed info to the next prisoner to guess his correctly ... etc.

Give it some more thought... it's a difficult solution to find, but easy to understand once you "see" how it works.

And it does ensure that 19 prisoners definitely will survive...!

[Guest]

wow, this riddle sounds impossible lol

heres my guess

well, the prisoners are in a high class prison and they come with mirrors. Everybody straps a mirror onto their head so the person behind them knows the color of their hat. the first person then makes funny faces at the executor until the executor gets angry and threatens you with his nice big looking (very shiny) Axe so you can see the reflection of the hat on your head. YOU ALL LIVE. W00T, PARTY AT THE KING'S PLACE.

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

[Guest]

Good Job Bonanova (as usual), I always liked your way of thinking.

Now there's a thing about these kind of puzzles. For me, I enjoy the journey of finding the solution 10 times more than the analysis of the solution. And that's because I never know where I would end up!

And here's where this puzzle lead me:

What if RED and BLACK were replaced with 0 and 1!!!!

Would the solution for this puzzle represent a new compression technique, where one number at the beginning can make the rest of the series known? in other words, would this reduce file sizes?

I realise it needs a "little" adjustment but my intuition tells me there's something there....

Good job everyone!!

Shame I came here late, Like BN, I would have got this with Computer logic.

What he described is basically how a Raid 5 system works.

It was the first thing I though of when I looked at the puzzle...

For those that do not know a Raid 5 system is a servers way of making sure you never lose data. It involves 3 or more disks. The Parity disk (for simplicity sake I will put all the parity on one disk - however, in reality Parity is usually divided across all disk.) has either 1 or 0 that it calulates by adding the 1's and 0's from that same spot on all other disks

If you lose a disk, by knowing the parity bit and the total of all other 1's and 0's (minus the lost disk) you can calulate what is missing....

Great Puzzle and great Job BN

[Guest]

I was just thinking, it isn't even possible to have the 50/50 chance of the 1st prisoner guessing the right answer if he decides to just say something else like "yellow" and get them all executed.

Probably not what you meant here, but wanted to see what you think.

Newbie here, Marie in Arizona a.k.a....skapunklover

[Guest]

I am sure this is the answer, it would guarantee that 19 live, and the last one has a 50% chance

The last person says red if they see an odd number of red hats in front of them and black if they see an odd number of black hats in front of them. The next person looks at the number of red and black hats in front of them. If they heard black, and there is an even number of black hats in front of them, they are wearing a black hat. If they heard black, and there is an odd number of black hats in front of them, they know that there hat must be red because the number of black hats stayed the same. For example, the first person see 13 red hats and 6 black hats. They say red, because there is an odd number of red hats. The next person sees 12 red hats and 6 black hats. They know the person behind them saw an odd number of red hats, so their hat must be red. The next person has heard red twice, the first he knows meant there were an odd number of hats. If the second person said red, they saw an even number of red hats . So if this person sees an odd number of red hats they are wearing a red hat, if it is still even, they are wearing a black hat. It would continue this way until the last person. Even if there were 19 red hats and one black hat, or even 20 red hats and no black hats, it would still work. The first person would see 19 red hats, and say red. The next person knows the other saw an odd number of red hats, but they see 18, an even number. They know their hat is red and say so. The next person heard red and knows the number of red hats the second person saw was even, they will see an odd number and guess red, etc. etc..

Edited May 4, 2008 by collateral

[Guest]

Here's my solution, not sure if it's allowed or not...

You can save the 19 ahead of you by stretching out how long you say the color. The guy in the very back (20th in line) would say the color of the individual (19th) in front of him in 1 second. (Red.) He's got the 50-50 chance. The next person, if 18 is red as well, he says it in one second. If not, he counts off the number of people until he sees another red and that's how long it takes him to say "Red." So if the person 3 (number 16) ahead of him has a red hat, he says "Reeeeeed" over 3 seconds. This way, everyone knows counts the number of seconds for the word and knows that if it skips them, they are the opposite color. If you get close to the end and there are 3 people left with red hats and yours is black, you extend it to 4 seconds for saying red, telling the three of them they are all black.

How's this one?

This is a good puzzle roolstar. I also thought to solve it this way.

[Guest]

Yea I used time intervals too. Where most people go wrong is that they assume that there are an equal # of red and black hats.

[Guest]

I would say if the prisoners "Paired" up beforehand 10 men could be "guaranteed" freedom by statng the color of their partners hat. The first in the "pair would live only if he matched his partner.

[Guest]

Here is what I would do if I was that prisoner.

I agree with cookiemonster, except that I think that he chose an incorrect signal, because a visual symbol like leaning would only work if they were facing in a way so that the shadow showed. So my signal would be audible, so if the person in front of you had a black hat, you answered unsure (but with your own color, like "Red?"), like you are afraid you might die. But if its red you just state it, as if you knew it was that color "Black." This doesn't require any counting, but like all other solutions, you have to take a guess as the first person (since you can't be sure if there are an even number of each hats).

Maybe not the most logical, but the easiest, I would think.

[Guest]

I do not believe the riddle can be answered as to the fact that they do not tell you how many red hats or black hats there are.

[Guest]

The night before. The prisoners should agree to who ever is the 20th one. Would say (when asked) the color of the one thats in front of them. So, at least 19 should be guaranteed and there fore the 20th would have a 50% chance.

[bonanova]

The night before. The prisoners should agree to who ever is the 20th one. Would say (when asked) the color of the one thats in front of them. So, at least 19 should be guaranteed and there fore the 20th would have a 50% chance.

20th prisoner has a black hat. He sees all the other hats. In particular he sees that #19 has a red hat.

So he says "Red" - and he's executed. OK he only had a 50-50 chance and he was unlucky.

Now #19 knows his hat is Red. Suppose all even #'s are black and all odd #'s are red.

How can he use the knowledge that his hat is red to save himself and everyone else?

Other recent answers where there's "signaling" read the OP which says

... you will not be allowed to look back or communicate together in any way ...

There is a solution, but it does not involve length of time, nodding your head, voice pitch or .. "communicating in any way"

[Guest]

Okay.. but am I missing something?? There is no statement in that riddle which says that there has to be equal numbers of Red and Black Hat, that implies that POSSIBLY everyone could have all Black hats ...

Anyways here's my solution and do let me know if somethings up with it!

20th is a chance save. 50-50, all he can do is save the other by just saying the color of the hat of the person in front of him. This is the most logical/sensible way to do it. Even if he counts 10 black and 9 red, the probability that he has either is still 50%. He might just as well save the one in front of him. And then they pass this down the line. so they end up saving 10 surely, while the other 10 have 50-50 chance of making it.

And if there is an agreement about signals, that is if the riddle allows any kind, than they can speak softly for black and loudly for red one in the front or stammer for one and not for another color while saying their own. This way you save 19 and 1 has a 50% survival chance.

And if the riddle presumes equal number of black/red hats, then its a mathematical certainty. Everyone is saved. they just need to keep track of the colors shouted and people remaining.

[Guest]

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

So you would need as many bits for the alteration as you would for the original. I'm feeling an encryption or hash technique.

[Guest]

Would this not also work???

If they can speak freely the evening before, Devise the answer in high pitch low pitch, meaning the first guy is a 50/50 guess. Use high pitch for the color of the man in front of you for red, and low pitch for black. You will save 19 with still 50/50 on the first guy.

[Guest]

Bonanova was correct...there is a way to save 19 with the 20th having a 50% chance of surviving. But there is a far simpler way of accomplishing that.

When in the cell the night before here's the solution. The 20th person will say a color, just a guess at his own hat color. The only thing that matters to the other prisoners is how long that person says the color. If the person in front of you has a red hat you should stretch out the color you say. example...instead of saying "black" say "bllllllaaaaaaaaaaaaacccccccckkkkkkkkkkk" and that means red. if you're going to say red, instead of saying "red" say "reeeeeeeeeeeeeeeeeeeeddddddddddddddddddddddddddddd". that too means red.

If the person in front of you has a black hat you should just say "black" or "red" normally.

Be sure that you listen to how long the person directly behind you says the color of his hat. it doesn't matter what color they say, just if they stretch it out or not...how they say it.

need more explaining...just ask or email me.

19 saved, 20th with a 50% chance.

[Guest]

Okay.. but am I missing something?? There is no statement in that riddle which says that there has to be equal numbers of Red and Black Hat, that implies that POSSIBLY everyone could have all Black hats ...

Anyways here's my solution and do let me know if somethings up with it!

20th is a chance save. 50-50, all he can do is save the other by just saying the color of the hat of the person in front of him. This is the most logical/sensible way to do it. Even if he counts 10 black and 9 red, the probability that he has either is still 50%. He might just as well save the one in front of him. And then they pass this down the line. so they end up saving 10 surely, while the other 10 have 50-50 chance of making it.

The problem with this theory, is if you are the last person and the person in front of you has a red hat, you can say "red" to let him know (and yes, you have a 50/50% chance of having the same) HOWEVER the next guy in line will SURELY say "red" knowing that is the color of his OWN hat...but then what about the NEXT guy in line?