1. 2.14 Three players enter a room and are given a red or a blue hat to wear. The color of each hat is determined by a fair coin-toss. Players cannot see the color of their own hats, but do see the color of the other two players’ hats. The game is won when at least oneoftheplayerscorrectlyguessesthecolorofhisownhatandnoplayergives an incorrect answer. In addition to having the opportunity to guess a color, players may also pass. Communication of any kind between players is not permissible after they have been given hats; however, they may agree on a group strategy beforehand. Verify that there is a group strategy that results in a 3 4

probability of winning. (This puzzle was discussed in the New York Times of April 10, 2001. The hat problemwithmanyplayersisrelatedtoproblemsincodingtheory.Thestrategy gets far more complicated for larger numbers of players. In the game with 2m − 1 players, there is a strategy for which the group is victorious with a probability of

(2m −1)/2m).