The inverse football pool problem

Brink, David

Journal of integer sequences, Tome 14 (2011) no. 8.

Résumé

Summary: The minimal number of spheres (without "interior") of radius $n$ required to cover the finite set ${0, \dots , 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, \dots $, 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 \ge 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 \le 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.

Détail

Classification : 05B40, 11H31, 52C17
Keywords: minimal covering codes, football pool problem