Journal of Integer Sequences, Vol. 14 (2011), Article 11.8.8

The Inverse Football Pool Problem


David Brink
Institut for Matematiske Fag
Københavns Universitet
Universitetsparken 5
DK-2100
Denmark

Abstract:

The minimal number of spheres (without "interior") of radius n required to cover the finite set {0, ..., q-1}n equipped with the Hamming distance is denoted by T(n,q). The only hitherto known values of T(n,q) are T(n,3) for n = 1, ..., 6. These were all given in the 1950's in the Finnish football pool magazine Veikkaaja along with upper and lower bounds for T(n,3) for n ≥ 7. Recently, Östergård and Riihonen found improved upper bounds for T(n,3) for n = 9,10,11,13 using tabu search. In the present paper, a new method to determine T(n,q) is presented. This method is used to find the next two values of T(n,3) as well as six non-trivial values of T(n,q) with q > 3. It is also shown that, modulo equivalence, there is only one minimal covering of {0,1,2}n for each n ≤ 7, thereby proving a conjecture of Östergård and Riihonen. For reasons discussed in the paper, it is proposed to denote the problem of determining the values of T(n,3) as the inverse football pool problem.


Full version:  pdf,    dvi,    ps,    latex,     PARI source code    


(Concerned with sequences A004044 A086676.)


Received January 14 2011; revised versions received February 19 2011; June 28 2011; September 5 2011. Published in Journal of Integer Sequences, October 16 2011.


Return to Journal of Integer Sequences home page