On an Erdős-Szekeres Game

Este artículo analiza un juego de permutaciones de dos jugadores inspirado en el Teorema de Erdős-Szekeres, determinando al ganador y proporcionando una estrategia ganadora cuando $a \geq b$ y $b \in \{2,3,4,5\}$.

Lo esencial

¡Hola! Imagina que este artículo es como un manual de estrategia para un juego de mesa muy inteligente, pero en lugar de usar fichas de madera o cartas, usamos números y patrones.

Aquí tienes la explicación de la investigación de Lara Pudwell, traducida a un lenguaje sencillo y con algunas analogías divertidas:

🎲 El Juego: "La Carrera hacia el Desastre"

Imagina que dos amigos, Jugador 1 y Jugador 2, están construyendo una fila de números, uno por turno.

• El Jugador 1 pone un número.
• El Jugador 2 pone otro número después del primero.
• Luego el Jugador 1 pone otro, y así sucesivamente.

La Regla de Oro: El juego termina (y alguien pierde) en el momento en que se forma una de dos cosas:

1. Una fila de números que suben (como 2, 5, 8, 10) de cierta longitud (digamos, 4 números).
2. Una fila de números que bajan (como 10, 7, 3, 1) de cierta longitud (digamos, 3 números).

El objetivo: En esta versión del juego (llamada misère), el primero que completa una de esas filas pierde. ¡Es como jugar a "no seas el que enciende la mecha de la dinamita"!

🧩 El Problema Matemático (El Teorema de Erdős-Szekeres)

Hace mucho tiempo, unos matemáticos descubrieron una regla aburrida pero poderosa: "Si haces la fila lo suficientemente larga, ¡es imposible evitar que aparezca una subida o una bajada!".

El artículo pregunta: ¿Quién gana si ambos jugadores juegan perfectamente? ¿Puede el Jugador 1 forzar al Jugador 2 a ser el que complete la fila y pierda?

🗺️ La Gran Innovación: El Mapa de "Celda Eliminada"

Aquí es donde la autora hace algo genial. En lugar de pensar en números (que es confuso), ella convierte el juego en un tablero de cuadrícula (como un mapa de tesoro o un juego de Chomp).

• Imagina un tablero rectangular.
• Cada vez que un jugador pone un número, pinta una casilla en el tablero.
• Hay una regla mágica: Si pintas una casilla, todas las casillas que están arriba y a la izquierda de ella también se consideran "pintadas" automáticamente.
• El juego termina cuando alguien pinta la esquina inferior derecha. ¡Esa persona pierde porque significa que el tablero está lleno y el siguiente movimiento obligará a crear la fila prohibida!

La analogía: Es como si estuvieras construyendo un muro de ladrillos. Cada vez que pones un ladrillo, el muro crece hacia arriba y hacia la izquierda. El objetivo es no poner el ladrillo que complete el muro hasta el techo, porque eso le daría la victoria al otro.

🏆 Las Estrategias Ganadoras

La autora descubrió cómo ganar este juego para diferentes tamaños de tableros (cuando la longitud de la fila que baja es 2, 3, 4 o 5).

1. Si la fila que baja es muy corta (2 números): Es como una carrera de velocidad. El ganador depende simplemente de si el número total de casillas es par o impar. ¡Es un juego de suerte si no sabes contar!
2. Si la fila que baja es mediana (3, 4 o 5 números): Aquí entra la magia. La autora dice: "¡El Jugador 1 siempre puede ganar!" (siempre que la fila que sube sea larga).
   • ¿Cómo? El Jugador 1 sigue un "baile" muy específico. Si el Jugador 2 pinta una casilla en la fila de arriba, el Jugador 1 pinta una en la de abajo. Si el Jugador 2 pinta a la derecha, el Jugador 1 pinta a la izquierda.
   • Es como si el Jugador 1 tuviera un espejo mágico que refleja los movimientos del rival para mantener el tablero en un estado "seguro", obligando al Jugador 2 a dar el paso fatal.

🤖 El Secreto: Computadoras y Patrones

Para los casos más difíciles (cuando la fila que baja tiene 5 números), la estrategia es tan compleja que ni un humano podría recordarla de memoria.

