The Toque Game (for winter months)

The Toque Game (for winter months).

Alice and her two friends Bob and Chris are selected to play the "Toque game": They will be seated so that each can see the others. Each will be given a bag containing two toques, one with a white pompom and one with a red pompom. They will then be blindfolded and each will pick a toque at random out of the bag and put it on. When the blindfolds are removed, the players will be able to see the pompom on the other's toque, but not their own. They will not be allowed to communicate by gestures or shouting, and they will have to whisper to a referee standing next to them either "I guess my pompom is white", "I guess my pompom is red", or "I pass". If at least one of them guesses right and nobody guesses wrong, they all win a trip to Moose Jaw, Saskatchewan. Otherwise they just get popcorn. Alice and her friends can devise a strategy before the game to give them better odds. For instance, they could decide that Alice alone will guess and the others will pass; such a strategy gives them a fifty percent chance of winning. Is there a way to do better?

Solution to MP46

Our statement of the problem should have emphasized that the rules of the game permit no signals of any kind. The three players guess simultaneously, and their words are heard only by the referees, not by the other participants. More to the point, the solution must make use of mathematical reasoning, with no trickery. Several of our respondents suggested winning strategies that involved signals much like those used in the game of bridge. Nevertheless we received optimal strategies from Alex Akulov (Regina), Xavier Hecquet (France), Wolfgang Kais (Germany), Patrick LoPresti (USA), Dat Phan (Regina), and Lionel Ruiz (France).

The optimal strategy:

If you see two pompoms of the same colour, guess that your pompom has the opposite colour. Otherwise, pass.

Using this strategy the team will have a 75% chance of winning. To see why, note that there are eight possible arrangements of colours; each of them are equally likely:

Alice	Bob	Chris
Red	Red	Red
Red	Red	White
Red	White	Red
Red	White	White
White	Red	Red
White	Red	White
White	White	Red
White	White	White

In two of these cases, the first and last, the pompoms all have the same colour. By using our strategy here, each participant will guess incorrectly (choosing the opposite colour), so that the team will lose two times out of eight. In the remaining six cases, one pompom has a colour different from the other two. So in the second case, for example, Alice and Bob have red, while Chris has white. Both Alice and Bob will see both colours and pass, while Chris sees two reds and he guesses white. With this strategy the team will win in all six of the mixed cases, so their probability of success will be 75%.

Note that any individual still has only a 50-50 chance of guessing correctly, but it is the team that wins or loses, not the individual. What makes the strategy work is that all of the wrong guesses are gathered together into the two losing cases. There is a lesson to be learned here – In the words of Gadiel Seroussi, director of information theory research at HP Labs, “If the evidence suggests that someone on your team knows more than you, you should keep your mouth shut.”

But, is it possible to do better than 75%? The answer is no, when playing by the rules and using a deterministic strategy. Here is Patrick Lo Presti’s argument. Consider any case C which the team wins. At least one player X guesses correctly. Let C' be the case in which X has his colour switched, but his teammates keep their colours. Then X sees what he saw in case C, but in case C' he guesses incorrectly, and the team loses. By carefully arguing that switching all three colours from case C' to its complementary case will similarly lead to a loss, we see that there must be at least two losing cases.

Further comments.

Of course the same game can be played with any number of players. The general problem is to find a strategy for a team of n players that maximizes its chances of winning. In this form the game reduces to a problem in coding theory and, as such, has applications to error correcting codes (the codes that make data transmission, cell phones, and CDs possible), and to covering codes (which are used to compress data so it takes up less space in a computer’s memory). There seems to be serious mathematics related to the game, but the optimal strategy is not known for n in general. There is a nice discussion of the problem in the New York Times (April 10, 2001; see

http://www.worlds-fastest-website.com/why-mathematicians-care-about-hat-color.htm).

We have also seen articles about it in Scientific American, and in Focus, the newsletter of the Mathematical Association of America. (Sorry, we cannot be more precise with our references at this time.)

math central