|
|
A004044
|
|
The classic football pool problem: size of minimal covering code in {0,1,2}^n with covering radius 1.
|
|
2
|
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
The next 3 terms a(6..8) are in the ranges 71-73, 156-186, 402-486. Also a(13) = 3^10 [Kamps and van Lint, 1969].
Because each codeword covers 2n+1 of the 3^n words, ceiling(3^n/(2n+1)) is a lower bound. - Rob Pratt, Jan 06 2015
a((3^m-1)/2) = 3^((3^m-1)/2 - m) follows from the existence of ternary Hamming codes in these dimensions (see page 286 of [Cohen et al.]).
a(n+1) <= 3*a(n): given a covering of {0,1,2}^n, copy it in each of {i}x{0,1,2}^n for i = 0, 1, 2.
Combining the above three comments, one obtains ceiling(3^n/(2n+1)) <= a(n) <= 3^(n-floor(log_3(2n+1))) for n >= 0.
Conjecture: a((3^m+1)/2) = 3^((3^m+1)/2 - m) for m > 0; i.e., a((3^m-1)/2 + 1) = 3 * a((3^m-1)/2) for m > 0. - Thomas Ordowski, Jul 10 2021
|
|
REFERENCES
|
Cohen, Gérard, Iiro Honkala, Simon Litsyn, and Antoine Lobstein, Covering Codes, North-Holland, 1997, p. 174.
H. J. L. Kamps and J. H. van Lint. "A covering problem." In Colloq. Math. Soc. Janos Bolyai; Hungar. Combin. Theory and Appl., Balantonfured, Hungary, pp. 679-685, 1969.
|
|
LINKS
|
P. J. M. van Laarhoven, E. H. L. Aartsa, J. H. van Lint, L. T. Wille, New upper bounds for the football pool problem for 6, 7, and 8 matches, Journal of Combinatorial Theory, Series A, 52(2) (1989), 304-312.
|
|
EXAMPLE
|
An example for a(4) = 9 is {0000, 0112, 0221, 1022, 1101,1210, 2011, 2120, 2202}. - Robert P. P. McKone, Jun 27 2021
For a(5) = 27, prepend each of these 9 codewords by 0, 1, and 2. - Rob Pratt, Jun 27 2021
van Laarhoven et al. (1989) give examples for a(6), a(7), a(8) which are the best presently known. - R. J. Mathar, Jun 29 2021
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,more,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|