puzzle

[desh]

LOGIC PUZZLE TIME!

This is one of my favorite puzzles, both because the answer isn't easy, and because the setup is very similar to another problem a lot of people know.

You and two other prisoners are set to be executed. You're given one chance to get out, by some sadistic game invented by your captors. (Isn't that how it always is?)

You're each privately given a hat, which is either red or blue (randomly chosen, independent of the hats chosen for the other people). You can't see your own hat. Once you're all wearing the hats, you're ushered into a common room where you can see the other two people and their hats. Without being allowed to communicate, you're then sent back to your solitary confinement and your hats are removed.

Each of you is then given a piece of paper to write down your hat color. You may either write "red", write "blue", or leave the paper blank. If any of you guess wrong, or if you all leave your papers blank, then you're all executed. But if even one of you guesses right, without any wrong guesses, you're all set free.

If you are allowed to discuss strategy among the three of you before the hats are handed out, but you're allowed no communication during or afterwards, what is the optimal strategy? In other words, what should you do such that you all have the best chance of survival? (The answer is "legit", assuming no wording loopholes, no color-blindness, no sympathetic guards, and nothing else like that.)

(Comments to this post are screened, but only correct answers and really good guesses will remain screened. I'll unscreen questions, comments, wrong answers...almost everything except correct answers. Eventually, I'll unscreen everything.) EDIT: Comments now contain spoilers.

Comments

[(Anonymous)]

If any of you guess wrong, or if you all leave your papers blank, then you're all executed. But if even one of you guesses right, without any wrong guesses, you're all set free.

You mean if any guesses wrong you all die, but if every one of you guesses right you're all set free?

[desh]

Nope. One correct guess among the three of you is enough, as long as there are no incorrect guesses.

[sleepsong.livejournal.com]

If any of you guess wrong, or if you all leave your papers blank, then you're all executed. But if even one of you guesses right, without any wrong guesses, you're all set free.

Fallacy.

If any one of us guesses wrong, we're all killed, but if one of us guesses right, we all live? That makes no sense. If one of us guesses right, one of us guesses wrong, and one of us leaves our paper blank then we all die because of the one wrong guess, but we all live because of the one right guess.

Or does it mean that if one person gets it right and the other two don't answer then we all live?

[desh]

Yeah, your last sentence. Want it in perl psuedocode?

if (wrong_guesses > 0) { # blank answers don't count as wrong guesses
    die();
} else if (right_guesses > 0) {
    live();
} else { # if every paper is blank
    die();
}

[sleepsong.livejournal.com]

Remember, I know purl, not perl, but that makes sense now.

[intangiblehugs.livejournal.com]

no, you need to rearrange your if statements. according to what you wrote above, 1 or more wrong answers will lead to the die function and bypass the first else if that would redeem the three prisoners if someone got it right.

but really, it doesn't need to be that complicated at all. if one or more of the three gets it right, they live. wrong vs. blank is irrelevant.

if (right_guesses > 0) {
live();
}

[desh]

No, my code was right. I think you're reading the question wrong. Don't forget that "If any of you guess wrong ... then you're all executed."

[myq.livejournal.com]

Okay...at first I was convinced it was two people just don't guess and one randomly guesses and you coinflip.

But then I worked out all the possibilities...

Everybody tells each other that if you see two people with different color hats, leave your paper blank. However, if you see the two others with the same color, guess the opposite.

Is this right?

[desh]

Right! Good job.

[sleepsong.livejournal.com]

But what if they're all wearing red hats and they all guess blue?

You never said that all of the prisoners were not wearing the same coloured hats.

[desh]

In that case, they all die. The success rate of this solution is 75%, not 100%. But it's not possible to do better within the rules of the problem.

[vox-dei.livejournal.com]

Okay, I'm not sure here or anything but here's a guess. I think that the people should make the decision whether to leave the paper blank based on the color of the hats that they see when they're in the room. At least two of the people will have the same color hat, so a person that enters and sees the other two people wearing hats of the same color should write an answer. The reason that it should be the person that sees to hats of identical color is that it is guaranteed that at least one person will have an answer. If you were to assign the job to someone who saw hats of both colors and it turns out that all three wore the same color hat, then all papers would be left blank. Now, if you assign the job to a person that sees hats of the same color, then it could play out in two ways:

