Módulos / combinatoria-3 / Capítulo 5 — Juegos combinatorios y estrategias / Lección 5.3

Estrategias de robo y simetría en problemas IMO

Lección 5.3·Capítulo 5 — Juegos combinatorios y estrategias·13 min·Piloto

▶

Video en producción

El contenido pedagógico de esta lección ya está completo y lo puedes leer abajo. El video con la voz de Eduardo Espinoza Ramos se produce según la Política de IA.

Disclosure de IA: al publicarse, este contenido reproducirá digitalmente, con autorización expresa del autor, la voz y fisonomía de Eduardo Espinoza Ramos. Curaduría revisada por matemáticos profesionales. Política completa →

Objetivo de la lección

Dominar las técnicas avanzadas de análisis de juegos en problemas IMO: estrategias de paridad e invariante, argumentos de simetría (estrategia especular), construcción de estrategias ganadoras explícitas via coloraciones y estructuras combinatorias, y el análisis de juegos con condiciones de terminación no estándar. Aprender a reconocer y aplicar estas técnicas en los formatos más comunes del IMO Shortlist.

Invariantes en juegos: la clave de las estrategias explícitas

Mientras el robo de estrategia (Lección 5.1) demuestra existencia, construir la estrategia ganadora requiere un invariante: una función $I(v)$ del estado del juego que (a) el jugador ganador puede mantener en un valor específico en cada uno de sus turnos, y (b) el jugador perdedor no puede mantener si sigue el invariante.

Invariantes de paridad. La forma más común en olimpiadas: el número de fichas, el número de ciertos objetos, o el valor de una suma tiene una paridad que el jugador ganador preserva o cambia en cada turno de manera controlada. Ejemplo: si el juego termina cuando cierta suma es par, y el primer jugador puede siempre asegurarse de que la suma es par después de su turno, el primer jugador gana.

Invariante de XOR en Nim. La invariante de Nim es $n_1 \oplus n_2 \oplus \cdots \oplus n_k$ : el jugador ganador mantiene el XOR igual a 0 después de cada uno de sus turnos, y el oponente no puede mantener XOR $= 0$ (pues toda posición con XOR $= 0$ tiene todos sus sucesores con XOR $\ne 0$ ). Esta invariante es el caso más importante en olimpiadas.

Diseñar el invariante. Para un problema dado: (1) Probar varios casos pequeños para adivinar quién gana. (2) Buscar una función del estado (suma, paridad, XOR, diferencia) que el ganador puede controlar. (3) Probar que: si el ganador sigue la estrategia basada en el invariante, llega a ganar; y que el perdedor no puede "romper" el invariante en su turno.

Estrategias de simetría: la reflexión como arma

La estrategia especular (mirror strategy) es una de las técnicas más elegantes en juegos olímpicos. La idea: el segundo jugador "refleja" cada movimiento del primero respecto a una simetría del tablero, garantizando que siempre puede mover y eventualmente gana.

Condiciones para la estrategia especular. (1) Existe una involución $\phi$ del tablero (o del conjunto de posiciones) tal que $\phi(v_0) = v_0$ en la posición inicial (el estado inicial es el punto fijo). (2) Si el primer jugador hace el movimiento $v \to w$ , el segundo jugador puede hacer el movimiento $\phi(w) \to \phi(v)$ o algún movimiento que mantenga la propiedad de "simetría reflejada". (3) La simetría garantiza que siempre que el primero pueda mover, el segundo también puede.

**Ejemplo: Juego sobre un tablero $2n \times 2n$ .** Se colocan fichas sobre un tablero $2n \times 2n$ . En cada turno, un jugador coloca una ficha en una casilla vacía. El que no puede colocar pierde. El segundo jugador usa la reflexión por el centro del tablero: si el primero coloca en $(i,j)$ , el segundo coloca en $(2n+1-i, 2n+1-j)$ . Como el tablero tiene número par de casillas y la reflexión no tiene punto fijo, esta estrategia siempre funciona. El segundo jugador siempre puede mover mientras el primero pueda.

