Abstract :
Colored hats and Hamming codes
------------------------------
Imagine that you and two of your friends are the contestants at a
TV game show. First, the host flips a coin behind each person's back, and
depending on the outcome puts either a red or a blue hat on that person's
head. Each of you can see the hats of the other two people, but you have
no idea what color your own hat is.
Now, on the count of three, each of you has to guess the color of your own
hat -- or else "pass" by saying nothing. If at least one of you guesses
correctly and no one guesses incorrectly, the three of you get to split a
$999,999 prize. But if someone makes a mistake or if everyone passes, you
all go home empty handed.
Of course, you spend the week before the show trying to think
of a strategy for this game. Clearly, there are no fail-safe
strategies: every guess has an equal chance of being right and being
wrong. However, you can still look for a strategy that will maximize
the _probability_ of your winning the money. What strategy should you
adopt? (Hint: you can do much better than probability 1/2.)
This problem gets even more interesting when you have more than
three people (try it with seven), and leads to some surpirsingly beautiful
and useful(!) mathematics. It turns out to be connected both to other
games (Nim) and to the way digital information storage works. In my
lecture, I'll tell you how to approach the general "hat problem" (although you
should be able to figure out the three-person case on your own) and talk
about some of these connections. We might even get to some currently
unsolved hat-related problems, if there's time.