Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Covering Codes for Hats-on-a-line. | Covering Codes for Hats-on-a-line Sarang Aravamuthan Advanced Technology Center Hyderabad India. Sachin Lodha Tata Research Development and Design Center Pune India. Submitted Sep 22 2005 Accepted Feb 28 2006 Published Mar 7 2006 Mathematics Subject Classification 91A46 94B75 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 amn where d t n k mk m is the minimum covering radius of an m-ary code of length n k and size mk and log m ữm log m2 m 1 Both ATC and TRDDC are research units of Tata Consultancy Services Limited. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R21 1 1 Introduction In the Hats-on-a-line game puzzle a warden has n prisoners stand in a line and places a hat of color black or white on each of their heads. Starting from
