\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{mathrsfs}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf The Inverse Football Pool Problem}
\vskip 1cm
\large
David Brink\\
Institut for Matematiske Fag\\
K\o benhavns Universitet\\
Universitetsparken 5\\
DK-2100\\
Denmark\\
\href{mailto:brink@math.ku.dk}{\tt brink@math.ku.dk} \\
\end{center}

\vskip .2 in

\begin{abstract}
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
1950s in the Finnish football pool magazine \emph{Veikkaaja} along with
upper and lower bounds for $T(n,3)$ for $n\geq 7$. Recently,
\"Osterg\aa 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\leq 7$,
thereby proving a conjecture of \"Osterg\aa 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 \emph{inverse football pool
problem}.
\end{abstract}

\section{Introduction}

Consider the finite set $Q=\{0,\dots,q-1\}^n$ equipped with the Hamming distance
\[
d(\textbf{x},\textbf{y})=|\{i:\ x_i\neq y_i\}|
\]
for $\textbf{x}=(x_1,\dots,x_n)$ and $\textbf{y}=(y_1,\dots,y_n)$ in $Q$.
Let
\[
\mathscr{B}(\textbf{x}_0,r)=\{\textbf{x}\in Q:\ d(\textbf{x},\textbf{x}_0)\leq r\}
\mbox{, \ }
\mathscr{S}(\textbf{x}_0,r)=\{\textbf{x}\in Q:\ d(\textbf{x},\textbf{x}_0)= r\}
\]
be the ball and sphere, respectively, with centre $\textbf{x}_0$ and radius $r$.\footnote{Note that the word ``sphere'' is often used in the literature for what is here called a ``ball.''}

These simple concepts give rise to a plethora of combinatorial problems.
The most famous is the \emph{football pool problem} which
asks for the minimal number $K_3(n,1)$ of balls of radius 1 required to cover $\{0,1,2\}^n$.
In the football pools, one bets simultaneously on the outcomes of a number of football games, typically $n=12$ or 13.
Each game has three possible outcomes: win, draw or loss.
A bet can thus be thought of as a point in $\{0,1,2\}^n$,
and $K_3(n,1)$ is equal to the minimal number of bets on $n$ games required to guarantee at least one bet with at most one wrong outcome.

The complexity of such problems increases drastically with $n$. Indeed, when $n$ is not of the form $(3^m-1)/2$ and the existence of a perfect Hamming code shows $K_3(n,1)=3^n/(2n+1)$, then $K_3(n,1)$ is only known for $n=2,3,5$, cf.\ Sloane's A004044 \cite{Sloane}. See also \cite{Football} for an interesting discussion of this and related problems.

In the present paper, we study coverings of $Q$ with spheres of radius $n$.
Such spheres are $n$-dimensional grid graphs, i.e., they are
of the form $\prod_{i=1}^n A_i$ where $A_i\subset \{0,\dots,q-1\}$ with $|A_i|=q-1$.
The function defined below therefore equals the special case $T(n,q,q-1)$ of the function $T(n,q,p)$ introduced by \"Osterg\aa rd and Riihonen \cite{Tori}.

\begin{definition}
\label{def1}
Let $T(n,q)$ be the minimal number of spheres of radius $n$ required to cover~$Q$.
\end{definition}

We shall be particularly concerned with the problem of determining the values of $T(n,3)$, Sloane's A086676.
We propose to call this the \emph{inverse football pool problem} since it means asking for the minimal number of bets needed to guarantee that at least one is \emph{totally wrong}.

The inverse football pool problem was first considered in the Finnish football pool magazine
\emph{Veikkaaja} in the
1950s.\footnote{As was the ordinary football pool problem in the previous decade. Indeed, \emph{Veikkaaja} holds a place of the first rank in the history of combinatorics. It was here that Juhani Virtakallio gave the \emph{ternary Golay code} (a perfect covering of $\{0,1,2\}^{11}$ with 729 balls of radius 2) in 1947, two years before its rediscovery by Marcel Golay.}
The principal goal then was to determine $T(12,3)$, a value which remains unknown today.
The only hitherto known values of $T(n,q)$ are $T(1,3)=2$, $T(2,3)=3$, $T(3,3)=5$, $T(4,3)=8$, $T(5,3)=12$, and $T(6,3)=18$. The history of these results is discussed below.

