NEW UPPER-BOUNDS FOR THE FOOTBALL POOL PROBLEM FOR 11 AND 12 MATCHES

[摘要] We consider the problem of minimizing the number of words in a code with the property that all words in the space F3n are within Hamming distance 1 from some codeword. This problem is called the football pool problem, since the words in such a code can be used in a football pool to guarantee that at least one forecast has at least n - 1 correct results. In this note we show that for 11 and 12 matches, there are 9477 and 27702 words, respectively, having the aforementioned property. Simulated annealing has played an important role in the search for these words. (C) 1994 Academic Press, Inc.

[发布日期] 1994-08-01