1) Two hats are the same and one is different. This means that only one person will fill out the paper.
2) Three hats are the same. This means that all of them will include an answer.

Now, the person that sees both hats of the same color can either decide that his hat is the same as theirs or is the other color. In the first scenario, the odds that he'll be right are 50/50, but in the second scenario it is clear that each person ought to say that his hat is the same color as the two that he sees. Because none of the people can determine which of the two scenarios is the case, it is to the person's advantage that sees two hats of the same color to guess that his hat is the same as theirs. I think.

[desh]

Your first two paragraphs are right, but your third isn't. Work out all the scenarios.

[lord-emo.livejournal.com]

Two leave it blank and the third writes either (50-50)?

[desh]

Yeah, that'll get you a 50% survival rate, but it's possible to do better.

[jdcohen.livejournal.com]

Dude. Come up with an unseen signal, such as "the other two stare at the person with the red hat". Then, only one person submits a guess, which is right by way of signalling.

--Jeff

[desh]

No, there's no communication allowed at all. If it helps, maybe the guards blindfold everyone, and then unblindfold and reblindfold you one at a time. Or something.

[jdcohen.livejournal.com]

Best strategy would seem to be one person chooses and the others submit blanks. That way, it's 50/50 without the other 2 sabotaging the first one. Anything else is impossible without any communication during or after seeing the "hats". Without additional input (or even knowing how many of each type of hat there are), this is the best strategy.

--Jeff

[desh]

Nope. That way will successfully get 50%, but it's possible to do better.

[nuqotw.livejournal.com]

Here's the best strategy I can come up with:

(1) If you see one red hat and one blue hat, leave your paper blank.

(2) If you see two red hats or two blue hats, write down the color you don't see.

Example:

(r) A sees r and b
(b) B sees r and r
(r) C sees b and r

B will write down blue, and A and C will leave blank sheets. They all walk.

(r) A sees r and r
(r) B sees r and r
(r) C sees r and r

A,B,C will all write down blue and be executed.

1/4 of the time, all the hats will be the same color. Then by (2) everyone will write down the wrong color and be executed.

3/4 of the time, there will be two hats of one color and one hat of the other color. By (1), the people with the same color hats will leave blank papers and by (2), the person with with the different color will answer correctly.

I believe that this strategy is optimal. Here's why.

Suppose that upon seeing two same-color hats, I write down the color I don't see with probability p and the color I do see with probability 1-p. Then

p*(3/4) + (1-p)*(1/4)

of the time, we are set free. However,

p*(3/4) + (1-p)*(1/4) = 1/4 + p*(1/2)

1/4 + p*(1/2) is largest when p = 1, i.e. the strategy initially described.

I have a modification. One person of the three can ask the executioner one question. It is known that the executioner either always tells the truth or always lies. What is the optimal strategy now?

[desh]

Correct! And as for your bonus question, something like "If I asked you if my hat is red, would you say 'yes'?" would work.

[sen-ichi-rei.livejournal.com]

are there a finite number of hats of each color?

and no allowed communication- does that mean that they're watching us for hand motions, etc.

if there can't be 3 hats of the same color then it would all be very easy, and the only person who should write down their color would be someone who sees the other 2 wearing the same color hats, thus they have the other color.

but i guess that doesn't work here. that would be too easy. but the way you word it, there isn't a set way to win, because really there is a chance that you all get the same color hat.

ok. 2*2*2=8. 8 combinations of hat

RRR
RRB
RBR
RBB
BRR
BRB
BBR
BBB

6 out of 8 of those combinations are 2 and 1. So therefore, I think the optimal solution is that you should only write your color if you see the other 2 wearing the same color. you have a 3/4 chance of winning.

i have no clue what to do in the other case, but you said optimal solution.

[desh]

Yeah, that's basically right. You left out a detail or two, but you're on the right track.

[sen-ichi-rei.livejournal.com]

