Additive Subtraction Games

Este artículo determina la estructura completa de los valores nim en juegos de sustracción aditivos del régimen cuadrático primitivo, proporcionando una demostración rigurosa de una fórmula cerrada conocida desde 1982 y estableciendo que cada secuencia de valores nim reside en un desplazamiento lineal de las posiciones P clásicas.

Lo esencial

¡Claro que sí! Imagina que este artículo es como un mapa del tesoro para un juego de estrategia muy específico, donde el "tesoro" es entender exactamente cómo ganar en cada situación posible.

Aquí tienes la explicación de la investigación de Larsson y Manabe, contada como si fuera una historia de detectives matemáticos.

---

🎮 El Juego: "Restar y Ganar"

Imagina un juego para dos personas con una pila de fichas (o monedas).

• Las reglas: Cada jugador, por turno, debe quitar un número específico de fichas. Pero no puede quitar cualquier número; solo puede quitar cantidades que estén en una "lista de permisos" (llamada $S$).
• El objetivo: El último jugador en poder hacer un movimiento gana. Si te toca y no puedes quitar nada (porque la pila es muy pequeña para los números permitidos), ¡pierdes!

En este juego, los matemáticos usan un sistema de "valores mágicos" (llamados nim-values) para saber si una posición es ganadora o perdedora.

• Valor 0: Es una trampa. Si estás aquí, estás perdido (a menos que tu oponente cometa un error).
• Valor 1, 2, 3: Son escalones hacia la victoria.

🧩 El Misterio: La Regla Cuadrática "Primitiva"

Los autores se enfocaron en un caso especial donde la "lista de permisos" tiene tres números: $a$, $b$ y $a+b$.

• Hay una condición especial: el número $b$ es un poco más grande que $a$, pero no el doble de grande. Imagina que $a$ es un paso pequeño y $b$ es un paso medio.
• Cuando estos números interactúan de esta manera, el juego se vuelve complejo (como un laberinto que crece en dos direcciones, por eso lo llaman "cuadrático").

Antes de este artículo, los matemáticos tenían una fórmula secreta (una receta escrita en papel) que parecía decirte exactamente dónde estaban las trampas (los valores 0). Pero nadie había demostrado que la receta funcionara siempre. Era como tener un mapa dibujado a mano que todos creían que era correcto, pero sin la prueba de que el tesoro realmente estaba ahí.

🔍 La Misión: Demostrar la Receta

El objetivo de Larsson y Manabe fue: "¡Vamos a probar que esta fórmula funciona y a explicar por qué!"

1. La Fórmula Mágica (La Receta)

La fórmula es un poco rara a primera vista, pero imagina que es como una máquina expendedora. Metes un número $n$ (el turno o la posición) y la máquina te devuelve un número especial $w_n$.

• Si tu posición en el juego coincide con uno de estos números mágicos, estás en una trampa (Valor 0).
• La fórmula usa "pisos" (funciones matemáticas que redondean hacia abajo) para calcular estos números. Es como decir: "Cada vez que llegues a un múltiplo de $a$ o de $\delta$, salta un escalón extra".

2. El Primer Desafío: "No Chocar" (Anti-colisión)

Para que una lista sea una lista de trampas perfectas, no puede haber dos trampas que estén a una distancia exacta de un movimiento permitido.

• Analogía: Imagina que las trampas son pozos en el suelo. Si puedes saltar desde un pozo A hasta un pozo B usando solo un salto permitido, entonces no son trampas seguras (porque podrías saltar de uno al otro).
• Los autores demostraron que, gracias a la forma especial de la fórmula, nunca puedes saltar de un pozo a otro usando las reglas del juego. ¡Los pozos están perfectamente aislados!

3. El Segundo Desafío: "Llegar a todas partes" (Alcance)

No basta con que las trampas no se toquen; también debes poder llegar a ellas desde cualquier otro lugar.

• Los autores descubrieron que el juego se divide en cuatro zonas claras, como un mapa de colores:
  • Zona Roja (Valor 0): Las trampas originales ($W_0$).
  • Zona Azul (Valor 1): Posiciones que están exactamente un paso $a$ más allá de una trampa.
  • Zona Verde (Valor 2): Posiciones que están un paso $b$ antes de una trampa.
  • Zona Amarilla (Valor 3): Un grupo especial que aparece cuando restas un número $\delta$ de las trampas, pero que no cae en las otras zonas.

