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 Last person in line is a 50/50 guess but if he agrees to say the color of the hat infront of him he will spair the remaining 19 by communicating forward what color the next person should choose.

[Guest]

The answer is right down here (providing that there is 10 of each hat):

The guy in the back sees 19 hats in front of him, so he says the color hat that is odd(lets say it was black). If the 19th guy sees an equal number of hats, his hat would have to be black. if he saw an odd number of black hats, than his hat would have to be red. This continues on to ensure the safety of the front 19 people, but a 50% chance for the back person.

[unreality]

it's not necessarily 10-10, it could be anywhere from 20-0 to 0-20

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

My solution will save 19 out 0f 20.

Here is the perfect solution, that works for all numbers; Assume Red as '1' and Black as '0'. The 20th person add all zeros and ones. If the total comes an even number, he should say, Black' and if it is odd number, he should say 'Red'. Next person can add up the remaining ones and zeros and find out his color.

Example; if the 20th person said Black, the total is an even number. Next person can add the remaining numbers and if he finds that the total is an 'even' number, his color should be 'o', That is Black,.... .

I hope everyone understood the solution.

[Guest]

My solution will safe 19,5 of the crooks i think.

I never saw in the puzzle there where 10 red and 10 black hats, that way you could save 20.

The first prisoner has to guess because he can not know the color of hit hat so he has a 50/50 chance.

He may say one word only "Red" or "Black".

He is able to say the word in a certain way. He can say:"B-lack" (make the B longer) if the person in front of him has a black hat.

He can say:"Black" (faster) if the person in front of him has a red hat. The same for the word red.

You can also change pitch. High pitch -> person in front has red. Low pitch -> person in front has Black.

You can also use different pitches.

I do not know whether this is a legal solution but i think it works.

I did not know the riddle but i am a magician, they think in a strange way and are too lazy to work......

[Guest]

Your hint about 2 possibilities made it suddenly clear. Try this:

The first speaker counts the number of red vs black hats on the remaining 19. Whichever there are more of, is the color he says his is. Since there are 19 remaining, there must be more of one color or the other.

2nd speaker also counts the number of red vs black on the remaining 18. Based on the first person's pronouncement, he knows which color there should be more of on the 18 plus his own. He compares what he sees and knows which color his own hat must be.

3rd-20th speaker should be keeping track of the the changing number left based on each previous speakers correct pronouncement and can compare that to the number they see in front of themself. They will be able to correctly deduce their own color.

to illustrate as an example:

#1 sees 10 red and 9 black (10R/9B), he says red -maybe gets lucky and survives, if not he is the 1 sacrifice we knew we might have, brave soul that he was.

# 2 sees either 10R/8B or 9R/9B on the remaining 18 in front of himself. He knows there should be 10R/9B including his own so he knows which his must be.

# 3 knows from the original 10R/9B, accounts for the correct answer that #2 gave, then deduces his own color from what he sees in front of him.

# 4 - 20 repeat, keeping track of the running count of R & B vs what he sees in front of himself.

example 2

#1 sees 18R/1B - says R - maybe gets lucky on his own.

#2 two possibilies: he sees 18R/0B and knows he's B or he sees 17R/1B and knows he's R

etc.

This should work no matter what the initial distribution of hats is.

