Posted by: Dave Richeson | August 10, 2009

Infinite hat problems

I got back from MathFest yesterday after a long 3-leg red-eye trip across the country. It was a great meeting. It is always fun to hear some good talks, visit a new city, and see old friends (and meet another math blogger).

The first talk that I attended was given by Alan Taylor: “Predicting Values of Arbitrary Functions.” In it he mentioned some hat problems that I thought I’d repeat here. I’ll post solutions tomorrow. [Update: the solutions are now posted.]

1. Alice and Bob are wearing hats. The hats are either red or blue. They can see each other’s hats, but not their own hat. They are tasked with guessing their own hat color. If either person gets the color right, then they both receive \$100. They cannot communicate with each other in any way after the hats have been placed on their heads and they must both say their guess at exactly the same time. However, they can meet in advance to decide on a strategy. Find a strategy that guarantees a payoff.

2. Suppose there are infinitely many people in the room wearing red or blue hats and each person can see everyone else’s hat except his or her own. Is there a collective strategy that guarantees infinitely many correct guesses?

3. Suppose there are a countably infinite number of people standing on a number line with one person at each positive integer. Each person can only see the hats of the people in front of him or her (they’re all looking toward positive infinity). Find a strategy that guarantees infinitely many correct guesses.

4. Again, like (2) assume that there are infinitely many people and each person can see everyone else’s hat. Show that there is a strategy in which only finitely many people guess wrong. That’s not a typo—all but finitely many guesses must be correct. This one is hard.

For more information about infinite hat problems and the crazy things that can happen see Christopher Hardin and Alan Taylor’s article ”An introduction to infinite hat problems” (The Mathematical Intelligencer, Vol. 30, No. 4. (1 September 2008), pp. 20-25).