• 0

Hats on a death row!! One of my favorites puzzles!

Question

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

474 answers to this question

  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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?

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

:P
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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>

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

Ah I see now! Awesome!

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

This is an awesome riddle btw :D 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 by roolstar
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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? :unsure:

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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? :unsure:

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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. :P

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

This is confusing

Edited by Nebukhadnezzar
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.