A Combinatorial Approach to Ebert's Hat Game with Many Colors

Abstract

This paper proves an optimal strategy for Ebert's hat game with three players and more than two hat colors. In general, for $n$ players and $k$ hat colours, we construct a strategy that is asymptotically optimal as $k\rightarrow \infty$. Computer calculation for particular values of $n$ and $k$ suggests that, as long as $n$ is linear with $k$, the strategy is asymptotically optimal. We conclude by comparing our strategy with the strategy of Lenstra and Seroussi and with the bound of Alon, and suggest our strategy is better when $2k \geq n \geq 7$.