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

  • Uthaipon Tantipongpipat
Keywords: Ebert's hat game, hat game, game, strong covering, generalized cover

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$.

Published
2014-11-13
Article Number
P4.33