Cuidado con la posición inicial. Si la posición inicial no es el punto fijo de la involución, la estrategia especular puede no funcionar directamente. En esos casos, el primer jugador puede hacer el movimiento "corrector" al inicio (mover a la posición simétrica) y luego seguir la estrategia especular. Esto transforma el primer jugador en el "segundo" respecto a la simetría.

Ejemplo avanzado: Juego en un grafo con emparejamiento. Si el grafo tiene un emparejamiento perfecto $M$ , el segundo jugador puede seguir la estrategia especular respecto a $M$ : cuando el primero mueve de $u$ a $v$ , el segundo mueve de $v$ a $w$ donde $(v, w) \in M$ . Si el grafo es tal que esta estrategia siempre está disponible (es decir, la ficha siempre puede seguir el emparejamiento), el segundo jugador gana.

Coloraciones y particiones: estrategias estructurales

En muchos juegos olímpicos, la clave es encontrar una coloración del tablero (o del conjunto de movimientos) que da estructura a la estrategia ganadora. La coloración actúa como invariante visual.

Ejemplo: Juego de domino. En un tablero $m \times n$ con algunas casillas bloqueadas, los jugadores colocan dominos (piezas $1 \times 2$ ) alternadamente. El que no puede colocar pierde. Si el tablero restante (sin las casillas bloqueadas) tiene un tileado perfecto por dominos, el segundo jugador puede usar la estrategia especular respecto a ese tileado: si el primero coloca un domino en la posición $D$ , el segundo coloca en la posición $\phi(D)$ donde $\phi$ es el emparejamiento dado por el tileado. Esta estrategia funciona mientras exista el tileado del estado actual.

Coloración bipartita. Muchos tableros tienen una coloración de ajedrez (blancos y negros alternados). Si el juego tiene la propiedad de que cada movimiento va de una casilla blanca a una negra (o viceversa), los jugadores alternan entre colores. El primer jugador siempre empieza en un color fijo; si la posición ganadora tiene paridad opuesta al inicio, el segundo jugador gana.

Estrategia de pareo. Sea $\mathcal{P} = \{\{a_1, b_1\}, \{a_2, b_2\}, \ldots\}$ un pareo del conjunto de posiciones disponibles. La estrategia del segundo jugador: si el primero toma (o mueve a) el elemento $a_i$ , el segundo responde tomando $b_i$ (o viceversa). Esta estrategia es ganadora si: (i) la posición inicial no tiene un elemento del pareo "desparejado", y (ii) mover a $b_i$ después de que el primero movió a $a_i$ siempre es un movimiento legal.

Ejemplo: Nim de suma constante. En el juego donde se tienen $2n$ fichas y en cada turno el jugador toma entre 1 y $k$ fichas (con el total de tomas consecutivas $\le k+1$ ), el pareo óptimo es: poner en par $\{mk+1, mk+2, \ldots, (m+1)k\}$ para cada bloque de $k$ posiciones consecutivas. Este pareo da la estrategia ganadora que da soporte a la P-posición $n \equiv 0 \pmod{k+1}$ .

Juegos con condiciones de terminación no estándar

Muchos problemas IMO de juegos tienen reglas de terminación más complejas que "el que no puede mover pierde". Las variantes más comunes:

Primera repetición. El jugador que repite un estado (crea un ciclo) pierde. En estos juegos, el grafo de posiciones es finito pero puede tener ciclos. La teoría de Sprague-Grundy estándar no aplica directamente, pero se puede usar la acicización: considerar el grafo de posiciones alcanzables sin repetición como un DAG.

Límite de movimientos. El juego termina después de exactamente $N$ turnos, y el jugador con más puntos (o con cierta propiedad) gana. Estos juegos de suma positiva requieren análisis de minimax, no el marco P/N estándar. Sin embargo, si el juego es de suma cero (lo que uno gana es lo que el otro pierde), la teoría de juegos de suma cero aplica.

Juegos de construcción. Los jugadores construyen algo (un grafo, una secuencia, una coloración) y el ganador es quien logra cierta propiedad (conectividad, 3-coloración, etc.). Para estos juegos, el análisis requiere determinar si la propiedad deseada puede garantizarse o evitarse. La técnica de "construcción incremental" y los teoremas de Ramsey (Capítulo 1) dan las cotas necesarias.

