The Inverse Football Pool Problem

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

                   brink@math.ku.dk

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 1950s 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.

1 Introduction

Consider the finite set Q = {0, …, q − 1}^{n} equipped with the Hamming distance

d(x, y) = |{i : x_{i} ≠ y_{i}}|

for x = (x_{1}, …, x_{n}) and y = (y_{1}, …, y_{n}) in Q. Let

ℬ(x_{0}, r) = {x ∈ Q : d(x, x_{0}) ≤ r}, 𝒮 (x_{0}, r) = {x ∈ Q : d(x, x_{0}) = r}

be the ball and sphere, respectively, with centre x_{0} and radius r.^{1}

1Note 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 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 [5]. See also [2] 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 ∏_{i=1}^{n} A_{i} where A_{i} ⊂ {0, …, 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 Östergård and Riihonen [3].

Definition 1. Let T (n, q) be the minimal number of spheres of radius n required to cover Q.

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 inverse football pool problem since it means asking for the minimal number of bets needed to guarantee that at least one is totally wrong.

The inverse football pool problem was first considered in the Finnish football pool magazine Veikkaaja in the 1950s.^{2} 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 Veikkaaja on the inverse football pool problem seem to have been unknown to the mathematical community until they were discovered by Östergård and Riihonen in 2002 and presented in [3] and [4]. All references to Veikkaaja here come from these two papers.

2 General bounds

First we state some easy or well-known bounds. If a sphere covering of {0, …, q − 1}^{n} is given, a covering of {0, …, 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. Veikkaaja no. 23, 1956, and [3, Theorem 3.3]. Hence

T (n, q) ≥ \frac{q}{q − 1} · T (n − 1, q).  (1)

2As was the ordinary football pool problem in the previous decade. Indeed, Veikkaaja holds a place of the first rank in the history of combinatorics. It was here that Juhani Virtakallio gave the 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.

In particular, it follows inductively from T (1, q) = 2 that T (n, q) ≥ n + 1. If n < q, the spheres with centres (0, …, 0), …, (n, …, n) cover Q. Thus

T (n, q) = n + 1 for n < q.  (2)

Taking direct product gives

T (n + n′, q) ≤ T (n, q) · T (n′, q).  (3)

Finally, an exceedingly elegant and ingenious construction for q = 3, described in Veikkaaja no. 15, 1960, and [3, Corollary 3.5], gives the bound

T (n + n′ − 2, 3) ≤ \frac{1}{3} · T (n, 3) · T (n′, 3)  (4)

(and sometimes a little more, cf. [3, Theorem 3.4]) which is considerably better than (3).

Definition 2. (a) We represent a covering of {0, …, q − 1}^{n} with m spheres 𝒮 (x_{1}, n), …, 𝒮 (x_{m}, n) by the n × m covering matrix A whose columns are the centres x_{1}, …, x_{m}.

(b) Two covering matrices of the same size (and the sphere coverings they represent) are called equivalent if one can be transformed into the other by permuting rows and columns and by renaming the symbols in any given row.^{3}

(c) We call a covering matrix 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.).

The definition of equivalence is standard. If n < q, for example, the matrix consisting of n identical rows (0, 1, …, n) is the unique canonical n×(n+1) covering matrix, cf. (2). Note that there is a 1–1 correspondence between equivalence classes of coverings and canonical covering matrices. The following lemma is a generalization of (1).

Lemma 3. Suppose A is an n × m covering matrix. Let there be given b_{i} ∈ {0, …, q − 1} for all i in some proper subset I ⊂ {1, …, n}. Then the number of columns (a_{1}, …, a_{n})^{t} of A with a_{i} ≠ b_{i} for all i ∈ I is at least T (n − |I|, q).

Proof. For each i ∈ I, delete all columns (a_{1}, …, a_{n})^{t} of A having a_{i} = b_{i}. Then delete row i for each i ∈ I. The resulting matrix A′ is a covering matrix for {0, …, q − 1}^{n−|I|} and hence has at least T (n − |I|, q) columns.

3 Main results

Theorem 4. 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.

3By “renaming the symbols,” we mean that given any row a = (a_{1}, …, a_{m}) and given any permutation σ of 0, …, q − 1, we may replace a by (σ(a_{1}), …, σ(a_{m})).

Proof. The lower bounds T (7, 3) ≥ 27 and T (8, 3) ≥ 41 follow from (1) and (2). The upper bounds T (7, 3) ≤ 29 and T (8, 3) ≤ 44 are known, cf. [3] and the discussion below. After having shown T (7, 3) = 29, it will follow that T (8, 3) = 44 by (1). 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 × m covering matrix. Then, by Definition 2 and Lemma 3, the following two conditions hold for each i = 1, …, n:

(I) The i × m submatrix A_{i} consisting of the first i rows of A is canonical.

(II) Given b_{1}, …, b_{i} ∈ {0, …, q − 1}, there are at least T (n − i, q) columns (a_{1}, …, a_{i})^{t} of A_{i} satisfying a_{j} ≠ b_{j} for all j = 1, …, i.

In order to find all canonical n × m matrices, we proceed as follows: First find the set R_{1} of all rows r_{1} such that the 1×m matrix A_{1} consisting only of r_{1} satisfies (I) and (II). Then, for each r_{1} ∈ R_{1}, find the set R_{2}(r_{1}) of all rows r_{2} such that the 2×m matrix A_{2} consisting of r_{1} and r_{2} satisfies (I) and (II). Next, for each r_{1} ∈ R_{1} and r_{2} ∈ 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}, …, r_{n−1}) is obtained in this way, each row r_{n} in that set gives rise to a canonical n × m covering matrix, namely the matrix consisting of r_{1}, …, 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 × 27 covering matrix A. First we find R_{1}. By condition (I), every r_{1} ∈ R_{1} is of the form

