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]

ADDENDUM

You are the first to guess, and thus the "sacrificial lamb". The guard, who is truthful, offers to answer any single yes-or-no question that you put to him. This is your chance to escape execution! But you decide it's better to sacrifice yourself, if necessary, than to leave your buddies to execution. What single yes-or-no question can you ask that will insure your own survival as well as that of your comrades? (Assume the guard knows all the conditions of the execution.)

"Will the total number of hats of my hat color be even?" If so, then you want to guess the odd number of hat colors you count (since there must be an even number of each hat color); if not, you guess the even number (since there must be an odd number of each hat color). Just set that as the initial condition for your friends to follow, do as described previously, and everyone gets out okay.

[roolstar]

You are the first to guess, and thus the "sacrificial lamb". The guard, who is truthful, offers to answer any single yes-or-no question that you put to him. This is your chance to escape execution! But you decide it's better to sacrifice yourself, if necessary, than to leave your buddies to execution. What single yes-or-no question can you ask that will insure your own survival as well as that of your comrades? (Assume the guard knows all the conditions of the execution.)

Great job there spoxjox!

But as you said, YOU ARE the first to guess (post) an answer for this puzzle (on the forum) so your solution will be dissected and scrutinized…

But let me first clarify: for this puzzle your solution is correct, but I invite you to find an answer that will be suitable for ANY number of prisoners (more than 1).

Because your technique does not work for 19 prisoners; in scenarios where we have 7 Black hats and 11 Red ones for example in front of the "sacrificial lamb" in the back.

Now don’t get me wrong, your solution works perfectly for the initial puzzle (taking into consideration that 0 hats is an even number of hats of course), but is there a universal way for any number of prisoners?

PS: It’s incredibly close to your technique!

[Guest]

But let me first clarify: for this puzzle your solution is correct, but I invite you to find an answer that will be suitable for ANY number of prisoners (more than 1).

Because your technique does not work for 19 prisoners; in scenarios where we have 7 Black hats and 11 Red ones for example in front of the "sacrificial lamb" in the back.

Now don’t get me wrong, your solution works perfectly for the initial puzzle (taking into consideration that 0 hats is an even number of hats of course), but is there a universal way for any number of prisoners?

PS: It’s incredibly close to your technique!

How about this:

Guess "red" if you see an odd number of each hat color, and guess "black" if you see an even number of each color. This will give the other prisoners the information they need to make (consecutively) the right choice of their own respective hat color.

What if you don't know how many prisoners will be selected before you get to the execution? I guess you just combine the two methods, and each prisoner has to keep track of both possibilities until it's his turn.

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

[Guest]

How's this one?

Great idea, but perhaps a bit complicated to ensure each person is counting seconds correctly. I like it, so here's a twist:

If the 2nd person in line is red, the 1st person guesses quickly. If the 2nd person is black, the first person takes a long minute to guess. The first person is signaling to the second person the color of their hat this way. When it's the second person's turn, they do the same thing. If the first person quessed quickly, # 2 knows his own is red. If # 3 is also red, #2 will say Red quickly also. If # 3 is black, then #2 will take his time before saying his own color of Red. Each person repeats down the line. credit to Jason for this ingeneous idea - I just tweaked it.

[roolstar]

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

Good thinking you guys, and there are even more ideas to solve it this way: there is the tone of voice (high or low pitch), the volume (screaming or normal), timing (suggested)....

But we wanted to stay restricted to a system where a simple and neutral "BLACK" & "WHITE" will provide a bullet proof technique to save ALL BUT ONE of the prisoners (one of them will have a 50-50 chance of surviving).

And here's my final challenge:

FIND A WAY THAT WILL SOLVE THE PROBLEM FOR ANY NUMBER OF PRISONERS (20 or 19).

PS: Bonanova already found it... And you are very close: just twist the most successful technique for a bit.

[unreality]

There are so many answers which have been said to be "right" or "close to right" i'm confused... which is the right answer? at least the most right answer so far? You can just point me to whose post

[unreality]

Ah I see now! Awesome!

[Guest]

bonanova cracks it out of the ballpark! Great job!

This is really fascinating to me. I consider myself a reasonably intelligent person, yet it took lots of hints and many tries by others before I stumbled upon a workable solution. Then, when the problem was made just a bit more general, my best solution was to keep two completely separate ideas in mind while you worked through the problem. It would have worked...but only if the prisoners had excellent memories and the ability to keep juggling two or three changing sums the whole time.

