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 way I see it, the first guy to say anything is taking a chance which is agreed upon by the whole group the night before. Since there is NO communication which can be passed on during the questioning process then there can be no way of secretly telling the person what color his hat is. There is also no guarantee that the King will use the same number of black or red hats, he may choose to use all black hats. The prisoners could agree that when asked what color his hat is, he simply says the color of the hat that is on the person in front. The only one that takes the chance with all lives is the 1st person asked. This would of course not guarantee any or all lives since he is taking a chance, if the man in front has the same color hat as he then all will survive, if wrong then they all die. No communication, means no communication, thus this is the only solution which might saved all lives easily if the first is correct.

[andromeda]

It s really simple. The 20th person in the row can not guess his hat color. So, he is against a 50-50 decision. there is not any difference to him to call "RED" or "BLACK". Therefore, when the king asks him about his hat color, he can reply the color of the person just in front of him. in this way he has a chance of 50 percent and the person just in front of him has a chance of 100 percent. In this way the 20th, 18th, 16th, ... persons tell the color of 19th, 17th, 15th, ... persons in the row. so, all odd persons will save and all even persons have the chance of 50 percent to save. at least 10 persons will save in this way.

good luck

just ask me ur questions because I HAVE ALL SOLUTIONS

Well... since this solution is not quite right (I thought of this as well ) I'm not so sure about the other solutions you might have?!

Welcome to the Den and use spoilers!

It doesn't matter that you didn't use spoilers here because it had already been solved!

Nice try!

Edited November 16, 2008 by andromeda

[Guest]

