A gruesome puzzle

If the red house has blue shutters and the green house has red shutters, what's this section for?
User avatar
deformation gradient
New Member
Posts: 16
Joined: Tue Apr 11, 2006 7:30 pm

A gruesome puzzle

Postby deformation gradient » Mon May 08, 2006 4:37 pm

I heard this puzzle at a dinner at Caltech, so I can't take credit for it. But I like it.

A group of (highly intelligent) criminals are about to be executed by a sadistic executioner. The executioner tells the criminals that he is going to line them up front-to-back (as opposed to standing side by side), so each can see the people in front of them, but not those behind them. Furthermore, he will turn off the lights, and RANDOMLY place either a red or white hat on each person's head. Then, he'll turn the lights back on. He will ask each person, starting from the BACK of the line, whether they are wearing a red or white hat. If the person answers incorrectly or says anything other than RED or WHITE, that person will be shot. Each person cannot see their own hats, only those of the people in front of them. They can hear, however, what the people behind them say, and whether or not each person gets shot. If anybody speaks out of turn, or makes any movement out of the line, etc... they will also be shot. Anybody who doesn't get shot will be granted amnesty.

After telling them all this, the executioner then leaves the criminals alone in a room for a few minutes. By the time he returns, they have divised a strategy that will ensure that AT MOST one person will get shot, and maybe none at all. What is their strategy?

User avatar
deformation gradient
New Member
Posts: 16
Joined: Tue Apr 11, 2006 7:30 pm

Hint

Postby deformation gradient » Tue May 09, 2006 4:41 pm

Here's a (small) hint:

Spoiler:
This puzzle will be easier for those who know anything about basic error correction (in computer science). However, that doesn't mean those who don't should give up (my wife got it, and she's not in CS)! :wink:
Last edited by Pyrrho on Fri May 01, 2009 11:22 pm, edited 1 time in total.
Reason: Edited to fix spoiler code.

User avatar
Flea
Regular Poster
Posts: 527
Joined: Fri Feb 03, 2006 9:17 pm

Postby Flea » Tue May 09, 2006 6:11 pm

Here's the way I'd do it:

Spoiler:
The first guy at the back guesses, saying red or white, but using tone of voice (or something like that) to indicate if the guy in front of him has a hat of the same color that he's saying. For example, if he says RED!!! it means the guy in front of him has a red hat. If he says red in a teeny voice, the guy in front has a white hat. Whether or not the first guy gets shot, the second guy still knows what color his own hat is, and can name his own hat color and the hat color of the guy in front of him.
Last edited by Pyrrho on Fri May 01, 2009 11:22 pm, edited 1 time in total.
Reason: Edited to fix spoiler code.
Gravity is a harsh mistress.

User avatar
Bearguin
Poster
Posts: 295
Joined: Tue Mar 29, 2005 5:00 pm

Postby Bearguin » Tue May 09, 2006 6:19 pm

My answer

Spoiler:
They all decide that the first guy looks at all the hats in front of him. If he sees an even number of white hats, he will guess "white". If he sees an odd number of white hats, he will say "red". He has a 50/50 chance of being correct (and living) but gives enough information to the rest of them that they can determine their hat color.

If number 1 says "white" and number 2 sees an even number of white hats, then he has a red hat. Then number 3 (paying attention) sees and odd number of white hats, he know he has a red hat. As long as each person pays close attention they can keep track of the even/odd white hats the person ahead of them sees and can determine their hat color.
Last edited by Pyrrho on Fri May 01, 2009 11:22 pm, edited 1 time in total.
Reason: Edited to fix spoiler code.

User avatar
deformation gradient
New Member
Posts: 16
Joined: Tue Apr 11, 2006 7:30 pm

Success

Postby deformation gradient » Tue May 09, 2006 6:54 pm

Bearguin got it.

I guess, to exclude Flea's answer, I should have added that if they use anything other than a neutral tone of voice, or they don't immediately answer, they will also be shot. :)

User avatar
Flea
Regular Poster
Posts: 527
Joined: Fri Feb 03, 2006 9:17 pm

Postby Flea » Tue May 09, 2006 7:36 pm

well .... yeah ... if you want to get all mathy about it
Gravity is a harsh mistress.

Tino
New Member
Posts: 11
Joined: Fri Apr 24, 2009 1:43 pm

Re: A gruesome puzzle

Postby Tino » Fri May 01, 2009 3:27 pm

OK I know this is old but I just saw it and am puzzled. I don't see that it says there are an equal number of each color. Does the solution require that? For example, if there are 4 prisoners, and they all happen to get white hats, does the solution still work? It doesn't appear to.

Herzeleid
Posts: 2
Joined: Wed Jul 08, 2009 12:37 am

Re: A gruesome puzzle

Postby Herzeleid » Wed Jul 08, 2009 10:01 pm

