Introduction
The classic hat guessing game, popularized by Todd Ebert in 1998, has long been a staple of recreational mathematics and coding theory. In the standard version, $n$ players are assigned hats of two possible colors. Each player sees the colors of all other players' hats but not their own. They must simultaneously guess their own hat color or pass. The team wins if at least one player guesses correctly and no player guesses incorrectly. This game is deeply connected to Hamming codes, with the maximum winning probability of $n/(n+1)$ achieved when $n = 2^t - 1$.
In "A New Variation of Hat Guessing Games," authors Tengyu Ma, Xiaoming Sun, and Huacheng Yu extend this challenge. They investigate a variation where the team wins if and only if at least $k$ players guess correctly and zero players guess incorrectly. This modification raises the stakes significantly, requiring higher levels of coordination among players.
Problem Formulation and the Hypercube Model
The game is modeled using an $n$-dimensional boolean hypercube, $Q_n = \{0, 1\}^n$. Each vertex represents a configuration of hats. A strategy for a player $i$ is a function from the observed hats (all except $i$) to a guess in $\{0, 1\}$ or a "pass."
The authors define $P_{n,k}$ as the maximum winning probability for $n$ players with the requirement of $k$ correct guesses. The theoretical upper bound for this probability is $n/(n+k)$. A strategy that achieves this bound is termed a "perfect strategy." The central goal of the paper is to determine the conditions under which such perfect strategies exist and to characterize the behavior of $P_{n,k}$ as $n$ grows.
Methodological Innovation: Regular Partitions
The core of the paper's contribution lies in the study of $(d_1, d_2)$-regular partitions of the hypercube. A partition of the vertex set $V(Q_n)$ into two sets $V_1$ and $V_2$ is $(d_1, d_2)$-regular if:
- Every vertex in $V_1$ has exactly $d_1$ neighbors in $V_2$.
- Every vertex in $V_2$ has exactly $d_2$ neighbors in $V_1$.
This geometric structure is crucial because a perfect strategy for the $k$-hat guessing game corresponds to a specific type of partition where $V_2$ represents the winning configurations. By utilizing linear algebra over the finite field $\mathbb{F}_2$ and recursive construction techniques, the authors demonstrate how to build these partitions. They show that the existence of these partitions allows for the "lifting" of strategies from smaller groups of players to larger ones, effectively linking the game to the theory of $k$-dominating sets.
Key Findings
1. Conditions for Perfection
The authors identify a necessary condition for the existence of a perfect strategy: $n + k = \text{gcd}(n, k)2^s$ for some integer $s$. While they discovered a counterexample at $n=5, k=3$ (showing the condition is not sufficient for all small $n$), they proved that it is "almost" sufficient. Specifically, for any $k$, a perfect strategy exists if $n$ is sufficiently large and the condition is met.
2. Asymptotic Winning Probability
One of the most significant results is the asymptotic behavior of the game. The authors prove that for any fixed $k$, as the number of players $n$ increases, the maximum winning probability $P_{n,k}$ approaches 1. They established a general lower bound: $$P_{n,k} > 1 - \frac{2k}{n+k}$$ This suggests that with enough players, the team can coordinate their guesses to overcome the stricter $k$-correct requirement almost entirely.
3. Concrete Constructions
The paper provides a constructive proof for perfect strategies. For any parameters $d, k, s$ such that $s \ge 2\lceil \lg k \rceil$, the configuration $(n, k) = (d(2^s-k), dk)$ is shown to be perfect. This provides a roadmap for designing optimal strategies in large-scale systems.
Implications and Future Research
The work of Ma, Sun, and Yu bridges the gap between recreational puzzles and the formal study of error-correcting codes. By characterizing $(d_1, d_2)$-regular partitions, they provide tools that may be applicable to other problems in network topology and distributed computing.
However, several questions remain. The exact behavior for small $n$ is still not fully understood, and the precise value of $s(k)$—the threshold for the existence of a perfect strategy—remains an open problem. Furthermore, the current study is limited to the binary (two-color) case. Extending these results to $q$-ary hat games (where hats can be one of $q$ colors) represents a promising frontier for future combinatorial research.
Summary updated