Hat puzzle  

From The Art and Popular Culture Encyclopedia

Related e

Wikipedia Wiktionary Shop Featured: Rhombicuboctahedron by Leonardo da Vinci

Hat puzzles are logic problems that date back to 1961 if not earlier.

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

A competitive version

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. The first to guess the colour of his or her hat correctly wins.

All three players get red hats, so all three 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?

If player 1 sees a blue hat on player 2, then player 1 knows his or her own hat must be red. Otherwise 1 and 2 would have blue hats, and 3's hand would not be raised. Thus any player who sees a blue hat can guess at once. The winner realizes that since no one guesses, there must be no blue hats, so every hat must be red.

A cooperative version

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:

• Count the numbers b of black hats and w of white hats that you see.
• Wait min(b,w) seconds.
• If nobody has yet spoken, guess that your hat is black if you can see fewer black hats than white hats, or white if you can see fewer white hats than black hats.
• If you have not yet spoken, guess that your hat is of the opposite colour to that of one of the first people to speak.

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.

If B < W then those wearing a black hat will see B−1 black hats and W white hats, whilst those wearing a white hat will see B black hats and W−1 white hats. Since B−1 < B ≤ W−1, those players wearing a black hat will be the first to speak, guessing correctly that their hat is black. The other players then guess correctly that their hat is white.

The case where W < B is similar.

Ebert's version and Hamming codes

Ebert's version of the problem states that all players who guess must guess at the same predetermined time, but that not all players are required to guess. Now not all players can guess correctly, so the players win if at least one player guesses and all of those who guess do so correctly. How can the players maximise their chance of winning?

One strategy for solving this version of the hat problem employs Hamming codes, which are commonly used to detect and correct errors in data transmission. The probability for winning will be much higher than 50%, depending on the number of players in the puzzle configuration: for example, a winning probability of 87.5% for 7 players.

Similar strategies can be applied to team sizes of N = 2^k−1 and achieve a win rate (2^k-1)/2^k. Thus the Hamming code strategy yields greater win rates for larger values of N.

In this version of the problem, any individual guess has a 50% chance of being right. However, the Hamming code approach works by concentrating wrong guesses together onto certain distributions of hats. For some cases, all the players will guess incorrectly; whereas for the other cases, only one player will guess, but correctly. While half of all guesses are still incorrect, this results in the players winning more than 50% of the time.

A simple example of this type of solution with three players is instructive. With three players, there are eight possibilities; in two of them all players have the same colour hat, and in the other six, two players have one colour and the other player has the other colour.

The players can guarantee that they win in the latter cases (75% of the time) with the following strategy:

1. Any player who observes two hats of two different colours remains silent.
2. Any player who observes two hats of the same colour guesses the opposite colour.

In the two cases when all three players have the same hat colour, they will all guess incorrectly. But in the other six cases, only one player will guess, and correctly, that his hat is the opposite of his fellow players'.