The football pool problem for 6 matches: A new upper bound obtained by simulated annealing (Q1117236)

The set \(V^ n_ 3\) of all n-tuples \(x=(x_ 1,x_ 2,...,x_ n)\) with \(x_ i\in \{0,1,2\}\) is considered. The problem mentioned in the title consists of determining \(\sigma_ n\), the minimal size of a subset W of \(V^ n_ 3\), such that for any element x in \(V^ n_ 3\) there is at least one element y in W at a Hamming distance d(x,y)\(\leq 1\). More popularly stated, \(\sigma_ n\) is the minimum number of forecasts in a foodball pool of n matches, such that at least one forecast has at leat n-1 correct results. In this paper it is shown that \(\sigma_ 6\leq 74\), which improves the previous best upper bound \((\sigma_ 6\leq 79)\). This solution has been obtained by a computer search using the recently developed simulated annealing method.