login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000983 Size of minimal covering code of length n and covering radius 1.
(Formerly M0329 N0124)
6
1, 2, 2, 4, 7, 12, 16, 32, 62 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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 in the Wikipedia link, 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.

Because each codeword covers n+1 of the 2^n words, A053637(n+1) is a lower bound. - Rob Pratt, Jan 05 2015

a(n) is also the domination number of the n-hypercube graph Q_n. - Eric W. Weisstein, Feb 20 2016

The next term a(10) is in the range 107-120. - Andrey Zabolotskiy, Sep 01 2016

REFERENCES

G. D. Cohen et al., Covering Codes, North-Holland, 1997, p. 166.

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.

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).

LINKS

Table of n, a(n) for n=1..9.

Jernej Azarija, M. A. Henning, S. Klavzar, (Total) Domination in Prisms, arXiv preprint arXiv:1606.08143 [math.CO], 2016. See Table 1.

R. Bertolo, P. R. J. Ostergard and W. D. Weakley, An updated table of binary/ternary mixed covering codes, J. Combin. Designs, 12 (2004), 157-176, DOI:10.1002/jcd.20008. [a(10)>=107]

H. Hamalainen et al., Football pools - a game for mathematicians, Amer. Math. Monthly, 102 (1995), 579-588.

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.

P. R. J. Ostergard and U. Blass, On the size of optimal binary codes of length 9 and covering radius 1, IEEE Trans. Inform. Theory, 47 (2001), 2556-2557. [Determines a(9)].

Eric Weisstein's World of Mathematics, Domination Number

Eric Weisstein's World of Mathematics, Hypercube Graph

Wikipedia, Hat puzzle (Ebert's version and Hamming codes)

Index entries for sequences related to covering codes

CROSSREFS

A column of A060438. Cf. A029866.

Sequence in context: A277752 A095054 A032162 * A095325 A179183 A244457

Adjacent sequences:  A000980 A000981 A000982 * A000984 A000985 A000986

KEYWORD

nonn,hard,more,nice

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 23 13:10 EST 2018. Contains 299581 sequences. (Running on oeis4.)