gah! detail or 2? well obviously beforehand they tell eachother that they are only writing if they see 2 hats of the same color. and they daven beforehand, so they can get some divine intervention.

the only thing that would work for all 3 being the same would be some covert signal, like some way they could say if they were going to write. if they could do that, and see that all 3 of them were going to write, then they would realize they all had the same color. but that might be cheating.

[desh]

(The detail you left out in your original answer was which color you should guess. But you got the "when should I guess a color" part right, which is the hard part.)

[sen-ichi-rei.livejournal.com]

oh duh. opposite of what they see. i just thought that was obvious

Solution?

[dredpiraterober.livejournal.com]

Lets call them player 1,2,3
Beforehand they agree that P1 will guess p2's color, p2 guesses p3's color, and p3 guesses p1's color. Is that right?

Re: Solution?

[desh]

Nope. Since the distribution of hats is independent, they'd each have a 50/50 chance of being right, so the overall chance of none of them being wrong is only 12.5%.

Re: Solution?

[dredpiraterober.livejournal.com]

Whoops forgot that they are guessing their own hat color.

[conana.livejournal.com]

I get a .75 survival rate. Of the eight possible hat assignments, 2 feature 3 hats of the same color, while the other 6 feature an odd man out. In these six cases, the correct strategy is for the one prisoner who observes two identical hats to guess that ey wears a hat of the other color, while the prisoners who observe mismatched hats return blank slips. In the two homochromous cases, this results in three wrong guesses.

[desh]

Correct, and I like that word you invented!

[t3chnomag3.livejournal.com]

http://www.google.com/search?q=hat+color+puzzle

[desh]

Booo.

[t3chnomag3.livejournal.com]

Yeah, I know, I'm bad.

[kyra.livejournal.com]

Is the total quantity of each type of hat known?

[desh]

Nope, and each hat is chosen independently of the others. Those damn guards have a whole storehouse full of 'em.

[intangiblehugs.livejournal.com]

coordinate so that p1 impersonates p2 (write p2's name and hat color on eir paper), p2 for p3 and p3 for p1 and hope that the guards don't notice who actually wrote which one?

oh wait that would be fishy if they all got it right, so only one of them should actually write the right color.

[desh]

See my comment to you above. I think you're reading the question wrong. They have to avoid all wrong answers if they want to live.

[desh]

For those of you who are wondering how the solution can possibly be above 50%: You'll note that in the correct solution, over all 8 possible hat distributions, any given red/blue guess has a 50% chance of being right, just like in any other scenario. But in the winning scenario, if one person guesses wrong, so do the other two people. And if one person guesses right, the other two people return blank papers. This "clustering" of the bad guesses raises the overall success rate, due to the live/die rules of the problem.

The optimal solution is related to something called Hamming Codes. The general answer to the problem, when N is one less than a power of 2 (e.g. 3, 7, 15, 31, etc.) involves using "Hamming Codewords". See http://www.ee.unb.ca/tervo/ee4253/hamming.htm, the section entitled "sixteen valid codewords". The correct solution for 7 people involves assigning everyone a number 1-7, and having everyone memorize these 16 codewords (where 0 is red and 1 is blue). Then, if the hats the other 6 people are wearing correspond to one of the codewords (with only your hat as an unknown), you guess the hat color which would make the overall distribution a non-codeword. Because of the way the codewords are arranged, that means that about 94% of the time, one person will guess the right color and the group will win, and 6.25% of the time (when the distribution is exactly a codeword), everyone will guess wrong. Read the rest of that link to try to figure out why it works.

[sen-ichi-rei.livejournal.com]

WTF? I soooooooooo did not comprehend that 2nd paragraph with hamming codewords.

And haming codewords wouldn't be kosher anyways

*Ducks* [that was an A worthy pun, I probably shout be hit at some point]

[myq.livejournal.com]

everyone who replied to this post thinks about math way too much.

red red red
red red blue
red blue red
red blue blue

blue blue blue
blue blue red
blue red blue
blue red red

there!

and doesn't "blue" look funny after reading it a lot?