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

Table of n, a(n) for n=0..5.

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

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

Adjacent sequences:  A004041 A004042 A004043 * A004045 A004046 A004047

KEYWORD

nonn,hard,more,nice

AUTHOR

N. J. A. Sloane

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 July 5 06:17 EDT 2022. Contains 355088 sequences. (Running on oeis4.)