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).

3 Comments

1. Theo says:

My favorite hat problem is an oldie but a goodie. Alice, Bob, and Claire are playing a game similar to the one in #1: each has either a red or blue hat on, no one can see their own hat color, they may not communicate once they are wearing hats, they must guess at the same time. The rules: each player is allowed to Guess the color of their own hat or to Pass. All three players win if at least one player guesses correctly AND nobody guesses wrong. The challenge: optimize their chances of winning.

In any case, these infinitary ones are really fun, and connect with all sorts of deep stuff.

1. That is a good one. In fact, if you click on the link to the paper above, you’ll see that they begin the article with that example.

Comments are closed.