The results in \emph{Veikkaaja} on the inverse football pool problem seem to have been unknown to the mathematical community until they were discovered by
\"Osterg\aa rd and Riihonen in 2002 and presented in \cite{Tori} and \cite{Riihonen}. All references to \emph{Veikkaaja} here come from these two papers.

\section{General bounds}

First we state some easy or well-known bounds.
If a sphere covering of $\{0,\dots,$ $q-1\}^n$ is given, a covering of $\{0,\dots,q-1\}^{n-1}$ is obtained by discarding the last coordinate as well as all spheres whose centres have any given value in that coordinate, cf.\ \emph{Veikkaaja} no.\ 23, 1956, and \cite[Theorem 3.3]{Tori}. Hence
\begin{equation}
\label{1.5}
T(n,q)\geq \frac{q}{q-1}\cdot T(n-1,q).
\end{equation}
In particular, it follows inductively from $T(1,q)=2$ that $T(n,q)\geq n+1$.
If $n<q$, the spheres with centres $(0,\dots,0),\dots,(n,\dots,n)$ cover $Q$. Thus
\begin{equation}
\label{trivial}
T(n,q)=n+1\ \mbox{for}\ n<q.
\end{equation}
Taking direct product gives
\begin{equation}
\label{direct}
T(n+n',q)\leq T(n,q)\cdot T(n',q).
\end{equation}
Finally, an exceedingly elegant and ingenious construction for $q=3$, described in \emph{Veikkaaja} no.\ 15, 1960, and \cite[Corollary 3.5]{Tori}, gives the bound
\begin{equation}
\label{elegant}
T(n+n'-2,3)\leq \frac{1}{3}\cdot T(n,3)\cdot T(n',3)
\end{equation}
(and sometimes a little more, cf.\ \cite[Theorem 3.4]{Tori})
which is considerably better than \eqref{direct}.

\begin{definition}
\label{def2}
(a) We represent a covering of $\{0,\dots,q-1\}^n$ with $m$ spheres $\mathscr{S}(\textbf{x}_1,n),\dots,$ $\mathscr{S}(\textbf{x}_m,n)$ by the $n\times m$ \emph{covering matrix} $A$ whose columns are the centres $\textbf{x}_1,\dots,\textbf{x}_m$.

(b) Two covering matrices of the same size (and the sphere coverings they represent) are called \emph{equivalent} if one can be transformed into the other by permuting rows and columns and by renaming the symbols in any given row.\footnote{By ``renaming the symbols,'' we mean that given any row $\textbf{a}=(a_1,\dots,a_m)$ and given any permutation $\sigma$ of $0,\dots,q-1$, we may replace $\textbf{a}$ by $(\sigma(a_1),\dots,\sigma(a_m))$.}

(c) We call a covering matrix \emph{canonical} if it is minimal among all equivalent matrices with respect to the lexicographic ordering (reading first row 1 from left to right, then row 2 from left to right, etc.).
\end{definition}

The definition of equivalence is standard.
If $n<q$, for example, the matrix consisting of $n$ identical rows $(0,1,\dots,n)$ is the unique canonical $n\times (n+1)$ covering matrix, cf.\ \eqref{trivial}.
Note that there is a 1--1 correspondence between equivalence classes of coverings and canonical covering matrices.
The following lemma is a generalization of \eqref{1.5}.

\begin{lemma}
\label{lem1}
Suppose $A$ is an $n\times m$ covering matrix.
Let there be given $b_i\in\{0,\dots,q-1\}$ for all $i$ in some proper subset $I\subset\{1,\dots,n\}$.
Then the number of columns $(a_1,\dots,a_n)^t$ of $A$ with $a_i\neq b_i$ for all
$i\in I$ is at least $T(n-|I|,q)$.
\end{lemma}

\begin{proof}
For each $i\in I$, delete all columns $(a_1,\dots,a_n)^t$ of $A$ having $a_i= b_i$.
Then delete row $i$ for each $i\in I$. The resulting matrix $A'$ is a covering matrix for $\{0,\dots,q-1\}^{n-|I|}$ and hence has at least $T(n-|I|,q)$ columns.
\end{proof}

\section{Main results}