Then bonanova introduces what is, in effect, a simplified version of my solution -- and it's perfect! Easy (easier than my original, even), 100% effective, and works for any number of prisoners.

I wonder: What is it that allows people to step outside their own mental processes and see a result like this? When I read it, it's so obvious that, had I not tried to solve it myself, I would have perhaps assumed that it was easy, that surely I would have figured it out in a minute or so on my own. It takes real genius to say something new and to which hearers respond, "Yes, that's obvious."

[roolstar]

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

[bonanova]

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?

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

[Guest]

YOU COULD JUST ASK YOUR OTHER CELLMATES, "WHAT COLOR IS MY HAT???" IF YOUR CELLMATES AREN'T SICK AND CRUEL, THEY WOULDN'T LIE, GUARANTEEING YOUR SURVIVAL.

[Guest]

19 it is. With 20th having 50% probability.

Had solved it long time ago. One of my favs.

Anyway .. my logic is that:

20th says Red if the no. of Red hats he see is Even. Says Black if its Odd.

Rest is simple!

If 19 sees no. of even Red hats in front of him and he heres Black from the 20th he knows he's got to be Red. if he heard Red, then he knows he got to be Black and so on ....

[roolstar]

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

I agree...

In fact I gave up on the idea after the post since every prisoner has to count the ones in front of him to determine him/herself, which means replacing every 0 & 1 will still be another number (not very effective for compression I guess)!

[unreality]

This is an awesome riddle btw I voted 5 stars ;D

[roolstar]

This is an awesome riddle btw I voted 5 stars ;D

Thank you...

I apreciate it!

Especially coming from a PUZZLE MASTER...

And by the person who set the voting rules too!!!

Edited February 19, 2008 by roolstar

[Guest]

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?

ok this may sound weird but there is a chance from 0 or 20 you see if the king is really cruel he could have but white hats on there heads therfore a possibility of 0 living or he might not be that cruel and may i remind you if one person answers wrong they all die soe that makes it impossible for 19 to live or does it?

[roolstar]

ok this may sound weird but there is a chance from 0 or 20 you see if the king is really cruel he could have but white hats on there heads therfore a possibility of 0 living or he might not be that cruel and may i remind you if one person answers wrong they all die soe that makes it impossible for 19 to live or does it?

I'm not sure I follow you there... RED PART

Even if he puts white hats on all their heads, they can still use the technique that we figured out on this forum and survive. (at least 19 of them)

GREEN PART

If the king tells each prisoner if he got the right answer or not just after they answer, the rest can still reason and survive...

Example:

Prisoner 10 screws up and says the wrong color (BLACK for example), the king tells him that he got it wrong and that he's gonna die, prisoner 9 can continue the reasonning after considering that Prisoner 10 had a WHITE hat and survive, the rest will follow...

[Guest]

cant the first person tell the person in front what colour hat they are wearing and so on... then so long as they are all truthfull all should be saved exept the first one who only has a 50/50 chance.

[bonanova]

cant the first person tell the person in front what colour hat they are wearing and so on... then so long as they are all truthfull all should be saved exept the first one who only has a 50/50 chance.

A person dies unless he speaks the color of his own hat.

Saying the color of the hat of someone else could get him killed...

[roolstar]

cant the first person tell the person in front what colour hat they are wearing and so on... then so long as they are all truthfull all should be saved exept the first one who only has a 50/50 chance.

This technique saves 10 prisoners for sure and the rest will have 50/50 chances...

[Guest]

as far as i'm aware this puzzle requires there to be equal numbers of red and black hats, though this is a variation on the one i know so that may not be so

[Guest]

My method will save a minimum of 10 people, mabe more.

The last man calls out the colour of number 1's hat, 19 calls out the colour of 2's hat and so on. The firts 10 will then know the colour of their hats and 11 to 20 have a 50/50 chance of getting their own colour correct.

[Guest]

Even if he puts white hats on all their heads, they can still use the technique that we figured out on this forum and survive. (at least 19 of them)

I don't think so. I think the white hat trick is a pretty twisted but surefire way to ensure mass execution, since, according to the rules ...

He will be only allowed to answer “BLACK” or “RED”. If he says anything else you will ALL be executed immediately.

Glad that sicko isn't my king.

[Guest]

awesome puzzle roolstar. I want to get a group of friends together and try it to see if we're smart enough to save ourselves.