El juego de progresión aritmética es un juego posicional en el que dos jugadores eligen números alternativamente, intentando ocupar una progresión aritmética completa de un tamaño determinado.
El juego está parametrizado por dos enteros n > k . El tablero de juego es el conjunto {1,..., n }. Los conjuntos ganadores son todas las progresiones aritméticas de longitud k . En una variante del juego Maker-Breaker , el primer jugador (Maker) gana al ocupar una progresión aritmética de longitud k ; de lo contrario, gana el segundo jugador (Breaker).
El juego también se denomina juego de van der Waerden , [1] llamado así por el teorema de Van der Waerden . Dice que, para cualquier k , existe algún entero W (2, k ) tal que, si los enteros {1, ..., W (2, k )} se dividen arbitrariamente en dos conjuntos, entonces al menos un conjunto contiene una progresión aritmética de longitud k . Esto significa que, si , entonces Maker tiene una estrategia ganadora.
Lamentablemente, esta afirmación no es constructiva: no muestra una estrategia específica para Maker. Además, el límite superior actual para W (2, k ) es extremadamente grande (los límites conocidos actualmente son: ).
Sea W *(2, k ) el entero más pequeño tal que Maker tenga una estrategia ganadora. Beck [1] demuestra que . En particular, si , entonces el juego es la victoria de Maker (aunque es mucho menor que el número que garantiza que no habrá empate).