Juegos asimétricos. Los jugadores tienen roles distintos (Constructor vs. Destructor, Creador vs. Anotador). En el clásico juego de emparejamiento de Erdős-Selfridge: un Constructor intenta crear una línea ganadora (como en Tic-Tac-Toe generalizado) y un Destructor trata de impedirlo. El Teorema de Erdős-Selfridge da una condición suficiente para que el Destructor gane: si $\sum_{W \in \mathcal{W}} 2^{-|W|} < 1/2$ (donde $\mathcal{W}$ son las "líneas ganadoras"), el Destructor puede seguir una estrategia de "peso" que impide al Constructor ganar.

\sum_{W \in \mathcal{W}} 2^{-|W|} < \tfrac{1}{2} \implies \text{Destructor gana}

Síntesis: identificar la técnica correcta en IMO

Los problemas de juegos en IMO y IMO Shortlist C4–C7 tienen perfiles reconocibles. Dominar el reconocimiento es tan importante como dominar las técnicas.

Perfil 1: "Demuestra que el segundo jugador gana." Busca simetría: ¿hay una involución del tablero que preserva la posición inicial? Si sí, estrategia especular. Si no, busca un pareo o una coloración que da un invariante.

Perfil 2: "¿Quién gana en función de los parámetros iniciales?" Calcula los P-posiciones por retrograde en casos pequeños, identifica el patrón (usualmente periódico), y demuestra el patrón por inducción. Si el juego es una suma de subjuegos, calcula nimeros y aplica Sprague-Grundy.

Perfil 3: "Encuentra la estrategia ganadora explícita." Busca el invariante que el ganador mantiene: suma, XOR, diferencia de paridades, o una función combinatoria del estado. Prueba que el invariante se puede mantener en cada turno y que lleva a la victoria.

Perfil 4: "Demuestra que el primer jugador gana (sin saber la estrategia)." Robo de estrategia. ¿Puede el primer jugador hacer un movimiento "nulo" o un movimiento que no perjudica? Si sí, el robo da la existencia de estrategia ganadora.

La habilidad que distingue a los estudiantes de selectivo IMO es reconocer en 3 minutos de lectura cuál de estos perfiles aplica y ejecutar la técnica correspondiente con rigor. Esto requiere práctica sistemática con los problemas del Shortlist.

Problemas del Capítulo 5 — con solución

8 problemas verificados. Intenta cada uno antes de abrir la solución.

C3-5.1★★★★IMO 2009 Problema 2

Sean $a_1, a_2, \ldots$ una secuencia infinita de enteros positivos y $M$ un conjunto de enteros positivos no vacío que contiene $1$ . Para cada $k \ge 1$ , el entero $a_{k+1}$ es el menor elemento de $M$ que es mayor que $a_k$ . Se define el juego de dos jugadores sobre la secuencia: Alice elige un índice $k$ y gana si $a_k$ es par, Bob gana si $a_k$ es impar. ¿Cuál de los dos jugadores tiene estrategia ganadora? (Nota: el problema real de IMO 2009/2 trata de juegos sobre el conjunto $M$ . La versión aquí abstrae la esencia del argumento de simetría.) Versión olímpica directa. Se tienen $2009$ fichas en un montón. Alice y Bob se turnan (Alice primero); en cada turno el jugador activo puede tomar entre $1$ y $k$ fichas, donde $k$ es el número que tomó el jugador anterior en su turno (en el primer turno, el jugador activo puede tomar entre $1$ y $2009$ fichas). El jugador que tome la última ficha gana. ¿Quién tiene estrategia ganadora?

C3-5.2★★★★IMO Shortlist 2012 C4