As prearranged, the first prisoner to guess (#20) states the opposite of the color he sees #10 wearing and secures a 50% chance while #10 is saved. #19 does the same with #9 and so on. Ten prisoners are guaranteed a walk and ten get a 50% chance.

[Guest]

I think the telling the color loudly & normally is just right........ otherwise you need to know the number of red & black hats atleast....

[Guest]

So i was just randomly google-ing brain teasers and i stumbled upon this one and i ended up registering here...

so here is my assumption.. take note it can save the 20 prisoners 100% haha

in the riddle it says that they have the whole night to discuss everything they want.. and consider also the term SAVE

basically they just need to pray to their God, if they were Christians, Allah if Muslim, Vishnu Buddha, etc. for the whole night.

on the day of execution the 20th person would just say out loud the name of his deity, and all of them will be killed

for example

p20: "*^!@(*"

King: Kill them all

Narator: p1-p20 met each other in heaven..nirvana..being reborn as cows, whatsoever. They were all saved and lived ever after.

nevermind me.

[Guest]

Here's another solution.

The first person either pauses before guessing or answers straight away. If there was a pause then the colour of the person's hat in front of him is opposite to his guess, otherwise the same. After the first person there is no guess work involved.

Another option would be to just say Blaaaaack or Reeeeed if the person in front is different to your guess else a quick Black or Red if it's the same.

There are plenty of ways to pass information to the person in front of you. (And they are still within the rules of the puzzle!)

Edited November 20, 2008 by ThomasB

[bonanova]

Here's another solution.

The first person either pauses before guessing or answers straight away. If there was a pause then the colour of the person's hat in front of him is opposite to his guess, otherwise the same. After the first person there is no guess work involved.

Another option would be to just say Blaaaaack or Reeeeed if the person in front is different to your guess else a quick Black or Red if it's the same.

There are plenty of ways to pass information to the person in front of you. (And they are still within the rules of the puzzle!)

Many have suggested ways to pass information other than the distinction between two responses,

but that certainly is not the challenge that the OP poses.

It's a fine line sometimes between solving the intended puzzle and finding loopholes.

I think in this case, the answer to the harder option is so cool it kind of demeans the puzzle to circumvent it.

But it's arguable these suggestions don't violate the terms.

[Guest]

Here's another solution.

The first person either pauses before guessing or answers straight away. If there was a pause then the colour of the person's hat in front of him is opposite to his guess, otherwise the same. After the first person there is no guess work involved.

Another option would be to just say Blaaaaack or Reeeeed if the person in front is different to your guess else a quick Black or Red if it's the same.

There are plenty of ways to pass information to the person in front of you. (And they are still within the rules of the puzzle!)

your answer seems the easiest and most common way to get it. I'm surprised that all of you intelligent people went to the hardest options, overlooking this. Oh well.

[bonanova]

your answer seems the easiest and most common way to get it.

I'm surprised that all of you intelligent people went to the hardest options, overlooking this.

Oh well.

Hi Neptune, and thanks for your comment.

The reason for hard options is to answer the problem as stated.

The ONLY information each prisoner is given permission to provide is "red" or "black".

Sometimes a puzzle appears to have no solution and the answer is a loophole in how it was stated.

The clear intention of this puzzle is to find the best solution from a single bit of information.

[Jiminy Cricket]

Hi Neptune, and thanks for your comment.

The reason for hard options is to answer the problem as stated.

The ONLY information each prisoner is given permission to provide is "red" or "black".

Sometimes a puzzle appears to have no solution and the answer is a loophole in how it was stated.

The clear intention of this puzzle is to find the best solution from a single bit of information.

Perhaps the puzzle should be ammended to read that every man, being bound and gagged, would first have to decide what he wants his answer to be and then he WRITES IT ON A PIECE OF PAPER, and hands it to the guard who will then inspect while he walks to a podium where he will then, in a monotone voice, simply state either "red" or "black". If the writing was not clearly legible the guard might utter the wrong word which would result in instant death for every prisoner (and those searching for loopholes) as they would all be on their own gallows with ropes securly fastened around their necks and hands shackled behind them - only the man whose guess it was would be temporarily unshackled just long enough to write either "red" or "black before immediately having his hands reshackled behind his back.

Once the guard monotones his one word answer, should that single man have guessed correctly, he would then be removed, gagged and shackled, to another area out of view from the remaining prisoners so that they would not know the outcome of his fate.

[Guest]

I admit, I like the first person guessing his own by calling out the color of the man in front of him, thus giving the 19th his color and so on and so on so that 19 are guaranteed to be saved with the 20th at a 50/50. However, I wanted to toy with the wording of the question a bit and offer a very (very very) simple solution: Can every prisoner just say "black or red"? They should all live because the hat on each of their heads is, in fact, black OR red. I know the words are separated by quotes and are capitalized, but the three words together as a phrase are also part of his entire speech and he doesn't ever say one word only ... Oh, I got tired of searching every single post to see if someone else says this too, so I apologize if someone already has - I have seen nothing about it to this point.

P.S. Glad to join a new group of intelligent thinkers - looking forward to your thoughts and comments.

[Guest]

I admit, I like the first person guessing his own by calling out the color of the man in front of him, thus giving the 19th his color and so on and so on so that 19 are guaranteed to be saved with the 20th at a 50/50. However, I wanted to toy with the wording of the question a bit and offer a very (very very) simple solution: Can every prisoner just say "black or red"? They should all live because the hat on each of their heads is, in fact, black OR red. I know the words are separated by quotes and are capitalized, but the three words together as a phrase are also part of his entire speech and he doesn't ever say one word only ... Oh, I got tired of searching every single post to see if someone else says this too, so I apologize if someone already has - I have seen nothing about it to this point.

P.S. Glad to join a new group of intelligent thinkers - looking forward to your thoughts and comments.

Well, I might as well comment on my own thoughts, since the first part is wrong and I'd rather call myself out than wait for one of you to do it - you can't inform the person in front of you of their color with a guarantee that their color matches yours (i.e. if you have different colors, you die - or, the only people that live are the ones with a hat that matches the person in front of them).

Still wondering about what people think of the way the question is written and how my solution plays into that ...

[bonanova]

I admit, I like the first person guessing his own by calling out the color of the man in front of him, thus giving the 19th his color and so on and so on so that 19 are guaranteed to be saved with the 20th at a 50/50. However, I wanted to toy with the wording of the question a bit and offer a very (very very) simple solution: Can every prisoner just say "black or red"? They should all live because the hat on each of their heads is, in fact, black OR red. I know the words are separated by quotes and are capitalized, but the three words together as a phrase are also part of his entire speech and he doesn't ever say one word only ... Oh, I got tired of searching every single post to see if someone else says this too, so I apologize if someone already has - I have seen nothing about it to this point.

P.S. Glad to join a new group of intelligent thinkers - looking forward to your thoughts and comments.

You've pretty well answered your question already.

1. If the OP is equivalent to
   You may answer "BLACK" or you may answer "RED". If you say anything else, all will die.
   Then saying "BLACK or RED" is a fatal idea.
   
   
   
2. If it's equivalent to
   You may answer "BLACK or RED". If you say anything else, all will die.
   then your idea is the only permissible approach, and all will escape by saying it.
   

It's fairly clear the first meaning is the intended one.

[bonanova]

Perhaps the puzzle should be ammended to read that every man, being bound and gagged, would first have to decide what he wants his answer to be and then he WRITES IT ON A PIECE OF PAPER, and hands it to the guard who will then inspect while he walks to a podium where he will then, in a monotone voice, simply state either "red" or "black". If the writing was not clearly legible the guard might utter the wrong word which would result in instant death for every prisoner (and those searching for loopholes) as they would all be on their own gallows with ropes securly fastened around their necks and hands shackled behind them - only the man whose guess it was would be temporarily unshackled just long enough to write either "red" or "black before immediately having his hands reshackled behind his back.

Once the guard monotones his one word answer, should that single man have guessed correctly, he would then be removed, gagged and shackled, to another area out of view from the remaining prisoners so that they would not know the outcome of his fate.

How about:

Every prisoner, each in his own transparent soundproof shell, has a keyboard with a black button and a red button .

The keyboard unlocks when it's his turn, and locks again after one of the buttons is pushed.

When the jailer decides to do so, he presses a button that displays "prisoner 13 has chosen BLACK", e.g., on a large screen that all can see.

The turn passes to the next prisoner.

etc.

No extra words, no verbal intonations, no prisoner-chosen delays, etc....

[Guest]

It is possible to get 99% guaranteed, and 99.5% on average. 99.0% and 100% will be equally likely.

The strategy:

The wizard in the back, #100, states white if there are an odd number of whites caps in front of him, or black for odd blacks.

From this, the 99th wizard knows his own color; If #99 sees the parity for that color change, he knows he wears the color that #100 proclaimed.

#99 then states his own color.

From this, the 98th wizard knows his own color; He knows what #100 said about the parity in front of him, he knows the color of #99, and he knows the parity he sees in front of him.

#98 then states his own color.

The same goes for the rest of the wizard -- they all know and state the correct color

However, there is only a 50% chance that the cap color of wizard #100 happens to be the same as the color he initially calls out.

Edited December 18, 2008 by corporate-target

[Guest]

Nice job corporate-target! Your solution entirely makes sense. If i was a # in that line i would use your solution.

[Guest]

Nice job corporate-target! Your solution entirely makes sense. If i was a # in that line i would use your solution.

Except isnt' this thread about 20 prisoners facing death, rather than 100 wizards?

[Guest]

how many times are people going to restate the answer over and over before we close this thread?

[andromeda]

how many times are people going to restate the answer over and over before we close this thread?

This thread won't be closed because it's on the Best Puzzles page!

EDIT: This riddle is the reason I joined BD!

Edited December 19, 2008 by andromeda

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

I thought about it last night. The solution above is correct.

[Guest]

#20 would say what color #1s hat is,#19would say what color #2s hat is and so on up the line. 10+ would be saved from death.

[Guest]

"One of my favorites"!?

Please, reconsider!

[Guest]

If every prisoner states the color of the prisoners hat in front of them, then 10 prisoners are guarenteed to survive.

[bonanova]

If every prisoner states the color of the prisoners hat in front of them, then 10 prisoners are guarenteed to survive.

Not quite - that would free those who stood behind a prisoner with the same color hat. If the colors alternated, no one would survive.

If the even number prisoners state the color in front of them and the odd prisoners state the color they've just heard, 10 are guaranteed to survive.

Probably you meant to say that.

[Guest]

It is possible to get 99% guaranteed, and 99.5% on average. 99.0% and 100% will be equally likely.

The strategy:

The wizard in the back, #100, states white if there are an odd number of whites caps in front of him, or black for odd blacks.

From this, the 99th wizard knows his own color; If #99 sees the parity for that color change, he knows he wears the color that #100 proclaimed.

#99 then states his own color.

From this, the 98th wizard knows his own color; He knows what #100 said about the parity in front of him, he knows the color of #99, and he knows the parity he sees in front of him.

#98 then states his own color.

The same goes for the rest of the wizard -- they all know and state the correct color

However, there is only a 50% chance that the cap color of wizard #100 happens to be the same as the color he initially calls out.