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

About these ads

Responses

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

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

  2. [...] hat problems (solutions) Yesterday I stated four hat problems. Today’s post contains the solutions to those problems. 1. Alice and Bob are wearing hats. [...]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

Follow

Get every new post delivered to your Inbox.

Join 206 other followers

%d bloggers like this: