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