yes, in addition to the puzzle not mentioning that there are the same amount of red and white hats, if there were the same amount of hats, i.e. 4 white and 4 red, I do not see how it would be possible for ANYONE to not be able to figure out what color hat they are wearing, as the puzzle mentions that possibly one person will die, which seems to imply that it is impossible for one of the soldiers to figure out what color their hat is, and would have to guess with a 50/50 shot of getting it right, however if there were 4 and 4 it would be extremely easy for everyone to figure it out.

[EDIT]
Ah yes... I see how one person could get it wrong, only if there were an odd number of people, he would not know which color is the extra one, of course in this example there is no longer the same amount of each color, the puzzle needs to clarify that there are REQUIRED to be an odd number of criminals and that there will be almost the same number of hats with one color having one extra, in order to proclaim that it is possible for one person to not be able to figure out what color their hat is, and also so we are able to discover the solution.

And actually...... MORE than one person can die. check this out.....

If this is the row of say 7 criminals and here are the order of color hats, starting from the back of the line:

W W W W R R R

In that scenario the first person will see 3 White and 3 Red and have to guess randomly at what color his hat is, lets say he guesses Red, he dies. So the next person knows the first hat was White, and he can see 2 White and 3 Red in front of him for a total of... 3 White and 3 Red, so once again he has to guess randomly at what color is the extra color, let's say he guesses Red, he dies. Now the 3rd person knows that the first two hats were White and he can see 1 White and 3 Red, for a total of, count them, 3 White and 3 Red. Once again he must guess randomly at what color his hat is because he's clueless to which one is the extra color (STILL). Lets say he guesses red, he dies. Now the fourth person knows that the first 3 hats were White and he can see 3 Red hats in front of him, for, indeed, a total of 3 and 3 again and so he must randomly guess, lets say red again (either way its a pure 50/50 shot).... OH NO... I see where I am going wrong.... The second must be able to discern that for the first guy to guess wrong he must have seen the same number of each color hat, so he can assume if he can see 3 Red and 2 White that he must be a 3rd white, because if he were Red the first guy would have seen 4 Red and 2 White and would have known his color was White.

Oh well.... it was a somewhat exhilarating thought experiment anyways......

[END EDIT]

In knowing there are the same amount of each hat it is easy to solve this puzzle; I prefer the answer above about using different tones.

User avatar
bigtim
Perpetual Poster
Posts: 4076
Joined: Thu Feb 16, 2006 7:04 pm
Custom Title: Skeptical Berserker
Location: Miðgarðr

Re: A gruesome puzzle

Postby bigtim » Thu Jul 09, 2009 3:44 pm

The way I'd do it is wait near the door so the executioner comes back in we all beat the crap out of him and take his gun...
~
BigTim
"I'm not entirely convinced that ValHalla isn't real."

Quasi-Skeptic
New Member
Posts: 22
Joined: Mon Apr 04, 2011 3:03 am

Re: A gruesome puzzle

Postby Quasi-Skeptic » Sun May 29, 2011 4:42 am

Herzeleid wrote:yes, in addition to the puzzle not mentioning that there are the same amount of red and white hats, if there were the same amount of hats, i.e. 4 white and 4 red, I do not see how it would be possible for ANYONE to not be able to figure out what color hat they are wearing, as the puzzle mentions that possibly one person will die, which seems to imply that it is impossible for one of the soldiers to figure out what color their hat is, and would have to guess with a 50/50 shot of getting it right, however if there were 4 and 4 it would be extremely easy for everyone to figure it out.

[EDIT]
Ah yes... I see how one person could get it wrong, only if there were an odd number of people, he would not know which color is the extra one, of course in this example there is no longer the same amount of each color, the puzzle needs to clarify that there are REQUIRED to be an odd number of criminals and that there will be almost the same number of hats with one color having one extra, in order to proclaim that it is possible for one person to not be able to figure out what color their hat is, and also so we are able to discover the solution.

And actually...... MORE than one person can die. check this out.....

If this is the row of say 7 criminals and here are the order of color hats, starting from the back of the line:

W W W W R R R

In that scenario the first person will see 3 White and 3 Red and have to guess randomly at what color his hat is, lets say he guesses Red, he dies. So the next person knows the first hat was White, and he can see 2 White and 3 Red in front of him for a total of... 3 White and 3 Red, so once again he has to guess randomly at what color is the extra color, let's say he guesses Red, he dies. Now the 3rd person knows that the first two hats were White and he can see 1 White and 3 Red, for a total of, count them, 3 White and 3 Red. Once again he must guess randomly at what color his hat is because he's clueless to which one is the extra color (STILL). Lets say he guesses red, he dies. Now the fourth person knows that the first 3 hats were White and he can see 3 Red hats in front of him, for, indeed, a total of 3 and 3 again and so he must randomly guess, lets say red again (either way its a pure 50/50 shot).... OH NO... I see where I am going wrong.... The second must be able to discern that for the first guy to guess wrong he must have seen the same number of each color hat, so he can assume if he can see 3 Red and 2 White that he must be a 3rd white, because if he were Red the first guy would have seen 4 Red and 2 White and would have known his color was White.

