Posiciones ganadoras y perdedoras, robo de estrategia y emparejamiento.
La teoría de juegos combinatorios básica se enfoca en juegos para dos jugadores, imparciales, con información perfecta y sin elementos de azar (nada de dados o cartas). En estos juegos, como el Nim o varios juegos de resta, los movimientos disponibles dependen solo del estado del juego, no de qué jugador esté moviendo. El juego termina cuando un jugador ya no puede hacer un movimiento, y la convención estándar (Convención de Juego Normal) dicta que el último jugador en mover gana o, lo que es lo mismo, el primer jugador que no puede mover pierde.
La idea central para resolver estos juegos es clasificar cada estado del juego en una de dos categorías: Ganadora (posiciones $N$) o Perdedora (posiciones $P$). Una posición $N$ (gana el siguiente jugador) es un estado desde el cual el jugador actual tiene una estrategia ganadora. Una posición $P$ (gana el jugador previo) es un estado donde el jugador actual va a perder, asumiendo que el oponente juega de forma óptima. Este análisis se hace seguido usando inducción hacia atrás: empezando desde el estado terminal (el final del juego) y trabajando hacia atrás para determinar el estatus de los estados anteriores.
Dos técnicas poderosas para identificar estrategias ganadoras sin mapear cada estado son el Emparejamiento y el Robo de Estrategia. El emparejamiento (o simetría) consiste en encontrar un movimiento que restaure una simetría específica al estado del juego, obligando al oponente a romperla una y otra vez hasta que el juego termine. El robo de estrategia es un argumento no constructivo que se usa para demostrar que el primer jugador debe tener una estrategia ganadora (seguido en juegos simétricos como Hex o variaciones de Gato) al mostrar que si el segundo jugador tuviera una estrategia ganadora, el primer jugador podría adoptarla para ganar, lo que lleva a una contradicción.
1. Definición Recursiva de Posiciones Sea $S$ un estado del juego y $M(S)$ el conjunto de todos los estados alcanzables desde $S$ en un solo movimiento.
2. Juego de Bachet (El Juego de la Resta) Para un juego con una pila de $n$ objetos donde un jugador puede quitar $s$ objetos tal que $s \in {1, 2, \dots, k}$:
3. Argumento de Robo de Estrategia (Forma General) Se usa principalmente en juegos simétricos donde tener un movimiento extra nunca es una desventaja. $$\text{Si el Jugador 2 tiene una estrategia ganadora } \mathcal{S}, \text{ el Jugador 1 puede hacer un movimiento arbitrario y luego usar } \mathcal{S}.$$ Si esto lleva a una contradicción (por ejemplo, que el Jugador 1 gane usando la estrategia del Jugador 2), entonces el Jugador 2 no puede tener una estrategia ganadora.
Teorema: En un juego de resta con una sola pila de $n$ objetos donde un jugador puede quitar cualquier cantidad de objetos $s \in {1, 2, \dots, k}$, el primer jugador tiene una estrategia ganadora si y solo si $n$ no es un múltiplo de $k+1$.
Demostración: Denota una posición por el número de objetos $n$ que quedan en la pila. Hay que mostrar que el conjunto de posiciones $P$ (posiciones perdedoras) es exactamente el conjunto de enteros divisibles por $k+1$. Sea $T = {n \in \mathbb{Z}_{\ge 0} \mid n \equiv 0 \pmod{k+1}}$.
Verifica las tres condiciones requeridas para las posiciones $P$ y $N$:
Paso 1: El Estado Terminal El juego termina cuando un jugador no puede mover. Esto pasa cuando $n=0$ (ya que hay que quitar al menos 1 objeto). Como $0 \equiv 0 \pmod{k+1}$, el estado terminal está en $T$. Por definición, el estado terminal es una posición $P$.
Paso 2: Desde una posición $P$, todos los movimientos llevan a posiciones $N$ Supón que el tamaño actual de la pila es $n \in T$. Es decir, $n = m(k+1)$ para algún entero $m$. Un jugador quita $s$ objetos, donde $1 \le s \le k$. El nuevo tamaño de la pila es $n' = n - s$. $$n' = m(k+1) - s$$ Como $1 \le s \le k$, $s$ no es un múltiplo de $k+1$. Por lo tanto: $$n' \not\equiv 0 \pmod{k+1}$$ Así que cualquier movimiento desde un estado en $T$ lleva a un estado fuera de $T$. Si identificas los estados en $T$ como posiciones $P$, cualquier movimiento lleva a un estado que no es una posición $P$ (una posición $N$).
Paso 3: Desde una posición $N$, existe un movimiento hacia una posición $P$ Supón que el tamaño actual de la pila es $n \notin T$. Es decir, $n \not\equiv 0 \pmod{k+1}$. Por el algoritmo de la división, puedes escribir $n = q(k+1) + r$, donde $1 \le r \le k$. El jugador actual puede elegir quitar exactamente $s = r$ objetos. Nota que este es un movimiento legal porque $1 \le r \le k$. El nuevo tamaño de la pila se vuelve: $$n' = n - s = (q(k+1) + r) - r = q(k+1)$$ Así, $n' \equiv 0 \pmod{k+1}$, lo que significa que $n' \in T$. Esto muestra que desde cualquier estado que no esté en $T$, existe un movimiento que lleva a un estado en $T$.
Conclusión El conjunto $T = {n \mid n \equiv 0 \pmod{k+1}}$ cumple con las definiciones recursivas de las posiciones $P$. Por lo tanto, una posición $n$ es una posición perdedora si y solo si $n$ es un múltiplo de $k+1$. Por el contrario, si $n$ no es un múltiplo de $k+1$, el primer jugador siempre puede quitar $n \pmod{k+1}$ objetos para forzar al oponente a una posición perdedora.
$\square$