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

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