Posted by: Dave Richeson | August 11, 2009

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

Solution. Alice says the color that she sees on Bob, Bob says the color that he does not see on Alice.  This will always produce one correct guess. Why? Alice is guessing that both hat colors are the same and Bob is guessing that both hat colors are different. Clearly one of them will be right.

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?

Solution. Pair everyone up and use the technique above. One out of every two people will guess correctly.

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.

Solution. An individual guesses red if he or she sees infinitely many red hats, and guesses blue otherwise. If there are infinitely many people wearing red hats then all of these individuals will guess correctly. If there are finitely many red hats, then only that finite number of people will guess incorrectly.

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.

Solution. This crazy strategy requires the axiom of choice. I am not going to say too much about what the axiom of choice is, but it is an innocuous-looking axiom in set theory that has many bizarre consequences. Roughly speaking the axiom of choice says that if you have a collection of sets, then it is always possible to pull out one representative from each set. In our case we’re going to look at sets in which the elements are hat colorings, where a hat coloring is a specific choice of hat colors for all the people. A good way to think of a hat coloring is an aerial snapshot of the crowd of people all wearing their hats. Create sets of hat colorings as follows: two hat colorings are in the same set if and only if all but finitely many of the hats are the same color in the two colorings. Think of the sets as boxes of photos with the property that if we took two of snapshots out of the same box and compared them, only finitely many of the people would have different colors in the two photos. And if we compared two photos from two different boxes, there would be infinitely many differences. By the axiom of choice we can choose one representative from each set (think of taking a photo out of each box and taping it to the top).

Now here’s the strategy. A person in the crowd looks around and examines every hat color that is present. The individual doesn’t know his or her own hat color, but knows enough information to know which box this particular coloring corresponds to. He or she looks at the photo taped onto the top of the box and sees his or her hat color in that photo. He or she calls out that color. If every person obeys this strategy, then by construction, only finitely many of them are going to be wrong.

According to Hardin and Taylor, this proof was discovered by two graduate students at Cornell, Yuval Gabay and Michael O’Connor, in 2004.

About these ads

Responses

  1. Not sure if you know the joke that goes along with these puzzles… I tried but couldn’t track down a good reference for the joke (maybe you mentioned it somewhere that I didn’t notice). Here’s my best recollection of it.

    The hat problems are extensions of the “king’s advisor” riddle, and some people end this riddle with a joke. In this version, a king asks three sages, Alice, Bob and Carol to solve the hat riddle in an attempt to find the wisest sage in the land, who will then become his advisor.

    Alice solves the riddle and is made the advisor. Later, in a time of great crisis, the King summons his new advisor and asks her whether or not to invade a neighboring state. Alice answers “this is a good question, but what does it have to do with hats?”

    • That’s great! I haven’t heard that one. I’ll have to keep my eyes open for a reference. Thanks.

  2. [...] 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.] [...]

  3. As a computer engineering graduate and someone who does not know axiom of choice,equivalence relation,equivalence class,I would say that yours is the best explanation I have found so far to problem no. 4.Thanks a lotttt :D

  4. Here is how I heard that joke:

    A king wants to get an adviser to tell him how to best govern the country, and he hears about the famous hat riddle above, and he holds a contest, and no one can solve the riddle, until finally one man DOES solve it and the king declares him the winner, and says, “From now on, I will not make any decisions without asking you, O wisest of men”.

    The next day, a neighboring hostile country sends troops to the border of the king’s country, and he summons his new adviser and says, “Should we attack the troops they sent or wait to see what they do next?”.

    The adviser says, “That depends. First tell me how many of their soldiers are wearing red 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 179 other followers

%d bloggers like this: