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

Teoría de juegos combinatorios: posiciones ganadoras y perdedoras

Lección 5.1·Capítulo 5 — Juegos combinatorios y estrategias·12 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 los fundamentos de la teoría de juegos combinatorios de dos jugadores con información perfecta: la clasificación de posiciones en ganadoras (P-posiciones) y perdedoras (N-posiciones), el algoritmo retrograde para determinar el valor de una posición, el Teorema de Zermelo, y la técnica de robo de estrategia. Entender cuándo una posición es un "segundo jugador gana" y cuándo el primer jugador tiene estrategia ganadora.

Juegos combinatorios: definición y marco

Un juego combinatorio (en el sentido de la teoría de juegos combinatorios) es un juego de dos jugadores (llamados habitualmente Jugador 1 y Jugador 2, o Alice y Bob) con las propiedades: (i) información perfecta (ambos jugadores conocen el estado completo del juego), (ii) sin azar, (iii) normal play convention: el jugador que no puede mover pierde (o en la variante misère: el que hace el último movimiento pierde).

Un estado o posición del juego es una descripción completa del tablero y a quién le toca mover. El conjunto de posiciones forma un grafo dirigido acíclico (DAG): los nodos son posiciones y las aristas van de una posición a las posiciones accesibles en un movimiento. Las posiciones sin sucesores son posiciones terminales (el jugador que está en ellas pierde bajo la convención normal play).

Los juegos combinatorios más comunes en olimpiadas: Nim y sus variantes, juegos sobre grafos (moverse a lo largo de aristas), juegos de divisibilidad (dividir o escribir números), juegos de tokens sobre tableros, y juegos de construcción (colocar fichas en un tablero).

La teoría matemática de estos juegos fue desarrollada por Sprague (1935) y Grundy (1939) de forma independiente, culminando en el Teorema de Sprague-Grundy que veremos en la Lección 5.2. En esta lección establecemos los fundamentos: la dicotomía P/N y la técnica del robo de estrategia.

Posiciones P y N: la dicotomía fundamental

Sea $G$ un juego combinatorio bajo la convención normal play. Definimos recursivamente:

Posición P (Previous player wins, o "el que movió antes gana"): la posición terminal es una P-posición; más generalmente, una posición $v$ es P si y solo si todos los sucesores de $v$ son N-posiciones.

Posición N (Next player wins, o "el que mueve ahora gana"): una posición $v$ es N si y solo si existe al menos un sucesor de $v$ que es una P-posición.

En otras palabras: estás en una posición perdedora (P) si cualquier movimiento que hagas lleva a tu oponente a una posición ganadora (N); y estás en una posición ganadora (N) si puedes mover a una posición perdedora (P) para tu oponente.

Teorema de existencia (Algoritmo retrograde). En todo juego combinatorio acíclico finito, toda posición es P o N (nunca ambas, nunca ninguna). El algoritmo para calcular el valor de cada posición: (1) Marcar todas las posiciones terminales como P. (2) Marcar como N toda posición que tenga un sucesor P. (3) Marcar como P toda posición no marcada cuyos todos los sucesores ya están marcados (todos son N). (4) Repetir hasta que no haya cambios. El proceso termina en tiempo finito si el grafo es acíclico.

La demostración es una inducción sobre el DAG: en el orden topológico inverso, cada posición recibe su valor. La acicidad garantiza que no hay ciclos que impidan la terminación.

v \text{ es P} \iff \text{todos los sucesores de } v \text{ son N}

Ejemplos: juego de divisores y juego de resta

Juego de resta. Dados $n$ fichas, cada jugador puede tomar 1, 2 o 3 fichas. El que tome la última pierde (versión misère) o gana (versión normal). Bajo normal play: la posición con 0 fichas es P (posición terminal, quien está aquí ha perdido). Con 1, 2, 3 fichas: N (puedes llegar a 0). Con 4 fichas: todos los movimientos llevan a 1, 2 o 3 (todas N), luego 4 es P. Patrón: $n$ es P iff $4 \mid n$ . Estrategia ganadora desde N: mover a la P-posición más próxima (tomar $n \bmod 4$ fichas).

