A combinatorial proof for the football pool problem for six matches
type: Item
instance of: scholarly article
title: A combinatorial proof for the football pool problem for six matches
zbMATH Open document ID: 0863.05023
published in: Journal of Combinatorial Theory. Series A
publication date: 1996-11-24T00:00:00Z
review text: 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\).
reviewed by: Jack van Lint
Mathematics Subject Classification ID: 05B40
Mathematics Subject Classification ID: 94B25
zbMATH DE Number: 935000
zbMATH Keywords: ternary code
zbMATH Keywords: covering radius
zbMATH Keywords: matches
zbMATH Keywords: football pool problem
zbMATH Keywords: covering code
author: Patric R. J. Östergård
MaRDI profile type: Publication
full work available at URL: jcta.1996.0097
OpenAlex ID: W2010061866
DOI: 10.1006/JCTA.1996.0097
Recommended article: An improved upper bound for the football pool problem for nine matches
Recommended article: Q3831025
Recommended article: A new lower bound for the football pool problem for six matches
Recommended article: Ternary covering codes derived from BCH codes
Recommended article: Graph domination, tabu search and the football pool problem
Recommended article: Q4393247
Recommended article: A new table of binary/ternary mixed covering codes
Recommended article: Improving bounds on the football pool problem by integer programming and high-throughput computing
Recommended article: Some new lower bounds for ternary covering codes
Recommended article: Binary and ternary codes of covering radius one: some new lower bounds
description: scientific article; zbMATH DE number 935000