Hat problems are a family of mathematical guessing games in which players see some other players' hat colors but not their own. The visibility rules, allowed responses, and winning condition specify the particular problem (Hardin and Taylor 2008, p. 21).
In one standard version, 
players each receive a red or blue hat, chosen by independent
fair coin tosses. Each player sees all other hats.
They may agree on distinct rules in advance, but cannot communicate after the hats
are placed. They simultaneously guess their own colors or pass. The team wins when
at least one guess is correct and none is incorrect (Lenstra and Seroussi 2005, p. 1;
Numberphile 2020).
For three players, each guesses the opposite color when the two visible hats agree and passes otherwise. The team wins on the six mixed-color assignments and loses
on the two monochromatic assignments, giving winning probability 
.
Encode red and blue by 0 and 1. For any deterministic strategy, its losing assignments form a binary covering code of code covering radius at most 1. Indeed, changing the hat of a correct guesser in a winning assignment leaves that player's observation unchanged and makes the guess incorrect. Conversely, given such a covering code, each player considers the two possible completions of the observed colors. If exactly one completion is outside the covering code, the player guesses the color of that completion. Otherwise, the player passes. This wins exactly outside the covering code (Lenstra and Seroussi 2005, pp. 2-3). Randomizing among deterministic strategies cannot improve the optimal winning probability, since their average winning probability cannot exceed the largest of their winning probabilities.
Let 
be the minimum size of such a
binary covering code. Its first values are 1, 2,
2, 4, 7, 12, 16, 32, 62, ... for 
, 2, ... (OEIS A000983).
The optimal winning probability is therefore
 |
Equivalently, the losing assignments are a dominating set in the hypercube graph 
. For 
with 
, a binary Hamming code
attains the sphere-covering bound, giving
 |
This proves optimality of the three-player strategy and gives probability 
for seven players.
The graph game defining the hat guessing number uses different rules: every player guesses, incorrect guesses are allowed, and at least one guess must be correct for every allowed assignment.
