Hat puzzle

Hat puzzle

The hat puzzle is a classic logic problem, attributed to Todd Ebert, in his 1998 Ph.D. thesis at the University of California, Santa Barbara. It is a strategy question about a cooperative game, which has been shown to have connections to algebraic coding theory.

Question

A team of $N$ players, where $N$ is at least three, are randomly assigned hats that are equally likely to be white or black, under conditions such that:

# Each team player can see the hats of the other team members, but cannot see their own hat;
# Team members cannot communicate in any way.

Hypothetically, there are $N$ prisoners, but as there was not enough space for all of them. The jailer decides to give them a test, and if all of them succeed in answering it, he will release them, whereas if any one of them answers incorrectly, then he will kill all of them. He describes the test as follows:

All of them go and discuss for some time. And after they come back, he starts the test. Interestingly, each of them answers correctly and hence all are released.

The question is, is there a pre-agreed team strategy for guessing, which will improve on an expected value of 0.5, for the score of the team, when it is awarded as 1 if there is at least one correct hat colour guess and no incorrect guess, and 0 otherwise?

Each prisoner counts the number of white hats and black hats they see, and waits for $10N$ seconds, where $N$ is the lower of the two numbers. After that time, (providing the other prisoners are all doing the same thing), he must be wearing the hat of the colour which he is seeing fewer of.

* Everyone wearing a white hat will see $W-1$ white hats and $B$ black hats.
* Everyone wearing a black hat will see $B-1$ black hats and $W$ white hats.

* If $W < B$ then all white hats will say 'White' at the same time ($10\left(W-1\right)$ seconds), and everyone else knows they are wearing black.
* If $B < W$ then all black hats will say 'Black' at the same time ($10\left(B-1\right)$ seconds), and everyone else knows they are wearing white.
* If $W = B$ then all prisoners will know their colour at the same time. ($10\left(B-1\right)$ seconds, or $10\left(W-1\right)$ seconds, they are equivalent).

Explanation

Four Prisoners

Suppose that there are 4 prisoners, among which two wear black hats and other two wear white.

W W W W "' or "' W B B B

Now, the first one sees two black hats, and a white hat. Had he seen three black hats, he could have easily told that his hat is a white hat, since there should at least be one white hat. Same is true for the second person who is also wearing a white hat. So, all of them are in dilemma. After 10 seconds, each of them thinks that, since the others are not able to deduce their own hat colour, he must be wearing a white hat. So they say WHITE. At about the same time, by similarity, the other two persons say BLACK.

ix Prisoners

Consider that there are 6 prisoners, among which three wear black hats and other three wear white.

W W W "' B B B W W W "' or or "' B B B B B B "' B B B

Now, the first one sees three black hats, and two white hats. Had he seen five black hats, he could have easily told that his hat is a white hat.Also, if he had seen 4 black hats, and a white hat, after 10 seconds, he could have guessed that he must be wearing a white hat since the other person wearing white hat is unable to deduce his hat's colour. (See Four Prisoners). But now he is still in dilemma and is unable to judge the colour even after 20 seconds. So, after 20 seconds, all the persons wearing white hats say WHITE and all the prisoners wearing black hats say BLACK.

Hamming Codes

There is a variation of the puzzle in which the players can answer 'I don't know' as a third choice. In this version there is no relevance in the order, or at what time the players give their answer. One strategy for solving this version of hat problem employs Hamming codes, which are commonly used to detect and correct errors in data transmission. Here, one can't solve the problem in the sense that the players will win in any case, but the probability for winning will be much higher than 50%, depending on the number of players in the puzzle configuration (e.g. winning probability of 87.5% for 7 players when using Hamming codes.)

This strategy can be applied to team sizes of $N = 2^k-1$ (e.g. 3, 7, 15) and achieves an expected value of $frac\left\{2^k-1\right\}\left\{2^k\right\}$. Notably, the Hamming code strategy yields greater expected values for larger values of $N$.

ee also

* Induction Puzzles
* Prisoners and hats puzzle

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Puzzle-Piraten — Puzzle Pirates Entwickler: Three Rings Design Verleger: gamigo AG Publikation: 14. Juni 2004 Plattform(en) …   Deutsch Wikipedia

• Puzzle Piraten — Puzzle Pirates Entwickler Three Rings Design Publisher …   Deutsch Wikipedia

• Puzzle — Vier typische miteinander verbundene Puzzleteile Ein Puzzle [ˈpasl, ˈpʊsl] (engl. [ˈpʌzl] Rätsel, Verwirrung) ist ein mechanisches Geduldspiel, genauer gesagt ein …   Deutsch Wikipedia

• HAT-P-1b — Planetbox begin name=HAT P 1 bPlanetbox star star=ADS 16402 B constell=Lacerta RA=22h 57m 47s DEC=+38° 40 prime; 30 Prime; dist ly=453 ± 65 dist pc=139 ± 20 class=G0V Planetbox orbit semimajor=0.0553 ± 0.0014 period=4.4652934 ± 0.000093… …   Wikipedia

• Puzzle Ball — ein Puzzleball mit historisiertem Globus Aufdruck Der Puzzleball ist ein dreidimensionales Puzzlespiel. Die Teile werden nicht wie beim herkömmlichen Puzzlespiel nebeneinander in einer Ebene gelegt, sondern sie bilden zusammengesetzt eine… …   Deutsch Wikipedia

• Puzzle — Puz·zle [ pazl̩, pasl̩] das; s, s; ein Spiel, bei dem man aus vielen kleinen Teilen ein Bild zusammensetzt <ein Puzzle legen, zusammensetzen> || K : Puzzlespiel || hierzu pụz·zeln (hat) Vi …   Langenscheidt Großwörterbuch Deutsch als Fremdsprache

• Prisoners and hats puzzle — The prisoners and hats puzzle is an induction puzzle (a kind of logic puzzle) that involves reasoning about the actions of other people, drawing in aspects of Game theory. There are many variations, but the central theme remains the same. Not to… …   Wikipedia

• 14-15-Puzzle — 15 Puzzle Spiel aus Plastik (Ordne die Zahlen aufsteigend von 1 bis 15.) Das 15 Puzzle, auch 14 15 Puzzle oder Ohne Fleiß kein Preis Spiel genannt, ist ein in seiner ursprünglichen Aufgabenstellung unlösbares Geduldsspiel. Es wurde zwischen 1870… …   Deutsch Wikipedia

• Pokémon Puzzle Challenge — Das Pokémon Logo Die folgende Auflistung aller Pokémon Videospiele von Nintendo nach Plattform soll einen Überblick über die Entwicklung der Reihe geben. Es werden jeweils zunächst die Rollenspiele genannt. Das Erscheinungsdatum in den Klammern… …   Deutsch Wikipedia

• 15-Puzzle — Spiel aus Plastik (Ordne die Zahlen aufsteigend von 1 bis 15.) Ausgang …   Deutsch Wikipedia