|
|
COMMENTS
|
For k > 0, a(2^k-1) = 2^(2^k-k-1). In this case the minimal covering code is also a Hamming code.
In the game described at http://en.wikipedia.org/wiki/Hat_Puzzle#Hamming_Codes, with n players, the optimal strategy wins with probability 1-a(n)/2^n. In the optimal strategy, the players first agree on a minimal covering code of length n. After the hats are placed, each player knows two words of length n such that one of them is the hat colors of the n players. If one of these two words is a member of the covering code and the other word is not, that player guesses the word that is not. Otherwise, that player does not guess. This strategy guarantees that the team wins for all words that are not members of the covering code.
|
|
|
REFERENCES
|
G. D. Cohen et al., Covering Codes, North-Holland, 1997, p. 166.
H. Hamalainen et al., Football pools - a game for mathematicians, Amer. Math. Monthly, 102 (1995), 579-588.
I. S. Honkala and P. R. J. Ostergard, Code design, Chapter 13 of Local Search in Combinatorial Optimization, E. Aarts and J. K. Lenstra (editors), Wiley, New York 1997, pp. 441-456.
J. G. Kalbfleisch and R. G. Stanton, A combinatorial problem in matching, J. London Math. Soc., 44 (1969), 60-64.
A. Lobstein, G. Cohen and N. J. A. Sloane, Recouvrements d'Espaces de Hamming Binaires, C. R. Acad. Sci. Paris, Series I, 301 (1985), 135-138.
P. R. J. Ostergard and M. K. Kaikkonen, New upper bounds for binary covering codes, Discrete Mathematics 178 (1998), 165-179.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
