Ebert's hat problem

Ebert's hat problem belongs to the rubric of mathematical conversations and is one of the numerous hat problems (English hat puzzles , often also prisoners and hat puzzles ), in which a number of players are randomly put on different colored hats and you do not know your own hat color, but guess should and can usually gain something. Ebert's hat problem is special in that there are connections to coding theory and to error-correcting codes , especially Hamming codes . This problem became known in 1998 with Todd Ebert's dissertation. B. has also been discussed in the time and spectrum of science .

The three player hat problem

The game with three players is the most popular variant. The players are given either a red or a blue hat at random. Every hat wearer cannot recognize his own hat color. The three players form a team and win if at least one player guesses his hat color correctly and no one gives a wrong answer. Each player is allowed to place a maximum of one tip and the players are not allowed to exchange any information with one another. Each player has only three options: say “red”, say “blue” or keep quiet. An obvious strategy is to oblige one of the players to respond and keep the others silent. This one player will then answer with a probability of 50% correctly.

However, the team can increase their probability of winning to 75% if each player decides as follows:

• If his teammates have hats of different colors, he is silent.
• If they have hats of the same color, he names the hat color that his teammates do not have.

There are a total of 8 possible cases of hat distribution on the three heads, namely

${\displaystyle ({\color {red}\bullet \bullet }{\color {red}\bullet })\quad ({\color {blue}\bullet \bullet }{\color {blue}\bullet })\quad ({\color {red}\bullet \bullet }{\color {blue}\bullet })\quad ({\color {red}\bullet }{\color {blue}\bullet }{\color {red}\bullet })\quad ({\color {blue}\bullet }{\color {red}\bullet \bullet })\quad ({\color {blue}\bullet \bullet }{\color {red}\bullet })\quad ({\color {blue}\bullet }{\color {red}\bullet }{\color {blue}\bullet })\quad ({\color {red}\bullet }{\color {blue}\bullet \bullet })}$.

Only in the two cases that everyone is wearing the same hat color is the answer wrong, and then all three players answer wrong. In the other six cases, exactly one player gives the correct answer, the others are silent. So the chance of winning is 75%. In the eight possible cases, each player guesses correctly twice and incorrectly twice. The highlight is that the six wrong answers concentrate on the two cases of the same color, while the six correct answers each apply to exactly one of the other six cases. The team philosophy could be casually described as follows: “If you lose, then do it right. If there is someone in the team who knows more than you do, then keep quiet. "

generalization

If the number of players is, then the team can reduce the probability of losing to , in the case of players, to . In order to formulate a strategy here, basic ideas about error-correcting codes are necessary. ${\displaystyle n=2^{k}-1;\ k=2,3,\ldots \ }$ ${\displaystyle 1/2^{k}}$ ${\displaystyle k=3}$ ${\displaystyle 7}$ ${\displaystyle 1/8}$

Error correcting codes

See also the popular science introduction to. A sequence of bits can, in principle, transmit messages, because it is the number of possibilities to write zeros or ones in a row. If you want to recognize or correct errors, not each of these bit sequences can be a message. Let a certain bit sequence be a message, also called a code word . The bit sequences that differ from the code word in exactly one place are called error words . In order to be able to correct errors, such an error word must not belong to several code words, i. H. every code word has its "own" error words. Each code word consumes pieces of the stock of bit sequences , one for itself and for its error words. If itself is a power of two, the code words including their error words can just use up the supply completely. Hence, the cases are particularly cheap to treat. With the error-correcting code, which Richard Hamming invented in 1950, the recipient corrects an incorrect message with a simple calculation that can be carried out in the head if necessary. ${\displaystyle n}$ ${\displaystyle 2^{n}}$ ${\displaystyle 2^{n}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 2^{n}}$ ${\displaystyle n+1}$ ${\displaystyle n}$ ${\displaystyle n+1}$ ${\displaystyle 2^{n}}$ ${\displaystyle n=2^{k}-1}$

Application to the hat problem

The players are each given a number from to , but represented as a binary number . In the order of the players, the hat colors are interpreted as a bit sequence, a zero for a red hat, a one for a blue hat. Each player sees the bit sequence with the exception of his own bit. The team of players agrees on the following strategy: They believe that the bit sequence on their hats is a mistake word. On average, this is correct in cases and incorrect in only one case. If the bit sequence is actually a code word, then all players guess wrong. If the bit sequence is an error word, exactly one of the players will recognize it, namely the one at the position of the error. By inserting zero or one for his own hat color, he receives the code word once and the error word once and can thus correctly guess his (error word) hat color. The other players in the non-error positions reach error words by inserting zero or one both times and remain silent. ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

Example hat problem with 7 players

This is what is known as the Hamming Code. The stands for the bit sequence length (or number of players) and by for the number of possible bit sequences. The stands for the number of code words. The following bit sequences are the code words: ${\displaystyle (7,4)}$ ${\displaystyle 7}$ ${\displaystyle 2^{7}=128}$ ${\displaystyle 4}$ ${\displaystyle 2^{4}=16}$ ${\displaystyle 16}$

Code words
0000000	1000110	0100101	0010011	0001111	1100011	1010101	1001001
0110110	0101010	0011100	1110000	0111001	1101100	1011010	1111111

