This is a game played between a team of 3 people (Ann, Bob and Chris, say), and a TV game show host. The team enters the room, and the host places a hat on each of their heads. Each hat is either red or blue at random (the host tosses a coin for each team-member to decide which colour of hat to give them). The players can see each others' hats, but no-one can see their own hat.
Each team member is now invited to guess the colour of their own hat. Each may guess either red or blue, or may pass. The team wins if at least one of them guesses correctly, and none of them guesses incorrectly.
Obviously, the team members can't confer with each other! However, they may have conferred in advance to agree on their strategy. We can now ask two questions: what is a good strategy for the team, and what proportion of the time can they win?
It's clear that the team can win at least half the time, by an easy strategy agreed in advance: Ann will guess "red", while Bob and Chris both pass.
On seeing this problem for the first time, most mathematicians feel that the team cannot win more than half the time. After all, Ann (or any other team member) cannot get any information about her own hat-colour by looking at those of her team-mates, because it was chosen at random, independently of the others. Indeed, on average, half the guesses made will be wrong.
In fact, however, it turns out that this intuition is quite wrong - and in fact this last observation is the key to finding a better strategy. Since half the guesses made will necessarily be wrong, the team should look for a strategy where, when wrong guesses are made, everyone guesses wrongly together.
How is this to be done? Let's look at all the possibilities for what colour hats are worn by the three players (Ann, Bob and Chris, say). There are eight possibilities in all:
| Case 1 | Case 2 | Case 3 | Case 4 | Case 5 | Case 6 | Case 7 | Case 8 | |
|---|---|---|---|---|---|---|---|---|
| Ann | Red | Red | Red | Red | Blue | Blue | Blue | Blue |
| Bob | Red | Red | Blue | Blue | Red | Red | Blue | Blue |
| Chris | Red | Blue | Red | Blue | Red | Blue | Red | Blue |
The important thing to notice is that there are only two cases (cases 1 and 8) where everyone's hat is the same colour. In the remaining six cases, two hats are the same colour, the other hat being different. This suggests the following strategy for members of the team: if you can see two hats of opposite colours, pass. If you can see two hats of one colour, guess that your hat is the other colour.
What will be the result of this strategy? Whenever everyone's hat is the same colour, all players on the team will guess wrongly. But this only happens in two out of eight cases, i.e. a quarter of the time. The rest of the time, the odd person out will guess correctly and their team-mates will pass, so the team will win. For example, in case 4, Ann can see two blue hats, so guesses (correctly) that her own hat is red. Bob and Chris both pass, and the team wins.
This is a very pleasant result. Even though each player has no actual information about the colour of their own hat (and therefore guesses wrongly with half of their guesses), the strategy succeeds in lumping all the wrong guesses together. As a result, the team's overall performance is better than that of any individual could possibly be. There is a useful message here about the value of working in a team!
This strategy wins 3/4 of the time. Could we have done even better with another strategy? A similar argument shows that the answer is "no". Since half of each player's guesses will be wrong, we cannot hope to do better than a strategy where each player in turn guesses correctly alone three times out of four, and the fourth time all guess wrongly. So we have now answered our original questions: the strategy we have found is best possible, and the team can win 3/4 of the time but not more.
Bigger teams
What if there are more players in the team? Say the number of players is n. Reasoning in the same way, we can see that the team cannot hope to win more often than n/(n+1) of the time. But it is not at all obvious that they can do this well. It seems at first sight that the more people are in the team, the harder it will be to synchronise their wrong guesses.
However, it turns out that, if the number of people in the team is one less than a power of 2, this best-possible value can be achieved. For example, with a team of 7, the team can win 7/8 of the time, and with a team of 15, they can win 15/16 of the time. The strategy is complex and delicate, but is closely linked to Hamming codes, a method of encoding and transmitting information so that, even if a small number of errors are made in transmission, the original information can all be recovered. (Such codes are called "error-correcting"; Take a break in issue 12 of Plus is about some simpler error-correcting codes.)
How about other team sizes? One thing we do know is that having more players cannot make things worse for the team. In fact, this is easy to see. For example, we know a team of three can win 3/4 of the time; let's show that a team of five people can do at least as well. Our team of Ann, Bob and Chris is now joined by Davina and Egbert. The strategy is this: Davina and Egbert always pass! Ann, Bob and Chris ignore the other two, and use exactly the same strategy as they were using before. Obviously, they will still succeed 3/4 of the time.
However, this leaves open the question of whether a five-player team could do better, up to the known limit of 5/6. In general, for team-sizes that are not one less than a power of 2, it is not known what the optimal strategy is, or what proportion of the time the team can win.
About the author
Mark Wainwright is an assistant editor of Plus.
Comments
What is the colour of my hat? Two person strategy.
What if, no matter what happens, Chris always chooses to pass, essentially taking himself out of the game. Then you have two people with two possible hat combinations. If Ann then always chooses the hat that Bob is wearing, and Bob always chooses the hat that Ann isn't wearing, one of them will always be right.
In case 1: Ann will see Bob wearing a red hat and she will guess that her hat is red (the one Bob is wearing), thus winning the game. Bob will guess his hat is blue (the one Ann isn't wearing) and will get it wrong.
Case 2: Ann will see a red hat and guess a red hat, winning the game. Bob will see a red hat and guess blue but it won't matter as Ann has already won.
Case 3: Ann will see a blue hat and guess that she is wearing a blue hat, however, Bob will see Ann's red hat and guess that he is wearing a blue hat, winning the game.
In this way, they can guarantee a victory. If Ann and Bob are wearing the same hat, Ann will win. If they are wearing different hats, Bob will win but they can always ensure that at least one of them will guess correctly and win the game.
It said no one can guess
It said no one can guess incorrectly.... you either guess right or pass.
Right
That's true
What is the colour of my hat? 3 person strategy
Ann guesses Bob's hat , Bob guesses Chris' hat and Chris guesses Ann's hat. Therefore one person will always win.
This strategy would work if
This strategy would work if there is no restriction as to who would give his answer first.
In all cases at least two hats are same. The person who sees two same hats answers first and says "Pass". This way the other to would come to know that their hat is same. And they would look at each other's hats and answer the question.