• La autora usó una computadora para jugar millones de partidas en segundos.
• La computadora le dijo: "Si el tablero se ve así, el Jugador 1 gana. Si se ve asá, el Jugador 2 gana".
• Con esos datos, la autora encontró patrones (como un código secreto) que el Jugador 1 puede seguir para mantenerse en la zona de victoria, sin importar lo que haga el rival.

💡 ¿Por qué es importante esto?

Este artículo no solo resuelve un juego de números.

• Enseña a pensar: Muestra cómo transformar un problema difícil (números) en uno visual (tableros) para encontrar soluciones.
• Es un rompecabezas infinito: Aunque la autora resolvió los casos pequeños, el juego sigue abierto para tableros gigantes. Es como decir: "Ya sabemos cómo ganar en un tablero de ajedrez pequeño, pero en uno gigante, ¡aún estamos buscando la estrategia perfecta!".

En resumen

Imagina que eres un arquitecto que debe construir un rascacielos. Tu rival te lanza ladrillos. Si pones un ladrillo que hace que el edificio tenga una escalera perfecta hacia arriba o una escalera perfecta hacia abajo, pierdes.

La autora te dice: "No te preocupes, si sigues este mapa de colores (la cuadrícula) y mantienes el equilibrio, tú siempre podrás obligar a tu rival a poner el último ladrillo que hace que el edificio se caiga". ¡Es una victoria garantizada para el primer jugador!

Resumen técnico

A continuación presento un resumen técnico detallado del artículo "On an Erdős-Szekeres Game" (Sobre un juego de Erdős-Szekeres) de Lara Pudwell, publicado en Discrete Mathematics and Theoretical Computer Science.

1. Planteamiento del Problema

El artículo estudia una variante de dos jugadores de un juego basado en el Teorema de Erdős-Szekeres (1935). El teorema establece que cualquier permutación de longitud $n \ge (a-1)(b-1) + 1$ contiene necesariamente una subsucesión creciente de longitud $a$ ($I_a$) o una subsucesión decreciente de longitud $b$ ($J_b$).

El juego se define de la siguiente manera:

• Objetivo: Dos jugadores alternan turnos seleccionando números para construir una permutación.
• Condición de derrota (Juego Misere): El primer jugador que completa una subsucesión creciente de longitud $a$ o una subsucesión decreciente de longitud $b$ pierde.
• Parámetros: El juego depende de dos enteros positivos $a$ y $b$.
• Contexto: El trabajo anterior de Harary, Sagan y West (1983) y Albert et al. (2009) había analizado este juego, pero sus estrategias para $b \ge 4$ eran limitadas o se basaban en búsquedas computacionales exhaustivas que no escalaban bien. Este artículo busca proporcionar estrategias ganadoras analíticas y visuales para el caso de juego misere cuando $a \ge b$ y $b \in \{2, 3, 4, 5\}$.

2. Metodología: El Modelo de Sombreado de Cuadrícula

La contribución metodológica central es la traducción del juego de permutaciones a un juego geométrico de sombreado de celdas en una cuadrícula bidimensional. Esta representación se inspira en la prueba del Teorema de Erdős-Szekeres dada por Seidenberg (1959).

• La Tablero: Se define una cuadrícula de $(b-1)$ filas por $(a-1)$ columnas.
• Mecánica del Juego:
  • Cada número $n$ en la permutación se asocia a un par ordenado $(c, r)$, donde $c$ es la longitud de la subsucesión creciente más larga que termina en ese número, y $r$ es la longitud de la subsucesión decreciente más larga.
  • Al jugar un número, el jugador "sombrea" la celda $(c, r)$.
  • Regla de eliminación: Si una celda $(c, r)$ está sombreada, todas las celdas $(c', r')$ con $c' \le c$ y $r' \le r$ se consideran "eliminadas" (no disponibles para futuros movimientos).
  • Movimiento legal: Un jugador debe sombrear una celda que sea adyacente por aristas a la región eliminada actual.
  • Condiciones de victoria: El jugador que sombrea la celda en la esquina inferior derecha $(a-1, b-1)$ gana, ya que esto implica que la siguiente jugada obligará al oponente a completar una secuencia prohibida.
• Relación con Chomp: El autor nota que este juego es una variante del juego combinatorio clásico Chomp.
• Ventaja del modelo: A diferencia del enfoque de "palabras ternarias" utilizado en trabajos anteriores (Albert et al.), este modelo visual permite derivar estrategias geométricas claras y facilita el análisis de patrones para valores más grandes de $b$.

