Combinatorics: Guarantee getting 10 out of 13 right as efficiently as possible (Stryktipset)

Question

First, a little background

"Stryktipset" is a popular form of football (soccer) gambling in Sweden, but I'm sure similar games exist in many other countries. The concept is simple: out of a list of thirteen games, the player needs to pick the correct winner, or whether the game ends in a draw. The notation for this is 1 for home team win, X for a draw, and 2 for an away win.

The player competes against the player pool, where set percentages of the total prize pool gets divided among those who get 10, 11, 12 and 13 corretly picked games.

A common way to play is through "guarantees" and "semi-guarantees", meaning that for every game, the player can choose to play all three alternatives, or at least two of them.

So for instance, playing game 1 as 1X2, game 2 as X2 and the rest as "single choice", yields 3*2*(1^11) combinations, for 6 ways to get all 13 right, or 6 "rows", and thus a cost of 6 times the base cost. This is called an M, or Mathematical, system, whereas just picking one option per game is a "single".

To the point

Now, a common puzzle is "what is the lowest amount of rows that guarantees the player 5 correct games?" Many responders go by their gut feel of "guaranteeing" five games and then letting the remaining 8 be arbitrary, for 5^3 = 243 rows. But, if one plays just three singles that don't overlap, this turns out to be enough to guarantee at least 5 correct games. This can easily be seen by imagining one single with all 1's, one with all X's and one with all 2's. Naturally, at least one of the signs needs to show up at least five times.

But what I wonder is this:

What is the lowest amount of rows that guarantees 10 correct answers?

Answer 1

This is an open problem. The number you want is denoted $K_3(13, 3)$, and the currently known bounds are that $$612 \le K_3(13, 3) \le 1215.$$

---

A lower bound of $607$ can be established through elementary means, as follows.

Consider a particular "row", which is a prediction about each of the $13$ games. For this particular row, let us count the number of possible outcomes for which this row would have $10$ or more correct answers. An outcome that matches this row in exactly $k$ places can be determined by choosing the matching positions in $\binom{13}{k}$ ways, and then picking one of the two other non-matching results for each of the remaining $13-k$ places. Thus, it is $$\binom{13}{10}2^3 + \binom{13}{11}2^2 + \binom{13}{12}2^1 + \binom{13}{13}2^0 = 2627.$$

As each row "covers" (is good for) only $2627$ outcomes, and there are $3^{13} = 1594323$ possible outcomes, you need at least $\lceil 3^{13}/2627 \rceil = 607$ rows.

Thus $607$ is a lower bound. Whether this is actually achievable depends on whether you can pick sufficiently non-overlapping (in the sense of not "covering" too many common outcomes) rows.

Note by the way that for the "at least $5$" case, this lower bound is exact: it gives $$\left\lceil \frac{3^{13}}{\sum_{k=5}^{13} \binom{13}{k}2^{n-k}} \right\rceil = \left\lceil \frac{1594323}{714195} \right\rceil = 3$$ which is indeed the answer to the simpler puzzle.

---

In terms of coding theory, you want a ternary code (set of words over an alphabet of length $3$) such that every codeword is within Hamming distance $13 - 10 = 3$ (you are allowed to get up to $3$ events wrong) of some word. In other words the Hamming spheres of radius $3$ around your codewords ("rows") cover the entire space of ternary $13$-letter words. This is known as a covering code. The lower-bound argument I gave above is exactly what is known as the Hamming bound or sphere-packing bound.

The number you want is $K_3(13, 3)$ (the subscript $3$ is the size of the alphabet and denotes ternary words, and the second argument $3 = 13 - 10$ is the desired covering radius). According to the website "Tables for Bounds on Covering Codes", and in particular this table (PDF), the known bounds on $K_3(13, 3)$ are:

• $612 \le K_3(13, 3)$: Lang, Quistor, Schneider (2006), New Results on Integer Programming for Codes, Cong. Numer. 188 (2007), 97-107. [Via an improvement of the sphere-packing bound. The lower bound $609$ was proved in 1990.]
• $K_3(13, 3) \le 1215$: I was able to trace this back as far as Heikki Hämäläinen, Seppo Rankinen (1987), Upper bounds for football pool problems and mixed covering codes, J. Comb. Theory, Ser. A 56(1): 84-95 (1991)