r_{1} = (\overbrace{0, …, 0}^{l_{0} times}, \overbrace{1, …, 1}^{l_{1} times}, \overbrace{2, …, 2}^{l_{2} times})

with

l_{0} + l_{1} + l_{2} = 27.  (5)

By specifying b_{1} ∈ {0, 1, 2} and using T (6, 3) = 18, condition (II) gives the following three linear inequalities:

l_{1} + l_{2} ≥ 18, l_{0} + l_{2} ≥ 18, l_{0} + l_{1} ≥ 18.  (6)

It follows immediate from (5) and (6) that l_{0} = l_{1} = l_{2} = 9 and hence

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

Then we find R_{2}(r_{1}). By condition (I), every r_{2} ∈ R_{2}(r_{1}) is of the form

r_{2} = (\overbrace{0, …, 0}^{l_{0} times}, \overbrace{1, …, 1}^{l_{1} times}, \overbrace{2, …, 2}^{l_{2} times}, \overbrace{0, …, 0}^{l′_{0} times}, \overbrace{1, …, 1}^{l′_{1} times}, \overbrace{2, …, 2}^{l′_{2} times}, \overbrace{0, …, 0}^{l′′_{0} times}, \overbrace{1, …, 1}^{l′′_{1} times}, \overbrace{2, …, 2}^{l′′_{2} times})

with

l_{0} + l_{1} + l_{2} = l′_{0} + l′_{1} + l′_{2} = l′′_{0} + l′′_{1} + l′′_{2} = 9.  (7)

By specifying b_{1}, b_{2} ∈ {0, 1, 2} and using T (5, 3) = 12, condition (II) now gives the following nine linear inequalities:

\begin{matrix}l′_{1} + l′_{2} + l′′_{1} + l′′_{2} ≥ 12, & l′_{0} + l′_{2} + l′′_{0} + l′′_{2} ≥ 12, & l′_{0} + l′_{1} + l′′_{0} + l′′_{1} ≥ 12, \\ l_{1} + l_{2} + l′′_{1} + l′′_{2} ≥ 12, & l_{0} + l_{2} + l′′_{0} + l′′_{2} ≥ 12, & l_{0} + l_{1} + l′′_{0} + l′′_{1} ≥ 12, \\ l_{1} + l_{2} + l′_{1} + l′_{2} ≥ 12, & l_{0} + l_{2} + l′_{0} + l′_{2} ≥ 12, & l_{0} + l_{1} + l′_{0} + l′_{1} ≥ 12. \end{matrix}  (8)

It is not difficult to show that (7) and (8) imply l_{0} = l_{1} = l_{2} = l′_{0} = l′_{1} = l′_{2} = l′′_{0} = l′′_{1} = l′′_{2} = 3 and consequently

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

Similarly, in order to determine the elements r_{3} ∈ 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

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

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

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

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 × 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} ∈ {0, 1, 2} occurs exactly λ = 1 times in the 3 × 27 matrix A_{3}. By symmetry, the same holds for any 3 × 27 submatrix of A formed by t = 3 arbitrary rows. This means that the 7 × 27 matrix A is an orthogonal array with q = 3 levels, index λ = 1, and strength t = 3. But by a result of Bush [1], 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 × 28 covering matrix become too large to do the demonstration by hand. For example, R_{1} consists of the two rows