Oh well.... it was a somewhat exhilarating thought experiment anyways......

[END EDIT]

In knowing there are the same amount of each hat it is easy to solve this puzzle; I prefer the answer above about using different tones.

its a shame the original post did not include the fact that there are an even amount of criminals because that is how the riddle goes and it explains the "7 criminals" dilemma.
"And so these men of Indostan
Disputed loud and long,
Each in his own opinion
Exceeding stiff and strong,
Though each was partly in the right,
And all were in the wrong."

IBelieve
New Member
Posts: 8
Joined: Wed May 01, 2013 11:08 am

Re: A gruesome puzzle

Postby IBelieve » Mon May 06, 2013 7:10 pm

Another solution:
The person at the back of the line, who must guess first and who can see all the other hats, encodes the order of red/white hats as a boolean number with the least significant bit at the next person to speak [or the last person to speak, as agreed upon] and red representing a one bit and white as a zero bit [or vice versa, as agreed upon]. He simply says this number out loud. To satisfy the possibility that no one will get shot, one [or two if optimizing] encoding[s] are mapped to the word red and/or white. So, for example, if he sees all white hats in front of him it is understood that he will utter white.

User avatar
Scott Mayers
Veteran Poster
Posts: 2331
Joined: Sun Dec 30, 2012 4:56 pm
Custom Title: Deep

Re: A gruesome puzzle

Postby Scott Mayers » Tue Feb 04, 2014 9:50 am

deformation gradient wrote:I heard this puzzle at a dinner at Caltech, so I can't take credit for it. But I like it.

A group of (highly intelligent) criminals are about to be executed by a sadistic executioner. The executioner tells the criminals that he is going to line them up front-to-back (as opposed to standing side by side), so each can see the people in front of them, but not those behind them. Furthermore, he will turn off the lights, and RANDOMLY place either a red or white hat on each person's head. Then, he'll turn the lights back on. He will ask each person, starting from the BACK of the line, whether they are wearing a red or white hat. If the person answers incorrectly or says anything other than RED or WHITE, that person will be shot. Each person cannot see their own hats, only those of the people in front of them. They can hear, however, what the people behind them say, and whether or not each person gets shot. If anybody speaks out of turn, or makes any movement out of the line, etc... they will also be shot. Anybody who doesn't get shot will be granted amnesty.

After telling them all this, the executioner then leaves the criminals alone in a room for a few minutes. By the time he returns, they have divised a strategy that will ensure that AT MOST one person will get shot, and maybe none at all. What is their strategy?


Initial response without cheating:
If this is literal, then demanding that the last person in line stays silent and that no one should move should assure that no one gets shot as long as they don't have to wait an eternity before being granted amnesty!
Otherwise, this requires defining, "etc." and is missing a limit to the when this amnesty can be granted. If the lack of an answer is not included in 'etc', this cannot be determined.
I eat without fear of certain Death from The Tree of Knowledge because with wisdom, we may one day break free from its mortal curse.

User avatar
Scott Mayers
Veteran Poster
Posts: 2331
Joined: Sun Dec 30, 2012 4:56 pm
Custom Title: Deep

Re: A gruesome puzzle

Postby Scott Mayers » Tue Feb 04, 2014 10:22 am

If "etc." doesn't limit the way one speaks, then agree to a simple convention like say what the person in front is wearing like:

The first person guesses by stating what the person in front of them is wearing.
This person risks getting shot by the guess but communicates to the person in front of them what they are actually wearing.
That person says the color they have but speaks it differently according to the person in front of them.
For example, they can agree to answer as a declarative statement if the color of the person in front of them is the same as theirs or answer with a question to hint to the person ahead of them to answer opposite to what the person said behind them.
I eat without fear of certain Death from The Tree of Knowledge because with wisdom, we may one day break free from its mortal curse.

User avatar
Scott Mayers
Veteran Poster
Posts: 2331
Joined: Sun Dec 30, 2012 4:56 pm
Custom Title: Deep

Re: A gruesome puzzle

Postby Scott Mayers » Tue Feb 04, 2014 10:31 am

Post answer: Cool, I figured it out but I'd still use my first guess over the second one if we are to base it literally on the question as presented here because it assures that no will get shot. But if not saying anything gets the first person shot for not interpreting it properly, the second guess should also be included as a backup. At worst two people would get shot but then this is the fault of the cruelty of executioner to not be precise. And if he was to choose that behavior, your ability to even trust that he'd honor his words regarding amnesty is just as much a gamble.
I eat without fear of certain Death from The Tree of Knowledge because with wisdom, we may one day break free from its mortal curse.


Return to “Brainteasers”

Who is online

Users browsing this forum: No registered users and 1 guest