\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Sarang Aravamuthan and Sachin Lodha}
%
%
\medskip
\noindent
%
%
{\bf Covering Codes for Hats-on-a-line}
%
%
\vskip 5mm
\noindent
%
%
%
%
We consider a popular game puzzle, called {\em 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 {\em 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)}.$$
\bye