Hat puzzle

Hat puzzles are logic problems that date back to as early as 1961.

A number of players, at least three, are each wearing a hat, which may be of various specified colours. Players can see the colours of at least some other players' hats, but not that of their own. With highly restricted communication or none, some of the players must guess the colour of their hat. The problem is to find a strategy for the players to determine the colours of their hats based on the hats they see and what the other players do. In some versions, they compete to be the first to guess correctly; in others, they can work out a strategy beforehand to cooperate and maximize the probability of correct guesses.

One variation received some new publicity as a result of Todd Ebert's 1998 Ph.D. thesis at the University of California, Santa Barbara. It is a strategy question about a cooperative game, which has connections to algebraic coding theory.

Three players are told that each of them will receive either a red hat or a blue hat. They are to raise their hands if they see a red hat on another player as they stand in a circle facing each other. The first to guess the colour of his or her hat correctly wins.

All three players raise their hands. After the players have seen each other for a few minutes without guessing, one player announces "Red", and wins. How did the winner do it, and what is the color of everyone's hats?

First, if two people had blue hats, not everyone's hand would have been raised. Next, if player 1 had seen a blue hat on player 2 & a red hat on player 3, then player 1 would have known immediately that his own hat must be red. Thus any player who sees a blue hat can guess at once. Finally, the winner realizes that since no one guesses at once, there must be no blue hats, so every hat must be red.

In the case where every player has to make a guess, but they are free to choose when to guess, there is a cooperative strategy that allows every player to guess correctly unless all the hats are the same colour. Each player should act as follows:

Suppose that in total there are B black hats and W white hats. There are three cases.

If B = W then those players wearing black hats see B−1 black hats and B white hats, so wait B−1 seconds then correctly guess that they are wearing a black hat. Similarly, those players wearing a white hat will wait W−1 seconds before guessing correctly that they are wearing a white hat. So all players make a correct guess at the same time.

...
Wikipedia