The Three Hat Problem

jeffsenter writes: "The NYTimes has a nice article on the three hat problem, which has recently become quite popular among mathematicians. Three people are given either a red or a blue hat to wear. The goal is to have someone guess the correct color of his/her own hat with no person guessing incorrectly." Read the article for the rules of the puzzle. This problem is quite comparable to the Monty Hall problem, where people initially think that they can't do better than chance, but then realize that there is an extra source of information which can be tapped - either the host's knowledge of which door has the prize, or in this case, the fact that which player makes a guess can be determined after the game has started, that is, based on information available about the hats. Think about it - it's an interesting puzzle.

Comments

Some clarifications to the puzzle:

[DG]

It seems some people aren't reading the article very well (on Slashdot? Horrors!)

Here's some key points:

1) All guesses must be correct. If any of the 3 players guess and get it wrong, everybody loses.

2) Guesses are simultanious, not sequential - ie, you write down your guess, and all 3 guesses are passed to the host, who then reads them

3) There are 3 hats, but two colours. This means that out of 12 possible combinations, there are 2 that are "all hats same colour" - so 1/6th of the time. Thus, if you see 2 hats of the same colour, the probability that your hat is the same color is 1/6 - which in turn implies that guessing that your hat is a different colour will be correct 5/6th of the time.

Thus, if you see any two differently-coloured hats, you pass. If you see all hats the same colour, then invert the color you see and guess that. This starts at 5/6ths correct with 3 hats, and gets better for larger numbers of hats not a power of 2.

It's a Dr Seuss April Fools joke

[KlomDark]

Haha, funny to see how people are taking this problem entirely too seriously, and forgetting their childhoods at the same time.

This is all taken from the Dr Seuss' book "One Fish. Two Fish. Red Fish. Blue Fish", just changed to be One Hat Two Hat Red Hat Blue Hat.

Truely LMAO!

Research?

[sandler]

The problem has even spread to the Caribbean. At a workshop at a research institute in Barbados, one hardy group of theoretical computer scientists stayed up late one rum- soaked night, playing a drinking game based on the puzzle.

Sounds fun! How can I get a job at said "research" institute??

How to cheat

[Syberghost]

If you're ever kidnapped by aliens and forced to play this game in return for your life, figure out what the names of the two colors are, and assign "down" to the one that comes first alphabetically, such as "blue" in the standard example, and "up" to the other, "red" in the standard example.

Then when it's time to look at your fellow players, pick the one farthest to your right and look at his chest for down, or his hat for up. Point your whole face.

Then glance with your eyes at the others. If even one of them has read this post, you're in good shape. If they both have, you're free.

Unless the aliens are just shitting you, and intend to implant an 80-foot satellite dish in your ass regardless of the outcome.


-

Solution for the general case using Hamming codes

[e271828]

Nobody seems to have posted this yet, and since I've wasted a few hours on this already, I figured I should share. Here's the solution for the general case where the number of players is n=2^k-1; it involves Hamming codes.

The general case is perhaps best illustrated by example for the case of 7 players. Here's how it goes:

First, number the players 1 through 7. Now think of a player with a red hat as being assigned a binary zero, and a player with a blue hat as being assigned a binary 1. Then an assignment of hats to the players can be associated with a length 7 binary sequence: As an example, if all the players have red hats, this correspond to the sequence 0000000 (seven zeros), and if all but the last player have red hats, we get the sequence 0000001. We'll call length 7 binary sequences words; every hat assignment has an associated word, and vice versa. For future reference, denote the two words in the example above as c0 and c1 respectively.

A brief digression on Hamming codes: A length 7 Hamming code is a certain (carefully chosen) subset of the 2^7=128 possible words. This subset consists of 16 words, called codewords. We need just one fact about Hamming codes to describe the players' strategy: [Fact 1] If any one bit in a codeword is flipped, the resulting word is not a codeword. For example: c0, the all zero word, is always a codeword in a Hamming code; c1, which differs from c0 in just one bit, cannot be a codeword.

Suppose I am one of the players. Here's my strategy:

By observing the hats of the other 6 players, I construct two words. The first, w0, is the word that would be associated with our hat assignments if my hat is red. The second, w1, is the word that would be associated with our hat assignments if my hat is blue. We have 3 possible cases:

1. Neither w0 nor w1 is a codeword
2. w0 is a codeword
3. w1 is a codeword

Cases 2 and 3 are mutually exclusive because of Fact 1. My strategy?

In case 1, I say nothing, in case 2, I declare my hat to be blue, and in case 3, I declare my hat to be red.

That's it. This strategy will result in the team winning every time the word associated with the hat assignment is not a codeword, which happens (128-16)/128=7/8 of the time.

So, why does this work? To understand, we need one more property of Hamming codes: [Fact 2] For every word that is not a codeword, there is a unique bit, which if flipped, will produce a codeword. For instance, if the last bit in c1 is flipped, we get c0, the all zero codeword. Now suppose that the hat assignment is associated with a word that's not a codeword (which, as shown above, happens 7/8 of the time). To be specific, suppose the assignment corresponds to c1. Here, the 7th bit is the unique bit that can be flipped to get a codeword. Then, by Fact 2, players 1 through 6, after constructing their w0 and w1 words, will find themselves in Case 1 : neither word is a codeword. They'll keep quiet, while the 7th player will declare his hat to be blue (Case 2). Success!

