Hat puzzle

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

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.[2]



Another Version is the White Hat, Black Hat version

There are three men sitting around a round table. There are five hats on the table, two black, three white. All three men are then blindfolded, hats are placed on their heads. The other hats are then removed. These men are supposed to figure out the colour of their hat by only looking at the other men's hats. The first man removes his blindfold, after looking at the other men's hats he says that he cannot figure out the colour of his hat and gives up. The second man then removes his blindfold looking at the other men and cannot figure out the colour of his hat and gives up. But the third man, without removing his blindfold says the colour of his hat correctly.

What colour hat is the third man wearing and how did he figure it?


Solution

The third man was wearing a white hat The first man takes off his blindfold. If the other two men were wearing a black hat he would have known he was wearing a white hat - therefore not possible - so, one or none of the other men were wearing a black hat. The second man took off his blindfold, while looking at the third man, he realised that if the third man was wearing a black hat that he could not. So he would have to be wearing a white hat cause he was unsure of his own hat colour therefore guaranteeing the third man having a white hat.



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

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 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.[5]

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:

  1. Count the numbers b of black hats and w of white hats that you see.
  2. Wait b seconds or w seconds, whichever is sooner.
  3. 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.
  4. 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 = 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:

  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'.[6]

References

  1. ↑ Hardin, Christopher; Taylor, Alan D. (2008). "An introduction to Infinite Hat Problems" (PDF). Mathematical Intelligencer. 30 (4).
  2. ↑ Brown, Ezra; Tanton, James (April 2009). "A Dozen Hat Problems" (PDF). Math Horizons: 22–25. Retrieved 2011-10-08.
  3. ↑ Winkler, Peter (2004). Mathematical Puzzles: A Connoisseur's Collection. A K Peters. pp. 125–126.
  4. ↑ Biography of Todd Ebert at California State University, Long Beach
  5. ↑ Gardner, Martin (1978). Aha! Insight. Scientific American. p. 102. ISBN 0-89454-001-7. Retrieved 2011-10-08.
  6. ↑ Havil, Julian (2008). Impossible? Surprising Solutions to Counterintuitive Conundrums. Princeton University Press. pp. 50–59. ISBN 9780691131313. Retrieved 2011-10-08.

Further reading

See also

This article is issued from Wikipedia - version of the 10/18/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.