A combinatorial proof for the football pool problem for six matches (Q1924246)

The problem of finding a ternary code \(C\) of length \(n\) that has covering radius 1 and is of minimal cardinality \(\sigma_n\) is also known as the football pool problem (for \(n\) matches). For \(n\leq 5\) the value of \(\sigma_n\) is known. The best upper bound presently known in the case \(n=6\) is \(\sigma_6\leq 73\). This result was found using simulated annealing [{P. J. M. van Laarhoven}, \textit{E. H. L. Aarts}, \textit{J. H. van Lint} and \textit{L. T. Wille}, New upper bounds for the football pool problem for 6, 7 and 8 matches, J. Comb. Theory, Ser. A 52, No. 2, 304-312 (1989; Zbl 0724.90085)]. The code in question has no structure. Since many known upper bounds for \(n>6\) were found using a method described by \textit{A. Blokhuis} and \textit{C. W. H. Lam} [More coverings by rook domains, J. Comb. Theory, Ser. A 36, 240-244 (1984; Zbl 0533.05020)] which yields codes with cardinality divisible by some power of 3, it has been conjectured that \(\sigma_6 =8 \cdot 3^2 = 72\) but no code realizing this has been found yet. In the present paper a covering code of length 6 and cardinality 73 is presented by explicitly giving all codewords in a table. The code has sufficiently many symmetries to prove (in one page) that it indeed has covering radius 1. The author suggests that the structure present in this code may be evidence that in fact \(\sigma_6=73\).