A gruesome puzzle

 New Member
 Posts: 16
 Joined: Tue Apr 11, 2006 7:30 pm
A gruesome puzzle
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 fronttoback (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?
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 fronttoback (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?

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

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

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

 New Member
 Posts: 11
 Joined: Fri Apr 24, 2009 1:43 pm
Re: A gruesome puzzle
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.

 Posts: 2
 Joined: Wed Jul 08, 2009 12:37 am
Re: A gruesome puzzle
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.
[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.

 Perpetual Poster
 Posts: 4088
 Joined: Thu Feb 16, 2006 7:04 pm
 Custom Title: Skeptical Berserker
 Location: Miðgarðr
Re: A gruesome puzzle
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."
BigTim
"I'm not entirely convinced that ValHalla isn't real."

 New Member
 Posts: 22
 Joined: Mon Apr 04, 2011 3:03 am
Re: A gruesome puzzle
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.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.
"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."
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."

 New Member
 Posts: 8
 Joined: Wed May 01, 2013 11:08 am
Re: A gruesome puzzle
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 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.
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 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.

 Veteran Poster
 Posts: 2448
 Joined: Sun Dec 30, 2012 4:56 pm
 Custom Title: Deep
Re: A gruesome puzzle
Initial response without cheating: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 fronttoback (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?
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.

 Veteran Poster
 Posts: 2448
 Joined: Sun Dec 30, 2012 4:56 pm
 Custom Title: Deep
Re: A gruesome puzzle
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.
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.

 Veteran Poster
 Posts: 2448
 Joined: Sun Dec 30, 2012 4:56 pm
 Custom Title: Deep
Re: A gruesome puzzle
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.