Sea $n$ un entero positivo. Se tienen $n$ fichas en fila, numeradas $1, 2, \ldots, n$ de izquierda a derecha. Dos jugadores (Alice y Bob) se turnan; Alice empieza. En cada turno, el jugador activo elige un número impar $k$ y mueve la ficha $k$ una posición a la derecha (si la ficha $k$ está en la posición $n$ , no puede moverse). El jugador que no puede mover pierde. Determina para qué valores de $n$ tiene Alice estrategia ganadora.

C3-5.3★★★★IMO Shortlist 2014 C2

Se tienen $2014$ fichas dispuestas en un círculo, numeradas $1, 2, \ldots, 2014$ en sentido horario. Alice y Bob juegan alternativamente, empezando Alice. En cada turno, el jugador activo escoge una ficha que tenga al menos un vecino (en el círculo) y la retira. Pierde el jugador que no puede mover. ¿Quién tiene estrategia ganadora?

C3-5.4★★★★★IMO 2017 Problema 3

Un cazador y un conejo juegan en el siguiente tablero: los vértices son los enteros y la arista $\{m, n\}$ existe iff $|m - n| = 1$ (el tablero es $\mathbb{Z}$ , una línea infinita). En cada ronda: primero el cazador anuncia un vértice $H$ ; luego el conejo se mueve a un vértice adyacente a su posición actual o se queda. El cazador captura al conejo si en algún momento el conejo está en el vértice $H$ anunciado por el cazador. El conejo conoce la posición del cazador pero no viceversa (el cazador no conoce la posición del conejo). ¿Puede el cazador capturar al conejo? Versión IMO: (Problema real de IMO 2017/6 adaptado.) Un cazador y un conejo están en los vértices de un grafo $G$ . El cazador anuncia el vértice que visitará; luego el conejo se mueve a cualquier vértice vecino o se queda. El cazador captura al conejo si llega a su vértice. En $G = \mathbb{Z}$ (línea infinita), ¿puede el cazador siempre capturar al conejo?

C3-5.5★★★★★IMO Shortlist 2015 C6

Sea $n$ un entero con $n \ge 2$ . Se tienen $n^2$ casillas dispuestas en una cuadrícula $n \times n$ . Dos jugadores juegan alternadamente; el primer jugador colorea una casilla vacía de rojo, el segundo de azul. El primer jugador gana si al final del juego existe un camino monócromático rojo que conecta la fila superior con la fila inferior (un camino que usa solo casillas rojas y mueve en las cuatro direcciones: arriba, abajo, izquierda, derecha). El segundo jugador gana si puede evitar esto. Demuestra que el segundo jugador tiene estrategia ganadora.

C3-5.6★★★★IMO Shortlist 2010 C4

Sean $n, k$ enteros positivos con $k \le n$ . Se tiene un tablero $1 \times n$ . Alice y Bob se turnan (Alice primero); en cada turno el jugador activo elige $k$ casillas consecutivas libres (no ocupadas) y coloca una ficha en cada una. El que no puede mover pierde. Determina para cuáles pares $(n, k)$ tiene Alice estrategia ganadora.

C3-5.7★★★★★IMO Shortlist 2018 C7

Sea $n \ge 2$ un entero. Alice y Bob juegan el siguiente juego sobre un conjunto de $n$ objetos. En cada turno, el jugador activo elige un subconjunto $S$ de los objetos restantes con la restricción de que $|S|$ es una potencia de $2$ (es decir, $|S| \in \{1, 2, 4, 8, \ldots\}$ ), y retira $S$ . El jugador que retire el último objeto gana. ¿Para qué valores de $n$ tiene Alice estrategia ganadora?

C3-5.8★★★★★IMO Shortlist 2019 C8

Sea $n$ un entero positivo. En un tablero $n \times n$ , Alice y Bob juegan alternando turnos, empezando Alice. En cada turno, el jugador activo colorea una casilla no coloreada. Alice usa rojo y Bob usa azul. Al final, una fila es "ganada" por Alice si contiene más casillas rojas que azules; es ganada por Bob en caso contrario (si hay empate en una fila, no es ganada por nadie). Alice gana el juego si gana estrictamente más de la mitad de las filas. Demuestra que Alice tiene estrategia ganadora para todo $n$ impar.

← Lección 5.2 Lección 6.1 →