3. Contribuciones Clave y Resultados

El artículo proporciona estrategias ganadoras completas para el jugador 1 (P1) bajo la condición $a \ge b$ para los siguientes casos:

A. Caso $b = 2$

• Resultado: El ganador depende de la paridad de $a$.
• Estrategia: El tablero es una sola fila. Los jugadores simplemente llenan las celdas de izquierda a derecha. Si $a$ es par, P1 gana; si $a$ es impar, P2 gana.

B. Caso $b = 3$

• Resultado: El jugador 1 tiene una estrategia ganadora para todo $a \ge 3$.
• Estrategia: P1 mantiene un patrón específico donde, tras sus movimientos, la fila 1 tiene $i$ celdas sombreadas y la fila 2 tiene $i-1$. Esto fuerza al jugador 2 a entrar en una posición perdedora al final del juego.

C. Caso $b = 4$

• Resultado: El jugador 1 tiene una estrategia ganadora para todo $a \ge 4$.
• Estrategia: Se definen dos estados de tablero "seguros" (formas de celdas eliminadas). P1 responde a cualquier movimiento de P2 para mantener el tablero en uno de estos dos estados, garantizando que eventualmente P2 se vea forzado a tomar la celda perdedora.

D. Caso $b = 5$ (Contribución Principal)

• Resultado: El jugador 1 tiene una estrategia ganadora para todo $a \ge 5$.
• Innovación: Este es el primer resultado de este tipo para $b=5$ que va más allá de las estrategias dadas en la literatura anterior.
• Método: La estrategia se divide en tres fases: apertura, medio juego y final.
  • Se define un conjunto de estados ganadores $\mathcal{S}$ (7 configuraciones específicas de celdas sombreadas).
  • Se demuestra mediante búsqueda computacional asistida y análisis de casos que, si el tablero está en un estado de $\mathcal{S}$ al final del turno de P1, P1 puede responder a cualquier movimiento de P2 para regresar a un estado en $\mathcal{S}$.
  • Finalmente, se muestra cómo transitar desde $\mathcal{S}$ hacia un conjunto de estados de final de juego $\mathcal{E}$, donde P1 puede forzar la victoria mediante una estrategia de "ojo por ojo" (tit-for-tat) en las últimas filas/columnas.
• Complejidad: La estrategia para $b=5$ es significativamente más compleja que para $b < 5$, involucrando un análisis exhaustivo de paridades y configuraciones de celdas abiertas.

E. Juego Normal (Normal Play)

El artículo también analiza brevemente la variante donde el primer jugador en completar la secuencia gana.

• Se demuestra que la estrategia para el juego normal es isomorfa a la del juego misere, pero jugada en un tablero reducido de $(b-2) \times (a-2)$.
• Esto confirma la conjetura de que P1 gana en juego normal para $a \ge b \ge 4$.

4. Significado e Impacto

1. Generalización de Estrategias: El trabajo extiende las estrategias ganadoras conocidas para el juego de Erdős-Szekeres hasta $b=5$, superando las limitaciones de los análisis computacionales anteriores que no podían escalar fácilmente.
2. Nueva Perspectiva Visual: La introducción del modelo de "sombreado de cuadrícula" ofrece una herramienta intuitiva y poderosa para analizar juegos de permutaciones, conectando la teoría de patrones de permutaciones con juegos combinatorios geométricos.
3. Análisis de Complejidad: El artículo discute cómo el número de movimientos necesarios para ganar varía según la estrategia, mostrando que los juegos ganados por P1 suelen ser más cortos que la longitud máxima teórica $(a-1)(b-1)+1$.
4. Preguntas Abiertas: El autor plantea preguntas futuras sobre la existencia de estrategias para $b \ge 6$ y el comportamiento asintótico del número de posiciones ganadoras (clase P) a medida que $a$ crece, sugiriendo que el porcentaje de posiciones ganadoras podría converger a un valor no nulo.

En resumen, el artículo resuelve el problema de determinar el ganador y la estrategia óptima para una familia de juegos de permutaciones competitivos para parámetros específicos, utilizando una síntesis elegante de teoría de grafos, geometría discreta y teoría de juegos combinatorios.