Your logic is somewhat flawed... If the 20th guy, the first to speak says red b/c red outnumbers black the 19th guy in line, the second to speak would have no clue to the distribution of colors. Say he (#19) or #2 as you called him sees all red in front of him. He would have no idea whether or not his hat was red or black because the possibility exists that they are all be red and he would only have a 50/50 chance as well.

[Guest]

My solution:

the last man in the queue who will be the first to answer the question will simply guess the color of his hat (good luck on his 50-50 chance) but will either shout out LOUD or in a normal voice. If he shouts out LOUD, it means that the man directly in front of him has the same color as the one in front of him and if in a normal voice his hat is the same as the one in font of him. To illustrate, let's say the men in the queue are (from behind): A,b,C,d,e,F... where small letters are wearing black hats and capitals are wearing red hats. A will say in a normal voice "red", b during his turn will say in a normal voice "red", C will shout "BLACK", D will say in a normal voice "red", etc... The last man will say the same color as the one behind him if he shouted.

shouting is not saying any other thing or is not a violation of the King's rules.

[bonanova]

My solution:

the last man in the queue who will be the first to answer the question will simply guess the color of his hat (good luck on his 50-50 chance) but will either shout out LOUD or in a normal voice. If he shouts out LOUD, it means that the man directly in front of him has the same color as the one in front of him and if in a normal voice his hat is the same as the one in font of him. To illustrate, let's say the men in the queue are (from behind): A,b,C,d,e,F... where small letters are wearing black hats and capitals are wearing red hats. A will say in a normal voice "red", b during his turn will say in a normal voice "red", C will shout "BLACK", D will say in a normal voice "red", etc... The last man will say the same color as the one behind him if he shouted.

shouting is not saying any other thing or is not a violation of the King's rules.

Communication other than saying a color is banned.

This solution violates the ban - it can be seen to fail if all that's communicated is red or black.

If the loudness of the speaker's voice adds useful information, then it's a banned communication.

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

The puzzle didn't say that there were the same amount of hats (10 red hats and 10 black hats) so your solution wouldn't work. For all we know there are only 5 red hats so it would make this puzzle extremely difficult to answer

[bonanova]

The puzzle didn't say that there were the same amount of hats (10 red hats and 10 black hats) so your solution wouldn't work.

For all we know there are only 5 red hats so it would make this puzzle extremely difficult to answer

Where did you come up with the idea there were 10 red hats and 10 black hats?

Construct a sequence of 5 red and 15 black hats and try the method.

Tell us how it comes out.

[Guest]

i say you cant guarantee any of their lives. it says the king is a ruthless man. who knows if he'll keep his word?

[bonanova]

i say you cant guarantee any of their lives. it says the king is a ruthless man. who knows if he'll keep his word?

When you solve a puzzle, you take the statements as true.

Otherwise you're solving something else.

Under the statement of the problem, you can guarantee the lives of 19 prisoners.

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

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

Here is the perfect solution, that works for all numbers; Replace Red with '1' and Black with '0'. The 20th person add all zeros and ones. If the total comes an even number, he should say, Black' and if it is odd number, he should say 'Red'. Next person can add up the remaining ones and zeros and find out his color.

Example; if the 20th person said Black, the total is an even number. Next person can add the remaining numbers and if he finds that the total is an 'even' number, his color should be 'o', That is Black,.... .

I hope everyone understood the solution.

[bonanova]

Here is the perfect solution, that works for all numbers; Replace Red with '1' and Black with '0'. The 20th person add all zeros and ones. If the total comes an even number, he should say, Black' and if it is odd number, he should say 'Red'. Next person can add up the remaining ones and zeros and find out his color.

Example; if the 20th person said Black, the total is an even number. Next person can add the remaining numbers and if he finds that the total is an 'even' number, his color should be 'o', That is Black,.... .

I hope everyone understood the solution.

Hi shijumonantony, and welcome to the Den!

What's needed is to determine the parity of the black hats and update as we go through the line of prisoners.

Whether we count black hats [posted solution] or assign them '1' and red '0' and do the artithmetic [your solution]

what we're doing is determining the parity [oddness or evenness] of the black hats.

The solutions are logically identical, and it works for any distribution of hat colors and any number of prisoners.

[Guest]

Hey all, I am new to the forum, but I read the riddlles on this a lot.

Me and my friend got a problem very similar to this in our AP Stat class today just for fun. We saved the same amount of people but with a different solution. I was trying to find the faults in it:

First man looks at the man closest to him with a white hat. He says white, then says it again for every space in between them. For instance, if the next man with a white hat was right in front of him, then he would say "white, white." If the next white hatted man in front of him was 4 spaces away, he would say "white white white white white."

Now, all the men in between those men in white hats know that their hats are red, because the are of course not white.

The second white hat repeats his color: white. Then he follows first mans pattern and sends the message to the next white hat by saying "white" for each space that is between them. This continues until the last white hat can only see reds, in which he says only his own color. Then the rest are red (if any).

Now, all the men in between those men in white hats know that their hats are red, because the are of course not white.

This can be reversed, just starting with the first man saying red red etc...

Works?

[bonanova]

Hey all, I am new to the forum, but I read the riddlles on this a lot.

Me and my friend got a problem very similar to this in our AP Stat class today just for fun. We saved the same amount of people but with a different solution. I was trying to find the faults in it:

First man looks at the man closest to him with a white hat. He says white, then says it again for every space in between them. For instance, if the next man with a white hat was right in front of him, then he would say "white, white." If the next white hatted man in front of him was 4 spaces away, he would say "white white white white white."

Now, all the men in between those men in white hats know that their hats are red, because the are of course not white.

The second white hat repeats his color: white. Then he follows first mans pattern and sends the message to the next white hat by saying "white" for each space that is between them. This continues until the last white hat can only see reds, in which he says only his own color. Then the rest are red (if any).

Now, all the men in between those men in white hats know that their hats are red, because the are of course not white.

This can be reversed, just starting with the first man saying red red etc...

Works?

Hi Striker,

Sure it works, but so does this:

• "The prisoner in front of me has a white hat"
  
• "The prisoner in front of him has a white hat"
  
• "There aren't any more white hats after that until we've skipped 4 prisoners"
  
• etc.
  

So you see that unless we restrict each prisoner simply to guess his own hat color, there's not much of a puzzle left.

That means each prisoner just says "white" or "black" - nothing more or less.

Hope to see some of your own puzzles posted here soon.

Enjoy!

- bn

[Guest]

It is key when thinking laterally that you make NO assuptions, and obey exactly the terms you are given.

With this is mind, we have no way of knowing how many red hats there are. There could be 20!

So you can guaruntee to save only 10 men.

First man has to say hat colour of the second man's hat. The second man repeats the answer of the first man. The third man says the colour of the fourth man's hat, who repeats the answer. You get my drift...

Edited October 14, 2008 by dtreddevil

[bonanova]

Actually the correct answer has not been submitted yet. It is key when thinking laterally that you make NO assuptions, and obey exactly the terms you are given.

With this is mind, we have no way of knowing how many red hats there are. There could be 20!

So you can guaruntee to save only 10 men.

First man has to say hat colour of the second man's hat. The second man repeats the answer of the first man. The third man says the colour of the fourth man's hat, who repeats the answer. You get my drift...

Hi dtreddevil and welcome to the Den.

A solution that makes no assumptions of the color distribution has been posted.

It guarantees the freedom of all but one of the prisoners.

Your method guarantees only half. Yet you say the correct answer has not been submitted.

Care to share your thoughts on that?

- bn

[Guest]

Another simple riddle to solve.. My equation figures a 75% survival rate with a guaranteed 50% survival rate.. barring a few sadistic inmates. The last inmate yells the color of the first person in the lines hat color. He has a 50% chance to survive, the first person has 100% survival rate. The 2nd to the end calls out the 2nd person in lines hat color. Same thing, 50% for him, 100% for man number 2. By the time 10 people call out their hat color with a 50% survival rate, barring some sadism.. the last 10 will know their hat color.

JP

--Edit --

Hat color and distribution doesnt matter, the first 10 in line could literally have 10 different hat colours, the equation still has a guaranteed 50% survival rate.

Edited October 17, 2008 by smartguy007

[bonanova]

Another simple riddle to solve.. My equation figures a 75% survival rate with a guaranteed 50% survival rate.. barring a few sadistic inmates. The last inmate yells the color of the first person in the lines hat color. He has a 50% chance to survive, the first person has 100% survival rate. The 2nd to the end calls out the 2nd person in lines hat color. Same thing, 50% for him, 100% for man number 2. By the time 10 people call out their hat color with a 50% survival rate, barring some sadism.. the last 10 will know their hat color.

JP

--Edit --

Hat color and distribution doesnt matter, the first 10 in line could literally have 10 different hat colours, the equation still has a guaranteed 50% survival rate.

Welcome to the Den smartguy...

Sure, that works. 50% certain, 75% expected results from pairwise "communication" at least two ways [adjacent and end-wise].

The trick is to ensure freedom for all but the first to speak.

[Guest]

also new

but my solution

there is a common signal, like a cough before the guess

this is used if the person in front of the guesser has a black hat

so the first person guesses, and if the second person has a black hat, he coughs first.

if the person in front of him has a red hat, he just guesses.

NOW THIS ONLY WORKS IF THE PRISONERS ARE NOT SICK AND ARE ALSO TRUTHFUL.

[Guest]

What if they had a system to recognized the dialog of one another saying the hat color ?

If the persons hat infront of him is the same color, thens ay your hat color with a normal voice/tone.

If the hat is opposite, maybe take a slight breathe in then say your hat color, this little sign will give way. You can convieve hundreds of minor hints to distinguish opposite colors.

I say all 20 of them revolt and kill the guards/king, you know how hard it is to kill 20 guys in a row without guns back then ? Far better chance that way

[bonanova]

What if they had a system to recognized the dialog of one another saying the hat color ?

If the persons hat infront of him is the same color, thens ay your hat color with a normal voice/tone.

If the hat is opposite, maybe take a slight breathe in then say your hat color, this little sign will give way. You can convieve hundreds of minor hints to distinguish opposite colors.

I say all 20 of them revolt and kill the guards/king, you know how hard it is to kill 20 guys in a row without guns back then ? Far better chance that way

This has been suggested a bazillion times.

No information other than the color may be communicated.

Read the OP.

And what about the machine guns in the guard tower?

[Guest]

I can save at least 50% no matter what the distrubtion of color is. Since the first guy will see the 19 hats in front of him, he simply says the color of the majority of hats. At least 10 will be saved no matter the number of red or black will be. It's funny cause thats still the odds of getting it right 50/50, but it's a more educated guess. If i were the king I'd start with the first guy who can't see anything, plus the other remaining guys would have to watch their fellow inmate get executed, what a tyrant.