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

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