# More Monster and Hats

Our challenge this week was suggested by Chris Roat, who calls it “one of my favorite puzzles of the year.” And Dr. Roat sees a lot of puzzles — he’s an active participant in Bay Area puzzle competitions and a longtime Google employee currently up to something top-secret at Google X. His suggestion for this week is a continuation of our recent Andrew Luck Monster Problem. Put on your headgear and get ready for —

More Monster and Hats

Two people find themselves stuck on a remote island. One day, a terrible monster appears. The monster says that he intends to eat the pair, but will give them the following chance to survive: Later that day, the monster will line them up face-to-face. The monster will then place either a black or white hat on each person’s head. Each person can see the hat on his or her counterpart, but cannot see his or her own hat.

The monster will then ask both people at once to simultaneously guess the color of his or her own hat. The person can say only one word — either “white” or “black.” If both people are wrong, the monster will devour them on the spot; Otherwise they can go free.

The two people have all afternoon to plan their strategy. The question is — what should they do?

That’s it for the puzzle this week. If you’re looking for Gary Hewitt’s Enhancer to optimize your Numberplay experience, please be patient — Mr. Hewitt is revamping the tool to support The Times’s new blog format. Finally, do send your favorite hat-and-monster puzzle to gary.antonick@NYTimes.com.

Solution

Here’s Chris Roat:

As some discovered, the game is 100% solvable – no randomization/guessing is needed to increase the odds of winning. It’s true even for the n colors, n people generalization. And as Daniel Finkel alludes to in the 2-hat case, the rock-solid strategy will lead to exactly one person guessing correctly.

In the two-hat case, it’s easiest to explain to people that either the hats are the “same” or “different.” I find that is the paradigm shift people will have trouble with. Then the solution is deciding which of the two players will guess “same” and which will guess “different,” based on what they see.

The astonishing solution, then, is to have one person always call out whatever color hat they see on the other person’s head, and that other person call out the opposite color of what they see. This will, incredibly, always allow one person to guess his or her own hat color correctly, and thereby saving both from being devoured by the terrible monster.

An introduction to Smart Contacts, a recently announced Google X project:
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}