Combinatoria: Garantizar obtener 10 de 13 correctos de la manera más eficiente posible (Stryktipset)

Question

Primero, un poco de contexto

"Stryktipset" es una forma popular de apuestas de fútbol en Suecia, pero estoy seguro de que existen juegos similares en muchos otros países. El concepto es simple: de una lista de trece juegos, el jugador necesita elegir al ganador correcto, o si el juego termina en empate. La notación para esto es 1 para la victoria del equipo local, X para un empate, y 2 para una victoria visitante.

El jugador compite contra la piscina de jugadores, donde porcentajes fijos del total del premio se dividen entre aquellos que aciertan 10, 11, 12 y 13 juegos correctamente.

Una forma común de jugar es a través de "garantías" y "semi-garantías", lo que significa que para cada juego, el jugador puede optar por jugar las tres alternativas, o al menos dos de ellas.

Así que, por ejemplo, jugar el juego 1 como 1X2, el juego 2 como X2 y el resto como "elección individual", produce 3*2*(1^11) combinaciones, es decir, 6 maneras de acertar los 13 juegos, o 6 "filas", y por lo tanto un costo de 6 veces el costo base. A esto se le llama un sistema M, o Matemático, mientras que simplemente elegir una opción por juego es un "individual".

Al grano

Ahora, un acertijo común es "¿cuál es la cantidad más baja de filas que garantiza al jugador 5 juegos correctos?" Muchos responden basándose en su intuición de "garantizar" cinco juegos y luego dejar los 8 restantes de manera arbitraria, resultando en 5^3 = 243 filas. Pero, si se juegan solo tres individuales que no se superponen, resulta ser suficiente para garantizar al menos 5 juegos correctos. Esto se puede entender fácilmente imaginando un individual con todos 1's, uno con todos X's y uno con todos 2's. Naturalmente, al menos uno de los signos debe aparecer al menos cinco veces.

Pero lo que me pregunto es esto:

¿Cuál es la cantidad más baja de filas que garantiza 10 respuestas correctas?

Answer 1

Este es un problema abierto. El número que desea es denotado $K_3(13, 3)$, y los límites conocidos actualmente son que $$612 \le K_3(13, 3) \le 1215.$$

---

Se puede establecer un límite inferior de $607$ a través de medios elementales, de la siguiente manera.

Considere una "fila" particular, que es una predicción sobre cada uno de los $13$ juegos. Para esta fila en particular, contemos el número de posibles resultados para los cuales esta fila tendría $10$ o más respuestas correctas. Un resultado que coincida con esta fila en exactamente $k$ lugares se puede determinar eligiendo las posiciones coincidentes de $\binom{13}{k}$ formas, y luego eligiendo uno de los otros dos resultados no coincidentes para cada uno de los restantes $13-k$ lugares. Por lo tanto, es $$\binom{13}{10}2^3 + \binom{13}{11}2^2 + \binom{13}{12}2^1 + \binom{13}{13}2^0 = 2627.$$

Dado que cada fila "cubre" (es buena para) solo $2627$ resultados, y hay $3^{13} = 1594323$ resultados posibles, necesitas al menos $\lceil 3^{13}/2627 \rceil = 607$ filas.

Por lo tanto, $607$ es un límite inferior. Si esto es realmente alcanzable depende de si se pueden elegir filas suficientemente no superpuestas (en el sentido de no "cubrir" demasiados resultados comunes).

Nótese que para el caso de "al menos $5$", este límite inferior es exacto: da $$\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$$ que de hecho es la respuesta al rompecabezas más simple.

---

En términos de teoría de codificación, se busca un código ternario (conjunto de palabras sobre un alfabeto de longitud $3$) tal que cada palabra del código esté dentro de una distancia de Hamming de $13 - 10 = 3$ (se permite tener hasta $3$ eventos incorrectos) de alguna palabra. En otras palabras, las esferas de Hamming de radio $3$ alrededor de tus palabras del código ("filas") cubren todo el espacio de palabras ternarias de $13$ letras. Esto se conoce como un código de cobertura. El argumento del límite inferior que di anteriormente es exactamente lo que se conoce como el límite de Hamming o límite de empaquetamiento de esferas.

El número que se busca es $K_3(13, 3)$ (el subíndice $3$ es el tamaño del alfabeto y denota palabras ternarias, y el segundo argumento $3 = 13 - 10$ es el radio de cobertura deseado). Según el sitio web "Tablas para Límites en Códigos de Cobertura", y en particular esta tabla (PDF), los límites conocidos sobre $K_3(13, 3)$ son:

• $612 \le K_3(13, 3)$: Lang, Quistor, Schneider (2006), Nuevos resultados sobre programación entera para códigos, Cong. Numer. 188 (2007), 97-107. [A través de una mejora del límite de empaquetamiento de esferas. El límite inferior $609$ se demostró en 1990.]
• $K_3(13, 3) \le 1215$: Pude rastrear esto hasta Heikki Hämäläinen, Seppo Rankinen (1987), Límites superiores para problemas de quinielas de fútbol y códigos de cobertura mixtos, J. Comb. Theory, Ser. A 56(1): 84-95 (1991)