\begin{theorem}
\label{thm1}
We have the following two values of $T(n,3)$, i.e., the minimal number of spheres of radius $n$ needed to cover $\{0,1,2\}^n$: $T(7,3)=29$ and $T(8,3)=44$.
\end{theorem}

\begin{proof}
The lower bounds $T(7,3)\geq 27$ and $T(8,3)\geq 41$ follow from \eqref{1.5} and \eqref{trivial}. The upper bounds $T(7,3)\leq 29$ and $T(8,3)\leq 44$ are known, cf.\ \cite{Tori} and the discussion below.
After having shown $T(7,3)=29$, it will follow that $T(8,3)=44$ by \eqref{1.5}.
The rest of the proof consists of three parts. First we describe in general our method for finding canonical covering matrices. Then we illustrate this method by proving in detail the bound $T(3,7)>27$. Finally we discuss how the method can be used to prove $T(3,7)>28$.

Suppose $A$ is a canonical $n\times m$ covering matrix. Then, 
by Definition~2 and Lemma~\ref{lem1},
the following two conditions hold for each $i=1,\dots,n$:
\begin{enumerate}
  \item[(I)] The $i\times m$ submatrix $A_i$ consisting of the first $i$ rows of $A$ is canonical.
  \item[(II)] Given $b_1,\dots,b_i \in \{0,\dots,q-1\}$, there are at least $T(n-i,q)$ columns $(a_1,\dots,a_i)^t$ of $A_i$ satisfying $a_j\neq b_j$ for all $j=1,\dots,i$.
\end{enumerate}
In order to find all canonical $n\times m$ matrices, we proceed as follows: First find the set $R_1$ of all rows $r_1$ such that the $1\times m$ matrix $A_1$ consisting only of $r_1$ satisfies (I) and (II). Then, for each $r_1\in R_1$, find the set $R_2(r_1)$ of all rows $r_2$ such that the $2\times m$ matrix $A_2$ consisting of $r_1$ and $r_2$ satisfies (I) and (II).
Next, for each $r_1\in R_1$ and $r_2\in R_2(r_1)$, find the set $R_3(r_1,r_2)$, and so forth.
Every time a non-empty set $R_n(r_1,\dots,r_{n-1})$ is obtained in this way, each row $r_n$ in that set gives rise to a canonical $n\times m$ covering matrix, namely the matrix consisting of  $r_1,\dots,r_n$.



To illustrate the method just described, we prove in detail the bound $T(7,3)>27$.
Suppose indirectly that a covering of $\{0,1,2\}^7$ is given as a canonical $7\times 27$ covering matrix $A$. First we find $R_1$. By condition (I), every $r_1\in R_1$ is of the form
\[
\begin{array}{r}
r_1=(
\overbrace{0,\dots,0}^{l_0\ \mathrm{times}},
\overbrace{1,\dots,1}^{l_1\ \mathrm{times}},
\overbrace{2,\dots,2}^{l_2\ \mathrm{times}}
)
\end{array}
\]
with
\begin{equation}\label{27}
    l_0+l_1+l_2=27.
\end{equation}
By specifying $b_1\in\{0,1,2\}$ and using $T(6,3)=18$, condition (II) gives the following three linear inequalities:
\begin{equation}\label{18}
    \begin{array}{ccc}
  l_1+l_2  \geq  18, &
  l_0+l_2  \geq  18, &
  l_0+l_1  \geq  18.
