Hat Puzzle
Encyclopedia
Hat puzzles are logic problems that date back to 1961 if not earlier.
A number of players, at least 3, 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
. It is a strategy question about a cooperative game
, which has connections to algebraic coding theory. By 2009, hat problems were "all the rage".
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.
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.
One strategy for solving this version of the hat problem employs Hamming code
s, 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 = 2k−1 and achieve a win rate (2k-1)/2k. 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:
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'.
A number of players, at least 3, 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.
Doctor of Philosophy
Doctor of Philosophy, abbreviated as Ph.D., PhD, D.Phil., or DPhil , in English-speaking countries, is a postgraduate academic degree awarded by universities...
thesis
Thesis
A dissertation or thesis is a document submitted in support of candidature for an academic degree or professional qualification presenting the author's research and findings...
at the University of California, Santa Barbara
University of California, Santa Barbara
The University of California, Santa Barbara, commonly known as UCSB or UC Santa Barbara, is a public research university and one of the 10 general campuses of the University of California system. The main campus is located on a site in Goleta, California, from Santa Barbara and northwest of Los...
. It is a strategy question about a cooperative game
Cooperative game
In game theory, a cooperative game is a game where groups of players may enforce cooperative behaviour, hence the game is a competition between coalitions of players, rather than between individual players...
, which has connections to algebraic coding theory. By 2009, hat problems were "all the rage".
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. 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 code
Hamming code
In telecommunication, Hamming codes are a family of linear error-correcting codes that generalize the Hamming-code invented by Richard Hamming in 1950. Hamming codes can detect up to two and correct up to one bit errors. By contrast, the simple parity code cannot correct errors, and can detect only...
s, which are commonly used to detect and correct errors in data transmission
Data transmission
Data transmission, digital transmission, or digital communications is the physical transfer of data over a point-to-point or point-to-multipoint communication channel. Examples of such channels are copper wires, optical fibres, wireless communication channels, and storage media...
. 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 = 2k−1 and achieve a win rate (2k-1)/2k. 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:
- Any player who observes two hats of two different colours remains silent.
- 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'.
Further reading
- Andrew Liu, "Two Applications of a Hamming Code" The College Mathematics Journal 40 (2009) 2-5.