%I #88 Aug 08 2021 11:28:46
%S 1,1,3,5,9,27
%N The classic football pool problem: size of minimal covering code in {0,1,2}^n with covering radius 1.
%C 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].
%C 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
%C 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.]).
%C 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.
%C Combining the above three comments, one obtains ceiling(3^n/(2n+1)) <= a(n) <= 3^(n-floor(log_3(2n+1))) for n >= 0.
%C 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
%D Cohen, Gérard, Iiro Honkala, Simon Litsyn, and Antoine Lobstein, Covering Codes, North-Holland, 1997, p. 174.
%D 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.
%H D. Brink, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Brink/brink3.html">The Inverse Football Pool Problem</a>, J. Int. Seq. 14 (2011) # 11.8.8.
%H Hiram Fernandes and Edgar Rechtschaffen, <a href="https://doi.org/10.1016/0097-3165(83)90033-X">The football pool problem for 7 and 8 matches</a>, Journal of Combinatorial Theory, Series A 35.1 (1983): 109-114.
%H W. Haas, <a href="http://dx.doi.org/10.1016/S0012-365X(00)00461-1">Binary and ternary codes of covering radius one: some new lower bounds</a>, Discrete Math. 245 (2002), 161-178.
%H H. Hamalainen, Iiro Honkala, Simon Litsyn, and Patric Östergård, <a href="http://www.jstor.org/stable/2974552">Football pools - a game for mathematicians</a>, Amer. Math. Monthly, 102 (1995), 579-588.
%H Dmitry Kamenetsky, <a href="/A004044/a004044.txt">Best known solutions for n <= 6</a>
%H H. J. L. Kamps and J. H. van Lint, <a href="https://doi.org/10.1016/S0021-9800(67)80102-9">The football pool problem for 5 matches</a>, Journal of Combinatorial Theory 3.4 (1967): 315-325.
%H G. Keri, <a href="http://www.sztaki.hu/~keri/codes">Tables for Bounds on Covering Codes</a>
%H Klaus-Uwe Koschnick, <a href="https://doi.org/10.1016/0097-3165(93)90079-N">A new upper bound for the football pool problem for nine matches</a>, Journal of Combinatorial Theory, Series A 62.1 (1993): 162-167.
%H Patric R. J. Östergård, <a href="https://doi.org/10.1016/0097-3165(94)90010-8">New upper bounds for the football pool problem for 11 and 12 matches</a>, Journal of Combinatorial Theory, Series A 67.2 (1994): 161-168.
%H P. J. M. van Laarhoven, E. H. L. Aartsa, J. H. van Lint, L. T. Wille, <a href="https://doi.org/10.1016/0097-3165(89)90036-8">New upper bounds for the football pool problem for 6, 7, and 8 matches</a>, Journal of Combinatorial Theory, Series A, 52(2) (1989), 304-312.
%H Ewald W. Weber, <a href="https://doi.org/10.1016/0097-3165(83)90032-8">On the football pool problem for 6 matches: a new upper bound</a>, Journal of Combinatorial Theory, Series A 35.1 (1983): 106-108.
%H L. T. Wille, <a href="https://doi.org/10.1016/0097-3165(87)90012-4">The football pool problem for 6 matches: a new upper bound obtained by simulated annealing</a>, Journal of Combinatorial Theory, Series A 45.2 (1987): 171-177.
%H <a href="/index/Coa#covcod">Index entries for sequences related to covering codes</a>
%e An example for a(4) = 9 is {0000, 0112, 0221, 1022, 1101,1210, 2011, 2120, 2202}. - _Robert P. P. McKone_, Jun 27 2021
%e For a(5) = 27, prepend each of these 9 codewords by 0, 1, and 2. - _Rob Pratt_, Jun 27 2021
%e 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
%Y First column of A060439.
%K nonn,hard,more,nice
%O 0,3
%A _N. J. A. Sloane_
%E Bounds corrected and corresponding reference added by _Jan Kristian Haugland_, Mar 10 2010
%E Edited with more references. - _N. J. A. Sloane_, Jun 21 2021