¡La gran noticia es que estas cuatro zonas cubren todos los números posibles! No hay huecos. Si juegas, siempre caerás en una de estas cuatro categorías.

🌉 El Secreto Oculto: Las "Ventanas de Colisión"

La parte más difícil de la prueba (y la más creativa) fue contar cuántas veces ocurren ciertos "choques" matemáticos.

• El problema: A veces, al restar un número de una trampa, caes en otra trampa. Esto es un "choque".
• La analogía: Imagina que tienes una cinta métrica con marcas especiales (las trampas). Si tomas la cinta y la desplazas un poco hacia la izquierda, ¿cuántas marcas se alinean perfectamente con las marcas originales?
• Los autores descubrieron que estos choques no son aleatorios. Siguen un patrón geométrico muy ordenado basado en los residuos (el resto de dividir números).
• Dividieron el problema en tres regiones (izquierda, centro, derecha) y contaron cuántas "ventanas" de choques había en cada una. Fue como contar cuántas piezas de un rompecabezas encajan en un espacio específico.
• Al final, la suma de todas estas piezas coincidió exactamente con el número de espacios que faltaban para llenar el mapa. ¡La prueba estaba completa!

🏆 Conclusión: El Mapa está Completo

En resumen, este artículo logró:

1. Probar una fórmula antigua que nadie había validado.
2. Mostrar que el juego se divide perfectamente en cuatro tipos de posiciones (0, 1, 2 y 3).
3. Explicar la complejidad matemática detrás de por qué ocurren estos patrones, usando herramientas de teoría de números (como contar residuos y espacios).

¿Por qué importa?
Porque demuestra que incluso en juegos que parecen caóticos y complejos, existe un orden matemático profundo y predecible. Los autores nos dieron las llaves para descifrar este orden, transformando un misterio en una certeza absoluta.

¡Y eso es todo! Han resuelto el enigma de cómo ganar (o perder) en este juego específico para siempre. 🎉

Resumen técnico

Aquí tienes un resumen técnico detallado del artículo "Additive Subtraction Games" de Urban Larsson y Hikaru Manabe, presentado en español.

1. Planteamiento del Problema

El artículo aborda el estudio de los juegos de sustracción aditiva, una clase de juegos combinatorios de dos jugadores jugados con montones de fichas. En estos juegos, los jugadores eliminan alternadamente un número $s$ de fichas, donde $s$ pertenece a un conjunto fijo $S$ de enteros positivos. El jugador que no puede realizar un movimiento (porque todas las sustracciones llevarían a un número negativo) pierde.

El foco específico del trabajo es el régimen cuadrático primitivo para el conjunto de sustracción $S = \{a, b, a+b\}$, donde:

• $b = a + \delta$
• $a < \delta < 2a$
• $\text{mcd}(a, \delta) = 1$

El objetivo es determinar la estructura completa de los valores de nim (o nimbers) para todas las posiciones del juego. Históricamente, este problema apareció en el libro Winning Ways (Berlekamp et al., 1982), donde se propuso una fórmula cerrada para las posiciones de pérdida (P-posiciones, valor de nim 0) basada en expresiones de tipo Beatty con modulos racionales. Sin embargo, hasta la fecha de esta publicación, no existía una demostración completa de dicha fórmula en la literatura, a pesar de que trabajos recientes (Miklós y Post, 2024) habían establecido la periodicidad de los resultados sin utilizar la fórmula explícita.

2. Metodología

Los autores emplean una combinación de teoría de juegos combinatorios y teoría de números para resolver el problema:

1. Definición de Posiciones Candidatas: Se define un conjunto candidato de P-posiciones ($W_0$) mediante la fórmula cerrada propuesta:
   $$w_n = n + a \left\lfloor \frac{n}{a} \right\rfloor + b \left\lfloor \frac{n}{\delta} \right\rfloor$$
   Donde $n \in \mathbb{N}_0$. Esta es una "expresión de paréntesis" (bracket expression) de tres términos.

2. Verificación de la Regla Mex: Para probar que $W_0$ son realmente las posiciones de valor 0, y para clasificar los valores de nim 1, 2 y 3, se utiliza inducción fuerte sobre el tamaño de la posición. Se deben verificar dos condiciones para cada conjunto de valores de nim:

   • Anti-colisión: Ningún movimiento permitido conecta dos posiciones dentro del mismo conjunto de valores de nim.
   • Alcanzabilidad: Desde cualquier posición en un conjunto de valor $k$, existe al menos un movimiento hacia un conjunto de valor $j < k$ (específicamente hacia 0, 1, 2, etc., según corresponda).