Juego de divisores. Empezamos con un entero $n \ge 2$ . En cada turno, el jugador escoge un divisor propio $d \ge 2$ de $n$ y lo reemplaza por $n/d$ . El jugador que llega a 1 gana. El análisis: $n = 1$ es P (terminal, perdedor). $n$ primo: solo movimiento es $n \to 1$ (P), luego $n$ primo es N. $n = p^2$ : puedes ir a $p$ (N) o a 1 (P); como puedes ir a P, $p^2$ es N. $n = pq$ con $p \ne q$ primos: vas a $p$ o a $q$ (ambos N), o a 1 (P); puedes ir a P, luego N. En general, si $n$ tiene algún divisor propio $d \ge 2$ tal que $n/d$ es P, entonces $n$ es N. El análisis completo del juego de divisores requiere caracterizar los valores de $n$ que son P-posiciones.

Juego en un grafo. Una ficha empieza en un nodo $v_0$ de un grafo dirigido acíclico. Los jugadores alternan moviéndola a lo largo de una arista. El que no pueda mover pierde. Los nodos sumideros (sin salida) son P-posiciones; el análisis retrograde determina el resto. Este marco generaliza todos los juegos combinatorios.

El Teorema de Zermelo y estrategias determinísticas

Teorema de Zermelo (1913). En todo juego combinatorio finito de dos jugadores con información perfecta (sin empates posibles): exactamente uno de los dos jugadores tiene una estrategia ganadora.

La prueba usa el Lema de König (todo DAG finito tiene un nodo terminal alcanzable desde cualquier nodo) o directamente el algoritmo P/N: toda posición es P o N, y si la posición inicial es P gana el segundo jugador, si es N gana el primero.

Estrategia como función. Una estrategia para el Jugador 1 es una función $\sigma$ que a cada posición $v$ alcanzable por el Jugador 1 asigna un movimiento $\sigma(v)$ disponible en $v$ . La estrategia es ganadora si, siguiéndola, el Jugador 1 gana sin importar qué haga el Jugador 2.

Corolario importante. Si el juego tiene simetría de espejo (existe una involución $\phi$ del conjunto de posiciones que intercambia los dos jugadores y satisface $v \to w$ iff $\phi(v) \to \phi(w)$ ), y la posición inicial es un punto fijo de $\phi$ , entonces el segundo jugador puede "copiar" la estrategia del primero y ganar. Esta es la técnica de robo de estrategia: si ambas posiciones (la inicial y la imagen espejo) fuesen ganadoras para el primero, habría una contradicción.

Robo de estrategia: la técnica olímpica por excelencia

El robo de estrategia (strategy stealing) es un argumento de existencia que demuestra que el primer jugador tiene estrategia ganadora sin construir la estrategia explícitamente. El argumento es:

Supongamos que el segundo jugador tiene estrategia ganadora $\sigma_2$ . Entonces el primer jugador puede "ignorar" su primera jugada (haciendo un movimiento arbitrario o, si el juego lo permite, un movimiento "nulo"), y luego seguir la estrategia $\sigma_2$ como si fuera el segundo jugador. La primera jugada extra nunca puede ser perjudicial (en los juegos donde tener más fichas o más opciones no es malo), lo que da una contradicción.

Ejemplo: Juego de Hex. En Hex (tablero $n \times n$ con hexágonos, cada jugador conecta sus dos lados), el primer jugador tiene estrategia ganadora por robo: si el segundo tuviera estrategia $\sigma_2$ , el primero juega un hexágono arbitrario y luego sigue $\sigma_2$ . Si en algún punto $\sigma_2$ dicta "jugar donde ya hay una ficha del primero", eso solo favorece al primero. Luego el primero gana. (Esta es la prueba de existencia; la estrategia explícita para tamaños generales es desconocida.)

Ejemplo: Juego de crear conexiones. En muchos juegos de construcción (colocar fichas, conectar nodos), si tener una ficha adicional no puede perjudicar, el robo de estrategia garantiza que el primer jugador no pierde. En IMO, el argumento estándar es: "Si el segundo jugador tuviera estrategia ganadora, el primero la seguiría desde el principio, contradicción."

Limitación. El robo de estrategia solo funciona cuando el argumento "tener más es mejor" es válido. En juegos de Nim con reglas de no-tomar-la-última-ficha (misère), o en juegos donde agregar una ficha puede dañar, el robo puede fallar. En esos casos se necesita el Teorema de Sprague-Grundy.

En problemas de IMO Shortlist que piden demostrar que un jugador tiene estrategia ganadora sin construirla, el robo de estrategia es usualmente la ruta más corta. La construcción explícita de la estrategia se realiza con valores de Grundy (Lección 5.2) o con argumentos de invariante (Lección 5.3).

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 4.4 Lección 5.2 →