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.