3. Análisis Estructural de Brechas (Gaps): Se estudia la secuencia de diferencias entre posiciones consecutivas en $W_0$ ($g_n = w_{n+1} - w_n$). Se demuestra que esta secuencia es periódica y solo toma cuatro valores posibles: $\{1, a+1, b+1, b+a+1\}$. La estructura de estas brechas depende de las clases residuales de $n$ módulo $a$ y $\delta$.

4. Conteo de Colisiones ($\delta$-Collisions): El núcleo del desafío técnico reside en analizar la intersección entre el conjunto $W_0$ y su traslación por $\delta$ ($W_0 - \delta$). Los autores definen un "marco de colisión" (collision window) como una secuencia de brechas consecutivas que suman exactamente $\delta$. Utilizan un análisis detallado de las clases residuales para contar cuántas veces ocurren estas colisiones en un periodo.

3. Contribuciones Clave y Resultados Principales

El resultado central del artículo es el Teorema 1, que proporciona una partición completa y explícita de los números naturales en cuatro conjuntos disjuntos, correspondientes a los valores de nim 0, 1, 2 y 3.

Definición de los Conjuntos:

• Valor 0 (P-posiciones): $W_0 = \{w_n : n \ge 0\}$
• Valor 1: $W_1 = W_0 + a$
• Valor 2: $W_2 = W_0 - b$
• Valor 3: $W_3 = (W_0 - \delta) \setminus W_0$

Resultados Específicos:

1. Prueba de la Fórmula Cerrada: Se demuestra rigurosamente que la fórmula propuesta en Winning Ways para las P-posiciones es correcta bajo las condiciones del régimen cuadrático primitivo.
2. Estructura de los Valores de Nim: Se establece que los valores de nim no son arbitrarios, sino que siguen una estructura de traslaciones afines del conjunto base $W_0$.
   • Los valores 1 y 2 son traslaciones directas.
   • El valor 3 es una "diferencia simétrica" entre una traslación y el conjunto original.
3. Periodicidad: Se calculan explícitamente los periodos:
   • Periodo de índice: $a\delta$.
   • Periodo de montón (heap-period): $(3\delta + a)a$.
4. Conteo de Colisiones (Teorema 7): Se demuestra que el número de elementos en la intersección $(W_0 - \delta) \cap W_0$ dentro de un periodo de montón es exactamente $a(\delta - a)$. Este conteo es crucial para probar que la unión de los cuatro conjuntos cubre todos los números naturales sin superposición.
5. Densidad: Se calculan las densidades asintóticas de cada clase de valor de nim, mostrando que no siguen la familia geométrica de las conjeturas de Fraenkel para secuencias de Beatty puras, sino una estructura más compleja derivada de la expresión de paréntesis.

4. Significado e Impacto

• Resolución de un Problema Abierto: El artículo cierra una brecha de más de 40 años al proporcionar la primera prueba completa de la fórmula de las P-posiciones para este caso específico, que había sido solo conjeturada.
• Complejidad Cuadrática: El régimen estudiado ($a < \delta < 2a$) captura la fuente fundamental de la complejidad cuadrática en los juegos de sustracción aditiva. Fuera de este régimen, el problema se reduce a complejidad lineal o mantiene la complejidad cuadrática de manera trivial.
• Nuevas Herramientas Matemáticas: El método de "ventanas de colisión" y el análisis de la distribución de residuos en tres regiones (restringida a la izquierda, no restringida, restringida a la derecha) ofrece una nueva herramienta para estudiar expresiones de paréntesis con términos fijos y sus traslaciones.
• Conexión con Teoría de Números: El trabajo vincula profundamente la teoría de juegos combinatorios con problemas de partición de enteros y secuencias de tipo Beatty, sugiriendo que las estructuras de los juegos de sustracción pueden revelar propiedades ocultas en secuencias definidas por funciones de piso racionales.

En resumen, Larsson y Manabe no solo resuelven un problema clásico de la teoría de juegos, sino que establecen un marco metodológico robusto para analizar la estructura aritmética de los valores de nim en juegos con reglas de sustracción aditiva complejas.