Challenge question (star it!) - logic saves lives?

Question

A king has some (finite) number of subjects. One day he lines them all up in a row, facing towards the front of the row. He goes from the front of the row to the back, giving each subject a hat - either red or blue.

No subject can see his/her own hat, nor can any subject see behind himself/herself. But a subject can see ALL of the others that come before him/her in line.

So the king has made his way to the back of the line, and now he will ask the person at the back of the line "What color is your hat?" while brandishing a big sword. If answered correctly, the person is freed. If answered incorrectly, the person is beheaded immediately. No communication between subjects is allowed, although they can hear each others' guesses.

You have a chance to meet with the subjects ahead of time - the night before this incident - to give them a strategy that will save the most number of lives (guaranteed, not a probability or expected outcome). The strategy that saves the most will be chosen.

50% is well below the maximum you can guarantee to save (and 75% is below the maximum expected value too). The proof that 50% is best relies on the false assumption that one person can only provide enough information to save one other person.

AlexAlex, I resent the implication. I am a professional combinatorist. I know the correct answer, and the full solution. I'm not cheating to get answers to a "test" of any sort.

Users post questions to challenge and even stump others frequently in this forum. There is no reason for you to put my question to such scrutiny, scrutiny that is completely unnecessary and quite insulting.

And I've already explained the error in the proof of the 50% guaranteed solution, no need for you to continue to give hints for my challenge question, which is quite clearly meant for people to try to work out on their own, without prior knowledge of the solution or hints from people who have prior knowledge.

I'm not entertaining answers that aren't mathematical either - the subjects are not permitted to cheat, nor are they permitted to communicate AT ALL. Their guesses cannot me modulated (be it varied pitch or speed) to communicate, as this would violate my the stipulation that they not communicate.

Answer 1

It is simple to save 3/4
First person says the color of the person in front of him. That person guesses that way and lives. Next person says color of person in front of him and so on. This saves 1/2 for sure, (better than everyone simply guessing) and maybe more (in cases the person ahead of him has same color hat. So with 50/50 distribution of hats this saves 3/4 of the subjects.

Saved: 1/2 guaranteed and 3/4 expected.

Proof that this is best: Each person can either guess to survive and use information provided to him by the person behind him or help others. As we have no information on the distribution of hats each guess is a true 50/50. As each person cannot provide information to others with a true guess, the best he can do is tell the person in front of him the color of his hat. He cannot give more information than that. Thus we can guaranteee that every other person will live and offer the rest 50/50.

I tried to see if hearing the previous person's beheading would give information to people farther up the line, but couldn't think up a scheme.

The only other way to get a better survival rate is if there is an obvious pattern to the hat colors and people abandon this plan for simply interpreting the pattern.

Funny answer: Beheading is very bloody,(especially with a sword) so if the person behind you covered you with all his blood, maybe picking red would work!

Continued: Ok, the first person yells out the number of red hats really loud and then gets killed for his insolence. Then everyone else can just count the number of red hats remaining and choose accordingly. Saves all but the first chum.

Answer 2

This logic question is called the "The Volokh Conspiracy"
from September 2005. See the link.

As a side point: "If answered correctly, the person is freed."
Once a person is freed he is no longer a subject of the King.
Therefore the stipulation "No communication between subjects is allowed" goes out the window.

The first freed subject can tell all that are alive what color hat is on their heads - thus ruining the game (and this logic puzzle) for the King.

Answer 3

Not sure if this is what you have in mind, but I think you can save everyone but the last person in line and he has a 50/50 chance. Admittedly my answer may be like cheating but here it is anyway (let's assume the king gives his hats out randomly):

Suppose we number the person from the back of the line "1", the next person 2, and so on. Then 1 looks at the color of the hat that 2 has and when asks says that his hat is that color. Whether or not 1 is right is a 50/50 proposition. When the king gets to 2 and asks the question, 2 will know what his hat color is (say its red). When he looks at 3's hat and sees that it is red he will answer "red". But if 3's hat color is blue 2 will answer "my hat is not blue." Based on this code, 3 will know whether his hat is red or blue. When the king comes to him, he will answer the same way depending on what 4's hat color is. continue this until the last person in line answers. Here is an example for n = 10 people. In this case everyone is saved.

Person.....Hat Color ... answer
1..................R .............. Red
2..................R............... Not Blue
3..................B............... Not Red
4..................R................ Red
5..................R................ Not Blue
6..................B................ Blue
7..................B................ Blue
8..................B............... Blue
9..................B............... Not Red
10................R............... Red

You dismiss other answers that are similar to this saying that the subjects cannot communicate among themselves, but you say in your statement of the problem that "they can hear each other's guesses". So what I am suggesting or answers that suggest using voice modulations are acceptable according to your own stipulations.

Answer 4

first subject says the color of the hat of the person before him, say red.

when second subject hears this, he looks at the person before him (3rd subject), and if the 3rd subject wears also red, he calls out red in a quick and high pitched manner. If instead the 3rd subject has blue, the 2nd subject calls it in a slow and low pitched way.

then if the third subject wears a blue hat, he will know because the second subject called out red in a slow and low pitched way. Now its his turn (3rd subject) to call out blue, and whether he calls it out in a quick high pitched or slow low pitched manner depends on whether the 4th subjects hat is the same color as his or not.

This way, either the chance of everyone surviving is 100% or 99.99%!!!!! LOL. Provided the group of men don't get too nervous and spoil this Genius PLAN. nyahahaha!

Answer 5

I would tell them to choose red because the color red makes you anxious and makes you want to get up and go.