A004044 The classic football pool problem: size of minimal covering code in {0,1,2}^n with covering radius 1.

1, 1, 3, 5, 9, 27

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• hard
• more
• nice

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

Examples

			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
		

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

• D. Brink, The Inverse Football Pool Problem, J. Int. Seq. 14 (2011) # 11.8.8.
• Hiram Fernandes and Edgar Rechtschaffen, The football pool problem for 7 and 8 matches, Journal of Combinatorial Theory, Series A 35.1 (1983): 109-114.
• W. Haas, Binary and ternary codes of covering radius one: some new lower bounds, Discrete Math. 245 (2002), 161-178.
• H. Hamalainen, Iiro Honkala, Simon Litsyn, and Patric Östergård, Football pools - a game for mathematicians, Amer. Math. Monthly, 102 (1995), 579-588.
• Dmitry Kamenetsky, Best known solutions for n <= 6
• H. J. L. Kamps and J. H. van Lint, The football pool problem for 5 matches, Journal of Combinatorial Theory 3.4 (1967): 315-325.
• G. Keri, Tables for Bounds on Covering Codes
• Klaus-Uwe Koschnick, A new upper bound for the football pool problem for nine matches, Journal of Combinatorial Theory, Series A 62.1 (1993): 162-167.
• Patric R. J. Östergård, New upper bounds for the football pool problem for 11 and 12 matches, Journal of Combinatorial Theory, Series A 67.2 (1994): 161-168.
• 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.
• Ewald W. Weber, On the football pool problem for 6 matches: a new upper bound, Journal of Combinatorial Theory, Series A 35.1 (1983): 106-108.
• L. T. Wille, The football pool problem for 6 matches: a new upper bound obtained by simulated annealing, Journal of Combinatorial Theory, Series A 45.2 (1987): 171-177.
• Index entries for sequences related to covering codes

Crossrefs

First column of A060439.

Extensions

Bounds corrected and corresponding reference added by Jan Kristian Haugland, Mar 10 2010

Edited with more references. - N. J. A. Sloane, Jun 21 2021