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 wi th the property that all words in the space F3n are within Hamming dis tance 1 from some codeword. This problem is called the football pool p roblem, 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 res ults. In this note we show that for 11 and 12 matches, there are 9477 and 27702 words, respectively, having the aforementioned property. Sim ulated annealing has played an important role in the search for these words. (C) 1994 Academic Press, Inc.