The hat problem may be stated as follows: Three contestants, Alice, Bob, and Cedric, enter a room and a hat is placed on each contestant's head so that he or she can't see it. The color of each hat is based on a coin toss – blue (B) for heads, red (R) for tails. After all the contestants enter the room, they look at the colors of the others' hats and, based on this information, they guess the color of their hat. They can guess red or blue, or, if they can't make up their mind, they can pass. No communication is allowed during the competition, but the players are allowed to agree on a strategy before play begins. The team wins if at least one of them guesses correctly, and none of them guesses incorrectly. What is the team's best strategy? At first sight, it may seem as if no effective strategy is possible beyond each contestant guessing their own hat color. In fact, this is the very worst approach since, to succeed, it requires that everyone guess correctly and the probability of this is only 1/2 × 1/2 × 1/2 = 1/8. A far better plan is for the contestants to agree that two of them will pass while the third takes a stab at the color of their own. Then the odds improve to one in two. Beyond this it is hard to see any way that the probability of success could be increased. Yet there is an even better strategy. The key to it is to realize that that there are only two cases (RRR and BBB) where everyone's hat is the same color but six cases where two hats are the same color and the other hat is a different color (RRB, RBR, BRR, BBR, BRB, and RBB). This suggests the following strategy for members of the team: if you see two hats of opposite colors, pass. If you see two hats of one color, guess that your hat is the other color. If everyone's hat is the same color, all players on the team will guess wrongly and the team will lose. But the chance of this happening is only 2/8 (= 1/4). In every other possible case, the odd person out will guess correctly and their team-mates will pass, so the team will win. This strategy wins 6/8 (= 3/4) of the time – and can't be improved upon. Since half of each player's guesses will be wrong, it's impossible to do better than a strategy in which each player in turn guesses correctly alone three times out of four, and the fourth time all guess wrongly.

What if there are more players in the team? Say the number of players is n. By the reasoning used described, it's clear that the team can't hope to win more than n/(n+1) of the time. Yet it isn't at all obvious that it can do this well. Having more people, it seems, might make it harder for them to synchronize 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 involved is complicated but is closely linked to Hamming codes, which are 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. For teams of the others sizes, such as nine, ten, or 13, mathematicians have yet to find an optimal strategy or establish what proportion of the time the team can be expected to win.