Covering Codes for Hats-on-a-line

Abstract

We consider a popular game puzzle, called Hats-on-a-line, wherein a warden has $n$ prisoners, each one wearing a randomly assigned black or white hat, stand in a line. Thus each prisoner can see the colors of all hats before him, but not his or of those behind him. Everyone can hear the answer called out by each prisoner. Based on this information and without any further communication, each prisoner has to call out his hat color starting from the back of the line. If he gets it right, he is released from the prison, otherwise he remains incarcerated forever. The goal of the team is to devise a strategy that maximizes the number of correct answers. A variation of this problem asks for the solution for an arbitrary number of colors.

In this paper, we study the standard Hats-on-a-line problem and its natural extensions. We demonstrate an optimal strategy when the seeing radius and/or the hearing radius are limited. We show for certain orderings that arise from a (simulated) game between the warden and prisoners, how this problem relates to the theory of covering codes.

Our investigations lead to two optimization problems related to covering codes in which one leads to an exact solution (for binary codes). For instance, we show that for $0 < k < n$, $(n-k-d) \le \alpha_m n$ where $d = t(n-k, m^k, m)$ is the minimum covering radius of an $m$-ary code of length ($n-k$) and size $m^k$ and $$\alpha_m = {\log m\over \log (m^2 -m +1)}.$$