login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A004044 The classic football pool problem: size of minimal covering code in {0,1,2}^n with covering radius 1. 2
1, 1, 3, 5, 9, 27 (list; graph; refs; listen; history; text; internal format)
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
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.
H. Hamalainen, Iiro Honkala, Simon Litsyn, and Patric Östergård, Football pools - a game for mathematicians, Amer. Math. Monthly, 102 (1995), 579-588.
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.
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.
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
First column of A060439.
Sequence in context: A171879 A171877 A339068 * A192152 A217098 A262314
KEYWORD
nonn,hard,more,nice
AUTHOR
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
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 20:05 EDT 2024. Contains 371254 sequences. (Running on oeis4.)