\begin{matrix}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{matrix}

and R_{2}(r_{1}) consists of

\begin{matrix}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{matrix}

while R_{2}(r′_{1}) consists of

\begin{matrix}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{matrix}

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.

\begin{matrix}n & T (n, 3) \\ 1 & 2 \\ 2 & 3 \\ 3 & 5 \\ 4 & 8 \\ 5 & 12 \\ 6 & 18 \end{matrix}  \begin{matrix}7 & 29 \\ 8 & 44 \\ 9 & 66 − 68 \\ 10 & 99 − 104 \\ 11 & 149 − 172 \\ 12 & 224 − 264 \\ 13 & 336 − 408 \end{matrix}

Table 1: Old and new results on T (n, 3).

Table 1 collects old and new results on T (n, 3). All values for n ≤ 6 as well as the bounds T (7, 3) ≤ 29 and T (8, 3) ≤ 44 go back to Veikkaaja.^{4} All lower bounds for n ≥ 9 come from T (7, 3) = 29 combined with (1). Note that T (7, 3) = 29 is the first counter-example to the natural conjecture T (n, 3) = ⌈\frac{3}{2} · T (n − 1, 3)⌉. The upper bounds for n = 9, 10 were found in [3] using so-called tabu search. The upper bounds for n = 11, 12, 13 follow from the upper bounds for smaller n using (4). A covering proving T (12, 3) ≤ 264 appears explicitly in Veikkaaja no. 52, 1960. As related in [4], a writer in fact claims in Veikkaaja no. 15, 1960, to be in possession of a covering proving T (12, 3) ≤ 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 [3].

Theorem 5. Modulo equivalence, there is only one minimal covering of {0, 1, 2}^{n} with spheres of radius n for each n = 1, …, 7.

Proof. The statement can be proved by hand for n ≤ 6. We exemplify this by sketching the case n = 6. By the same arguments as in the proof of Theorem 4, the first three rows of a canonical 6 × 18 covering matrix A must be

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

Now there are three candidates for row 4:

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

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 4 finds only one canonical matrix (namely the one given at the end of this paper).

4It remains somewhat of a mystery, though, how the coverings proving these results were found.

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

Theorem 6. We have the following values of T (n, q), i.e., the minimal number of spheres of radius n needed to cover {0, …, q − 1}^{n}:

\begin{matrix}n & T (n, 4) & T (n, 5) & T (n, 6) & T (n, 7) \\ 1 & 2 & 2 & 2 & 2 \\ 2 & 3 & 3 & 3 & 3 \\ 3 & 4 & 4 & 4 & 4 \\ 4 & 7 & 5 & 5 & 5 \\ 5 & 10 & 8 & 6 & 6 \\ 6 & 14 − 16 & 11 & 10 & 7 \\ 7 & 19 − 28 & 14 − 20 & 12 − 18 & 11 \end{matrix}

The values typed in boldface are the non-trivial ones, i.e., the ones not following from equation (2).

Proof. The theorem is shown by a computer search following the same principles as in the proof of Theorem 4. 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 × 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 (1) and (3).

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

4 Appendix: Lexicographically minimal covering matrices

Finally, we present for each non-trivial value of T (n, q) given in Theorem 6 as well as for q = 3 and n = 3, …, 7 the unique lexicographically minimal n × T (n, q) covering matrix.

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)

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)

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)

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)

\begin{matrix}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{matrix}

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)

References

[1] K. A. Bush, Orthogonal arrays of index unity, Ann. Math. Statistics 23 (1952), 426–434.

[2] H. Hämäläinen, I. Honkala, S. Litsyn, and P. R. J. Östergård, Football pools—a game for mathematicians, Amer. Math. Monthly 102 (1995), 579–588.

[3] P. R. J. Östergård and T. Riihonen, A covering problem for tori, Ann. Comb. 7 (2003), 357–363.

[4] T. Riihonen, How to gamble 0 correct in football pools, Helsinki University of Technol-

    ogy, 2002. Available at http://users.tkk.fi/priihone/tuotokset.html.

[5] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electroni-

    cally at http://oeis.org/.

2010 Mathematics Subject Classification: Primary 05B40; Secondary 11H31, 52C17. Keywords: Minimal covering codes, football pool problem.

Concerned with sequences \underline{A004044} and \underline{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.