Of course, if the hat assignment corresponds to a codeword, then every player will speak up, and they'll all guess wrong! Example again: if every player is assigned a red hat (corresponding to c0), they'll all say they have blue hats.

It's not hard to see how this generalizes for an arbitrary number of players n, where n=2^k-1. The players will succeed if and only if the associated word is not a codeword. A Hamming code of length n=2^k-1 has 2^(n-k) codewords, so success is achieved 1-2^-k of the time, which tends to 1 as k tends to infinity.

There, I knew those grad courses in coding theory would come in useful sometime!

Unattributed puzzle taken from 1993 ACM paper

[frankie]

This puzzle comes from a paper by James Aspnes, Richard Beigel, Merrick Furst, and Steven Rudich. Attribution: I got this information from my friends on Mattababy.

Date: Tue, 10 Apr 2001 10:58:43 -0400
From: Steven Rudich
Subject: New Yorkl Times fails to credit me.

Today, the New York Times had a lively article on a brilliant puzzle going around mathematical circles.

Just before doing my post-doc, Richard Beigel and I formulated formulated our voting puzzles. Subsequently, our puzzles were developed into a now classic paper in theoretical computer science (with M. Furst and J. Aspnes). There paper can be found at www.rudich.net/papers/voting.ps . My initial solution to the first voting puzzle was a coding theory solution that is strictly identical to the much touted solution in the NYT article. When giving talks on the subject, I mentioned that if my voters had the ability to abstain, that my coding solution was still optimal and that the voters would make no errors in a most situations. This is strictly identical to the hat puzzle in the NYT article. My talks were very popular and many of the people in the article attended these talks. Subsequently, Burt Enderton gave a simple solution to my puzzle that did not have the abstention interpretation and hence is not a solution to the hat puzzle. I liked Burt's solution and put it in our paper.

In the last few months I have reminded people that *all* the proofs and connections to coding theory were developed by me. Nonetheless, these same people ignored me in the Times article.

I have had many ideas stolen, but never featured in vivid detail in the Times.

Steven

The Red Hat problem

[SpanishInquisition]

Why does their x.0 releases always suck?
--

Re:Math + Usefullness

[JWhitlock]

It's true, not everyone needs math. In fact, if most people don't learn math, then folks like me get paid more for our math knowledge.

I used math over the last seven days to:

Guestimate how long it will take me to do a task, based on past performance and how much was budgeted.

Made an estimate of what sprinkler I needed for my lawn and type of grass, taking into account water coverage and projected rainfall.

Determined what operations to make to get a bit structure in the format I desired, over a system with endian differences (using Fortran - yuck!)

For fun, calculated how many managers it would take to run a company, based on each manager having a maximum of 4 people under them (still working on those formulas - I leave it as an excerise for the reader to determine why I decided on 4, or you could go join the Discordians and find out for yourself).

Calculated my wife's reading rate, to determine when she would be done with the Harry Potter book

Cut down a recipe for 10 to a recipe for 2 1/2.

Determined whether it would be a better idea to make an extra car payment, house payment, get a CD, or invest in a mutual fund

Tried to figure out your age, based on how little math you have had (19? 20?)

It's been a slow math week, too. In my job (systems programmer), I've used logic, binary arithmetic, calculus, trig, geometry, statistics, and other flavors of math.

Understanding the materials is a long way from realizing practical applications. Even these folks who do math for a living don't comprehend possible applications yet, but it's been a safe bet that today's math theory is tommorrow's application.

Hmmmm

[BillyGoatThree]

"Three-fourths of the time, two of the players will have hats of the same color and the third player's hat will be the opposite color. The group can win every time this happens by using the following strategy: Once the game starts, each player looks at the other two players' hats. If the two hats are different colors, he passes. If they are the same color, the player guesses his own hat is the opposite color."

I was going to post a solution like this (before reading the rest of the article, duh) but then I thought it didn't work. That's because I was taking a single point of view (which is Timothy's point). I should have gone ahead and done it....

There are 8 possible universes. The algorithm works as follows:

RRR = every player sees two reds, every player says "blue" - LOSS
BBB = every player sees two blues, every player says "red" - LOSS
RRB = the reds see conflict and pass, the blue sees two reds and guesses "blue" - WIN
RBR = the reds see conflict and pass, the blue sees two reds and guesses "blue" - WIN
BRR = the reds see conflict and pass, the blue sees two reds and guesses "blue" - WIN
RBB = the blues see conflict and pass, the red sees two blues and guesses "red" - WIN
BBR = the blues see conflict and pass, the red sees two blues and guesses "red" - WIN
BRB = the blues see conflict and pass, the red sees two blues and guesses "red" - WIN

That's 6 wins in 8 plays or 3 wins in 4 plays. I'm not going to try to extend this to further cases.
--