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

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*.

(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