Improve the bounds on the football-pool number K_3(6): ternary covering code of length 6, radius 1
Statement
Let $K_3(n)=K_3(n,1)$ be the minimum number of codewords in a ternary code $C \subseteq \{0,1,2\}^n$ of covering radius 1 - i.e. such that every word in $\{0,1,2\}^n$ is within Hamming distance 1 of some codeword. This is the 'football pool problem' for $n$ matches. Exact values are known for small $n$ (e.g. $K_3(3)=5$, $K_3(4)=9$). For $n=6$ the exact value is open: the best known bounds are $65 \le K_3(6) \le 73$. Exhibit a ternary covering code of length 6, radius 1, with at most 72 codewords (improving the upper bound), or prove $K_3(6) \ge 66$ (improving the lower bound).
Acceptance. FULLY RESOLVES (upper bound): an explicit list of $\le 72$ codewords in $\{0,1,2\}^6$ such that every one of the 729 words of $\{0,1,2\}^6$ is at Hamming distance $\le 1$ from a listed codeword - verified exhaustively over all 729 words. FULLY RESOLVES (lower bound): a machine-checkable proof (e.g. an ILP infeasibility / LP-bound certificate) that no radius-1 covering code of size $\le 65$ exists, i.e. $K_3(6) \ge 66$. PARTIAL: a code matching the current record (73), or any verified bound improvement. Provide the codeword list and a verifier (or the certificate).
Background
The football pool problem asks for the fewest betting tickets guaranteeing at most one wrong prediction on $n$ ternary-outcome matches. $K_3(6)$ has resisted exact determination for decades. The best known upper bound, a covering code of 73 words, is due to Wille (1987, tabu search); the best published lower bound 65 is from Linderoth, Margot & Thain, 'Improving Bounds on the Football Pool Problem via Symmetry Reduction and High-Throughput Computing' (2007). A ternary covering code is trivially verifiable: a length-6 radius-1 code of size $m$ covers $\{0,1,2\}^6$ (only $3^6=729$ words) iff every word is at distance $\le 1$ from some codeword, checkable in well under a second. Improving the upper bound is a pure search/optimization task (tabu/ILP/simulated annealing over codeword sets). Source: Linderoth-Margot-Thain (2007); Keri's tables of covering codes.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Linderoth, Margot & Thain, Improving Bounds on the Football Pool Problem (2007) | link |
| REF-02 | Covering code (football pool problem, K_3(n,1) bounds) | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.