Covering codes for Hats-on-a-line (Q819183)

The authors consider a popular game puzzle, called Hats-on-a-line, where \(n\) prisoners are standing on a line, each one wearing a randomly assigned black or white hat. Each prisoner can see the colors of all hats before him, but not his or of those behind him. Starting from the back of the line, each prisoner has to call out his hat color, his guess being heared by the other prisoners. The goal of the team is to devise a strategy that maximizes the number of correct answers. A variation asks for the solution for an arbitrary number of colors. In the paper the standard problem and a number of natural extensions are studied. An optimal strategy is constructed in the case of a limited seeing radius and/or hearing radius. A game, involving orderings, is introduced between a warden and the prisoners. Investigations lead to two optimization problems related to covering codes in which one leads to an exact solution (for binary codes). For instance, it is shown that for \(0<k<n\), \((n-k-d)\leq \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=\frac{\log m}{\log (m^2-m+1)}\).