\end{array}
\end{equation}
It follows immediate from (\ref{27}) and (\ref{18}) that $l_0=l_1=l_2=9$ and hence
\[
\begin{array}{r}
r_1=(0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2).
\end{array}
\]
Then we find $R_2(r_1)$. By condition (I), every $r_2\in R_2(r_1)$ is of the form
\[
\begin{array}{r}
r_2=(
\overbrace{0,\dots,0}^{l_0\ \mathrm{times}},
\overbrace{1,\dots,1}^{l_1\ \mathrm{times}},
\overbrace{2,\dots,2}^{l_2\ \mathrm{times}},
\overbrace{0,\dots,0}^{l_0'\ \mathrm{times}},
\overbrace{1,\dots,1}^{l_1'\ \mathrm{times}},
\overbrace{2,\dots,2}^{l_2'\ \mathrm{times}},
\overbrace{0,\dots,0}^{l_0''\ \mathrm{times}},
\overbrace{1,\dots,1}^{l_1''\ \mathrm{times}},
\overbrace{2,\dots,2}^{l_2''\ \mathrm{times}}
)
\end{array}
\]
with
\begin{equation}\label{9}
l_0+l_1+l_2=l_0'+l_1'+l_2'=l_0''+l_1''+l_2''=9.
\end{equation}
By specifying $b_1,b_2\in\{0,1,2\}$ and using $T(5,3)=12$, condition (II) now gives the following nine linear inequalities:
\begin{equation}\label{12}
\begin{array}{rrr}
  l_1'+l_2'+l_1''+l_2''  \geq  12, &
  l_0'+l_2'+l_0''+l_2''  \geq  12, &
  l_0'+l_1'+l_0''+l_1''  \geq  12,\\
  l_1+l_2+l_1''+l_2''  \geq  12, &
  l_0+l_2+l_0''+l_2''  \geq  12, &
  l_0+l_1+l_0''+l_1''  \geq  12,\\
  l_1+l_2+l_1'+l_2'  \geq  12, &
  l_0+l_2+l_0'+l_2'  \geq  12, &
  l_0+l_1+l_0'+l_1'  \geq  12.
\end{array}
\end{equation}
It is not difficult to show that (\ref{9}) and (\ref{12}) imply
$l_0=l_1=l_2=l_0'=l_1'=l_2'=l_0''=l_1''=l_2''=3$ and consequently
\[
\begin{array}{r}
r_2=(0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2).
\end{array}
\]
Similarly, in order to determine the elements $r_3\in R_3(r_1,r_2)$, we get from (I), (II), and $T(4,3)=8$ a system of 27 linear inequalities in 27 unknowns which together imply
\[
\begin{array}{r}
r_3=(0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2).
\end{array}
\]
The determination of $R_4(r_1,r_2,r_3)$ is somewhat more complicated. It is possible by hand to proceed as above and show that this set consists only of
\[
\begin{array}{r}
r_4=(0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1, 2, 0).
\end{array}
\]
It is then relatively easy to show that $R_5(r_1,r_2,r_3,r_4)$ is empty and that in consequence no $7\times 27$ covering matrix of $\{0,1,2\}^7$ exists.
However, it is also possible at this point to make a short-cut. The determination of $r_1$, $r_2$, and $r_3$ shows that every possible column vector $(b_1,b_2,b_3)^t$ with $b_i\in\{0,1,2\}$ occurs exactly $\lambda=1$ times in the $3\times 27$ matrix $A_3$. By symmetry, the same holds for any $3\times 27$ submatrix of $A$ formed by $t=3$ arbitrary rows. This means that the $7\times 27$ matrix $A$ is an \emph{orthogonal array} with $q=3$ \emph{levels}, \emph{index} $\lambda=1$, and \emph{strength} $t=3$. But by a result of Bush \cite{Bush}, a such matrix can have at most $t+1=4$ rows, thus disproving the existence of $A$.

The method used to prove $T(7,3)>28$ is exactly the same, but now the row sets $R_i$ for the hypothetical $7\times 28$ covering matrix become too large to do the demonstration by hand. For example, $R_1$ consists of the two rows
\[
\begin{array}{r}
r_1 =(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2),\\
r_1'=(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2),
\end{array}
\]
and $R_2(r_1)$ consists of
\[
\begin{array}{r}
r_2 =(0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2, 2, 2),\\
r_2'=(0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 1, 1, 1, 2, 2, 2),
\end{array}
\]
while $R_2(r_1')$ consists of
\[
\begin{array}{r}
r_2 =(0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 1, 2, 2, 0, 0, 0, 1, 1, 2, 2, 2, 2),\\
r_2'=(0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2).
\end{array}
\]
Instead, the method can be implemented on a computer to show that no such matrix exists.
This computation took 28 seconds on the author's laptop.
\end{proof}

\[
\begin{array}{c|c}
n & T(n,3) \\
\hline
1 & 2 \\
2 & 3 \\
3 & 5 \\
4 & 8 \\
5 & 12\\
6 & 18
\end{array}
\hspace{2cm}
\begin{array}{c|c}
7 & 29 \\
8 & 44 \\
9 & 66-68 \\
10 & 99-104 \\
11 & 149-172 \\
12 & 224-264 \\
13 & 336-408
\end{array}
\]
\\
\hspace*{\fill}
{\footnotesize \textbf{Table 1: } Old and new results on $T(n,3)$.}
\hspace*{\fill}
\\

Table~1 collects old and new results on $T(n,3)$.
All values for $n\leq 6$ as well as the bounds $T(7,3)\leq 29$ and $T(8,3)\leq 44$ go back to \emph{Veikkaaja}.\footnote{It remains somewhat of a mystery, though, how the coverings proving these results were found.}
All lower bounds for $n\geq 9$ come from $T(7,3)=29$ combined with \eqref{1.5}.
Note that $T(7,3)=29$ is the first counter-example to the natural conjecture $T(n,3)=\lceil \tfrac{3}{2}\cdot T(n-1,3)\rceil$.
The upper bounds for $n=9,10$ were found in \cite{Tori} using
so-called \emph{tabu search}.
The upper bounds for $n=11,12,13$ follow from the upper bounds for smaller $n$ using \eqref{elegant}.
A covering proving $T(12,3)\leq 264$ appears explicitly in \emph{Veikkaaja} no.\ 52, 1960.
As related in \cite{Riihonen}, a writer in fact claims in \emph{Veikkaaja} no.\ 15, 1960, to be in possession of a covering proving $T(12,3)\leq 242$, but states---not unlike Pierre de Fermat three centuries earlier---that it is too long to be printed in the magazine!

The case $n=7$ of the following theorem was conjectured in \cite{Tori}.

\begin{theorem}
\label{thm2}
Modulo equivalence, there is only one minimal covering of $\{0,1,2\}^n$ with spheres of radius $n$ for each $n=1,\dots,7$.
\end{theorem}

\begin{proof}
The statement can be proved by hand for $n\leq 6$. We exemplify this by sketching the case $n=6$. By the same arguments as in the proof of Theorem~\ref{thm1}, the first three rows of a canonical $6\times 18$ covering matrix $A$ must be
\[
\begin{array}{r}
r_1=(0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2),  \\
r_2=(0, 0, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2),  \\
r_3=(0, 1, 0, 2, 1, 2, 0, 2, 1, 2, 0, 1, 1, 2, 0, 1, 0, 2).
\end{array}
\]
Now there are three candidates for row 4:
\[
\begin{array}{r}
r_4  =(0, 1, 1, 2, 2, 0, 2, 1, 2, 0, 1, 0, 0, 2, 0, 1, 2, 1),   \\
r_4' =(0, 1, 2, 0, 2, 1, 2, 0, 1, 2, 1, 0, 2, 1, 1, 0, 0, 2),   \\
r_4''=(0, 1, 2, 1, 0, 2, 1, 2, 2, 0, 0, 1, 2, 0, 1, 0, 2, 1).
\end{array}
\]
But also rows 5 and 6 must be chosen among $r_4$, $r_4'$, and $r_4''$.
One can check directly that the only way to get a covering is to take one of each.
Since the rows of a canonical matrix must come in increasing order, rows 4--6 of $A$ must be $r_4$, $r_4'$, and $r_4''$ in that order.

The case $n=7$ is too complicated to settle by hand, but an exhaustive computer search following the same principles as described in the proof of Theorem~\ref{thm1} finds only one canonical matrix (namely the one given at the end of this paper).
\end{proof}

We do not know if the covering of $\{0,1,2\}^8$ with 44 spheres is unique.

Next we consider values of $T(n,q)$ with $q>3$ (the case $q=2$ being trivial).

\begin{theorem}
\label{thm3}
We have the following values of $T(n,q)$, i.e., the minimal number of spheres of radius $n$ needed to cover $\{0,\dots,q-1\}^n$:
\[
\begin{array}{c|ccccc}
n & T(n,4)& T(n,5) & T(n,6) & T(n,7) \\
\hline
1 & 2                &2                    &2                   &2\\
2 & 3                &3                    &3                   &3\\
3 & 4                &4                    &4                   &4\\
4 & \mathbf{7}       &5                    &5                   &5\\
5 & \mathbf{10}      &\mathbf{8}           &6                   &6\\
6 & \mathbf{14-16}   &\mathbf{11}          &\mathbf{10}         &7\\
7 & \mathbf{19-28}   &\mathbf{14-20}       &\mathbf{12-18}      &\mathbf{11}
\end{array}
\]
The values typed in boldface are the non-trivial ones, i.e., the ones not following from equation \eqref{trivial}.
\end{theorem}

\begin{proof}
The theorem is shown by a computer search following the same principles as in the proof of Theorem~\ref{thm1}. All results were found within 24 hours of computer time, some of them within minutes or seconds.
A few non-trivial partial results can be proved by hand. For example, one can see $T(4,4)>6$ by showing that rows 1--3 of a canonical $4\times 6$ covering matrix must necessarily be (0, 0, 1, 1, 2, 3),
(0, 1, 0, 1, 2, 3), (0, 1, 1 ,0, 2, 3), but that this leaves no possibilities for row 4.
All lower and upper bounds in the undecided cases are straightforward consequences of \eqref{1.5} and \eqref{direct}.
\end{proof}


It appears that minimal coverings are more abundant when $q$ is composite.

\section{Appendix: Lexicographically minimal covering matrices}

Finally, we present for each non-trivial value of $T(n,q)$ given in Theorem~\ref{thm3} as well as for $q=3$ and $n=3,\dots,7$ the unique lexicographically minimal $n\times T(n,q)$ covering matrix.
\\[5mm]
\begin{tabular}{lll}
$T(3,3)=5$:     &$T(4,3)=8$:             &$T(5,3)=12$:\\
(0, 0, 1, 1, 2) &(0, 0, 0, 1, 1, 1, 2, 2)&(0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2)\\
(0, 1, 0, 1, 2) &(0, 0, 1, 0, 1, 1, 2, 2)&(0, 0, 1, 2, 0, 1, 1, 2, 0, 1, 2, 2)\\
(0, 1, 1, 0, 2) &(0, 1, 2, 2, 0, 1, 0, 1)&(0, 1, 0, 2, 1, 0, 1, 2, 2, 2, 0, 1)\\
                &(0, 1, 2, 2, 0, 1, 1, 0)&(0, 1, 2, 1, 2, 1, 0, 2, 0, 2, 1, 0)\\
                &                        &(0, 1, 2, 2, 2, 1, 0, 1, 2, 0, 0, 1)
\end{tabular}
\\[3mm]
\begin{tabular}{l}
$T(6,3)=18$:\\
(0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2)\\
(0, 0, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2)\\
(0, 1, 0, 2, 1, 2, 0, 2, 1, 2, 0, 1, 1, 2, 0, 1, 0, 2)\\
(0, 1, 1, 2, 2, 0, 2, 1, 2, 0, 1, 0, 0, 2, 0, 1, 2, 1)\\
(0, 1, 2, 0, 2, 1, 2, 0, 1, 2, 1, 0, 2, 1, 1, 0, 0, 2)\\
(0, 1, 2, 1, 0, 2, 1, 2, 2, 0, 0, 1, 2, 0, 1, 0, 2, 1)
\end{tabular}
\\[3mm]
\begin{tabular}{l}
$T(7,3)=29$:\\
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2)\\
(0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2, 2, 2)\\
(0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 2, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 0, 0, 1, 1)\\
(0, 1, 0, 2, 0, 2, 1, 2, 0, 1, 2, 1, 2, 0, 2, 0, 2, 0, 1, 0, 2, 0, 1, 1, 2, 0, 1, 1, 2)\\
(0, 1, 1, 2, 2, 1, 2, 0, 1, 0, 2, 2, 0, 2, 1, 1, 2, 0, 1, 2, 1, 1, 0, 2, 0, 0, 1, 0, 2)\\
(0, 1, 2, 0, 2, 0, 1, 2, 0, 1, 2, 1, 2, 2, 0, 2, 0, 0, 1, 0, 2, 1, 0, 2, 1, 1, 0, 2, 1)\\
(0, 1, 2, 1, 1, 2, 2, 0, 1, 0, 2, 2, 0, 1, 2, 2, 1, 0, 1, 2, 1, 0, 1, 0, 2, 1, 0, 2, 0)
\end{tabular}
\\[3mm]
\begin{tabular}{lll}
$T(4,4)=7$:          &$T(5,4)=10$:                  &$T(5,5)=8$:\\
(0, 0, 0, 1, 1, 1, 2)&(0, 0, 0, 1, 1, 1, 2, 2, 2, 3)&(0, 0, 0, 1, 1, 1, 2, 3)\\
(0, 1, 2, 0, 1, 2, 3)&(0, 0, 0, 1, 1, 1, 2, 2, 2, 3)&(0, 1, 2, 0, 1, 2, 3, 4)\\
(0, 1, 2, 0, 1, 2, 3)&(0, 1, 2, 0, 1, 2, 0, 1, 2, 3)&(0, 1, 2, 0, 1, 2, 3, 4)\\
(0, 1, 2, 1, 2, 0, 3)&(0, 1, 2, 0, 1, 2, 0, 1, 2, 3)&(0, 1, 2, 1, 2, 0, 3, 4)\\
                     &(0, 1, 2, 1, 2, 0, 2, 0, 1, 3)&(0, 1, 2, 1, 2, 0, 3, 4)
\end{tabular}
\\[3mm]
\begin{tabular}{ll}
$T(6,5)=11$:                     &$T(6,6)=10$:                  \\
(0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 4)&(0, 0, 0, 0, 1, 1, 1, 1, 2, 3)\\
(0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 4)&(0, 1, 2, 3, 0, 1, 2, 3, 4, 5)\\
(0, 1, 2, 0, 1, 2, 0, 1, 2, 3, 4)&(0, 1, 2, 3, 0, 1, 2, 3, 4, 5)\\
(0, 1, 2, 0, 1, 2, 0, 1, 2, 3, 4)&(0, 1, 2, 3, 0, 1, 2, 3, 4, 5)\\
(0, 1, 2, 1, 2, 0, 2, 0, 1, 3, 4)&(0, 1, 2, 3, 1, 0, 3, 2, 4, 5)\\
(0, 1, 2, 1, 2, 0, 2, 0, 1, 3, 4)&(0, 1, 2, 3, 2, 3, 0, 1, 4, 5)
\end{tabular}
\\[3mm]
\begin{tabular}{l}
$T(7,7)=11$:\\
(0, 0, 0, 0, 1, 1, 1, 1, 2, 3, 4)\\
(0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6)\\
(0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6)\\
(0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6)\\
(0, 1, 2, 3, 1, 2, 3, 0, 4, 5, 6)\\
(0, 1, 2, 3, 1, 2, 3, 0, 4, 5, 6)\\
(0, 1, 2, 3, 1, 2, 3, 0, 4, 5, 6)
\end{tabular}

\begin{thebibliography}{99}

\bibitem{Bush}
K.\ A.\ Bush,
Orthogonal arrays of index unity,
\emph{Ann.\ Math.\ Statistics} \textbf{23} (1952), 426--434.

\bibitem{Football}
H.\ H\"am\"al\"ainen, I.\ Honkala, S.\ Litsyn, and P.\ R.\ J.\ \"Osterg\aa rd,
Football pools---a game for mathe\-ma\-ticians,
\emph{Amer.\ Math.\ Monthly} \textbf{102} (1995), 579--588.

\bibitem{Tori}
P.\ R.\ J.\ \"Osterg\aa rd and T.\ Riihonen,
A covering problem for tori,
\emph{Ann.\ Comb.}\ \textbf{7} (2003), 357--363.

\bibitem{Riihonen}
T.\ Riihonen,
How to gamble 0 correct in football pools, Helsinki University of 
Technology, 2002.
Available at \href{http://users.tkk.fi/priihone/tuotokset.html}{\tt http://users.tkk.fi/priihone/tuotokset.html}.

\bibitem{Sloane}
N.\ J.\ A.\ Sloane,
The On-Line Encyclopedia of Integer Sequences.
Published electronically at \href{http://oeis.org/}{\tt http://oeis.org/}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05B40; Secondary 11H31, 52C17.

\noindent \emph{Keywords:} Minimal covering codes, football pool problem.

\bigskip
\hrule
\bigskip

\noindent Concerned with sequences
\seqnum{A004044} and
\seqnum{A086676}.

\bigskip
\hrule
\bigskip


\vspace*{+.1in}
\noindent
Received January 14 2011;
revised versions received February 19 2011; June 28 2011; September 5 2011. 
Published in {\it Journal of Integer Sequences}, October 16 2011.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}