There are also error words. ${\displaystyle 16\cdot 7=112}$

There is now the following strategy for the seven players: Each player adds (without carrying over) the binary numbers of the players with the red hat and receives a check number . ${\displaystyle P}$

• If there are all zeros for a player , he answers “red”. ${\displaystyle P}$
• If a player has his own player number, he answers “blue”. ${\displaystyle P}$
• In all other cases the players remain silent.

As an example, the calculation should now consider the case in which the player with the previously agreed numbers , and red and the other blue wear hats. This corresponds to the word . Each player now determines which other players are wearing red hats and determines their numbers in dual notation. For example, players (like any other blue hat player) will find players and . Now he adds these three numbers without a carryover or, in other words, he determines for each of the three digits individually how many of the players found have one at this point . If this number is even, he puts one in this position ; if it is odd, one . At the first stop is for and the one , for a total of two. So starts with one . In the second place only one has , so too . In the third place it's just that . For thus results . So it is not necessary to know the code words for the calculation. ${\displaystyle 2}$ ${\displaystyle 4}$ ${\displaystyle 5}$ ${\displaystyle 1010011}$ ${\displaystyle 1}$ ${\displaystyle 2=010,4=100}$ ${\displaystyle 5=101}$ ${\displaystyle 1}$ ${\displaystyle P}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 4}$ ${\displaystyle 5}$ ${\displaystyle 1}$ ${\displaystyle P}$ ${\displaystyle 0}$ ${\displaystyle 2}$ ${\displaystyle 1}$ ${\displaystyle P}$ ${\displaystyle 5}$ ${\displaystyle P}$ ${\displaystyle 011}$

With a little practice, the calculation is more convenient for most people, but it should not be confused with the "usual" addition (i.e. addition with carry), as the result shows. It should not be confused with the addition in the remainder class ring modulo , even if the result is the same in this example (see however ). ${\displaystyle 010+100+101=110+101=011}$ ${\displaystyle 2+4+5=3}$ ${\displaystyle 8}$ ${\displaystyle 2+4+6}$

Let us consider two specific cases: First, let the bit sequence of the hats be the code word ${\displaystyle 1010101}$

Player number	001	010	011	100	101	110	111
code word	1	0	1	0	1	0	1
Hat color	${\displaystyle {\color {blue}\bullet }}$	${\displaystyle {\color {red}\bullet }}$	${\displaystyle {\color {blue}\bullet }}$	${\displaystyle {\color {red}\bullet }}$	${\displaystyle {\color {blue}\bullet }}$	${\displaystyle {\color {red}\bullet }}$	${\displaystyle {\color {blue}\bullet }}$
Check number ${\displaystyle P}$	010 + 100 + 110 = 000	100 + 110 = 010	000	010 + 110 = 100	000	010 + 100 = 110	000
Player response	${\displaystyle {\color {red}\bullet }}$	${\displaystyle {\color {blue}\bullet }}$	${\displaystyle {\color {red}\bullet }}$	${\displaystyle {\color {blue}\bullet }}$	${\displaystyle {\color {red}\bullet }}$	${\displaystyle {\color {blue}\bullet }}$	${\displaystyle {\color {red}\bullet }}$

All players answered incorrectly. That is likely to happen . ${\displaystyle 16/128=1/8}$

Now let the bit sequence of the hats be the error word . Incidentally, this is an error word for the code word , the error is in the first position. ${\displaystyle 1010011}$ ${\displaystyle 0010011}$

Player number	001	010	011	100	101	110	111
Error word	1	0	1	0	0	1	1
Hat color	${\displaystyle {\color {blue}\bullet }}$	${\displaystyle {\color {red}\bullet }}$	${\displaystyle {\color {blue}\bullet }}$	${\displaystyle {\color {red}\bullet }}$	${\displaystyle {\color {red}\bullet }}$	${\displaystyle {\color {blue}\bullet }}$	${\displaystyle {\color {blue}\bullet }}$
Check number ${\displaystyle P}$	010 + 100 + 101 = 011	100 + 101 = 001	011	010 + 101 = 111	010 + 100 = 110	011	011
Player response	remain silent	remain silent	${\displaystyle {\color {blue}\bullet }}$	remain silent	remain silent	remain silent	remain silent

As with all error words, one player is typing correctly here.

The hat problem for any number of players

So far there has been no optimal behavioral strategy. If so , then it would be pragmatic to play according to the recipe for the next lower power of two and thus secure the corresponding success rate. The surplus players are condemned to silence and their hat colors are ignored. ${\displaystyle n\neq 2^{k}-1}$

Individual evidence

1. ^ E. Brown, J. Tanton: A Dozen Hat Problems. In: Math Horizons. April 2009, pp. 22-25.
2. ^ T. Ebert: Applications of Recursive Operators to Randomness and Complexity. Ph.D. Thesis, University of California, Santa Barbara 1998.
3. ↑ Wolfgang Blum: Thinking exercise for hat wearers. In: The time. May 3, 2001.
4. ↑ ^{a b} Christoph Pöppe: The hat problem. Spectrum of Science, September 1, 2001.
5. ^ Richard W. Hamming: Error Detecting and Error Correcting Codes. In: Bell System Technical Journal. Volume 29, No. 2, 1950, pp. 147-160.