Argumentos de estrategia robada en olimpiadas

La idea de la estrategia robada

El argumento de estrategia robada es una de las herramientas más elegantes de la combinatoria de juegos. La idea central es una prueba por contradicción: si suponemos que el segundo jugador tiene una estrategia ganadora, el primer jugador puede apropiarse de esa misma estrategia y usarla para ganar — una contradicción que implica que el segundo jugador no puede tener estrategia ganadora.

El argumento funciona cuando el juego tiene las siguientes propiedades: (1) es un juego imparcial o tiene suficiente simetría, (2) tener una ficha/movimiento de más no es perjudicial (en términos técnicos, el juego es "monótono" en el sentido de que una posición con más recursos no es peor), y (3) el primer movimiento puede ser "neutro" o puede ignorarse en la estrategia del jugador.

Formalmente: supongamos que el Jugador 2 tiene una estrategia ganadora $\Sigma$. El Jugador 1 hace un primer movimiento arbitrario $m_0$ (u "ocioso") y luego finge ser el Jugador 2, adoptando $\Sigma$. Cuando $\Sigma$ ordena al Jugador 2 hacer el movimiento que ya se realizó (porque el Jugador 1 lo hizo en $m_0$ o en un turno anterior), el Jugador 1 hace otro movimiento arbitrario. Como tener fichas extra no es perjudicial, el Jugador 1 puede seguir $\Sigma$ sin desventaja. Esto contradice que $\Sigma$ era estrategia ganadora para el Jugador 2.

El argumento concluye: el Jugador 2 no puede tener estrategia ganadora. En juegos sin empate, esto implica que el Jugador 1 tiene estrategia ganadora (aunque el argumento usualmente no la construye explícitamente). En problemas de olimpiada, el argumento de estrategia robada se usa para demostrar que el primero en mover gana, sin necesidad de describir la estrategia concreta.

Aplicación clásica: Hex y Chomp

Hex es un juego de tablero en un rombo de $n \times n$ hexágonos. Dos jugadores alternan colocando fichas de su color. El Jugador 1 (azul) gana si conecta el lado norte con el sur; el Jugador 2 (rojo) gana si conecta el este con el oeste. El juego tiene exactamente un ganador (no puede haber empate, porque si todos los hexágonos están ocupados, uno de los dos jugadores habrá conectado sus lados — esto es un resultado topológico no trivial).

Teorema (Nash, 1949): El primer jugador tiene estrategia ganadora en Hex. Demostración por estrategia robada: Supongamos que el Jugador 2 tiene estrategia ganadora $\Sigma$. El Jugador 1 hace el primer movimiento: coloca una ficha azul en cualquier hexágono $h_0$. Luego el Jugador 1 finge ser el Jugador 2 y sigue $\Sigma$. Cuando $\Sigma$ indica colocar en $h_0$ (que ya está ocupado), el Jugador 1 coloca una ficha en otro hexágono arbitrario y continúa siguiendo $\Sigma$ desde allí. Una ficha extra no puede perjudicar al Jugador 1 (más fichas propias en el tablero no impiden hacer conexión). Luego el Jugador 1 ganaría siguiendo $\Sigma$, contradiciendo que $\Sigma$ era ganadora para el Jugador 2. $\square$

Chomp es un juego en un tablero de $m \times n$ tabletas de chocolate. Los jugadores alternan eligiendo una tableta y comiendo esa tableta y todas las que están a su derecha y arriba (en el rectángulo superior-derecho). La tableta de la esquina inferior izquierda es "venenosa". El jugador que se ve forzado a comer la tableta venenosa pierde. El tablero de $1 \times 1$ es P-posición (el único movimiento es comer la tableta venenosa). Para todo $m, n > 1$ (no ambos iguales a 1), el Jugador 1 tiene estrategia ganadora. Demostración: Primero, el Jugador 1 hace el movimiento de comer solo la esquina superior derecha (tableta $(m,n)$). Si este movimiento es N-posición para el Jugador 2, el Jugador 1 ganó (el Jugador 2 ahora enfrenta N-posición). Si este movimiento es P-posición para el Jugador 2, entonces el Jugador 2 tiene un movimiento ganador $M$ desde esa posición. Pero el Jugador 1 podría haber hecho $M$ directamente como primer movimiento (ya que $M$ es un movimiento válido desde la posición inicial también), lo que sería P-posición para el Jugador 2 — el Jugador 1 ganaría. En ambos casos el Jugador 1 gana, o llegaríamos a la contradicción de que el Jugador 2 tiene estrategia ganadora pero el Jugador 1 puede robarla. $\square$

Nota importante: para Chomp y Hex, el argumento de estrategia robada demuestra que el Jugador 1 gana, pero no construye la estrategia explícita. Encontrar la estrategia concreta es un problema abierto para tableros grandes.

Estrategias de emparejamiento

Un caso especial muy útil del argumento de estrategia robada son las estrategias de emparejamiento (o estrategias de espejo). En este tipo de estrategia, el segundo jugador (o el primero, según convenga) empareja las posiciones del juego en pares $\{A_1, B_1\}, \{A_2, B_2\}, \ldots$ y responde siempre al movimiento del rival en $A_i$ con el movimiento en $B_i$, y viceversa.

Ejemplo 1 — Nim simétrico: Si se tienen $2k$ montones agrupados en pares iguales $(a_1, a_1, a_2, a_2, \ldots, a_k, a_k)$ (nim-suma $= 0$, P-posición), el Jugador 2 copia el movimiento del Jugador 1 en el montón emparejado. Por ejemplo, si el Jugador 1 quita $j$ fichas del primer montón de tamaño $a_i$, el Jugador 2 quita $j$ fichas del segundo montón de tamaño $a_i$. Esta estrategia de espejo garantiza que el Jugador 2 siempre tiene un movimiento disponible (el simétrico del de su rival), así que el Jugador 1 no puede ser el último en mover. Es decir, el Jugador 2 gana.

Ejemplo 2 — Nim en tablero: Se tiene un tablero de $2n$ casillas en una fila, numeradas $1$ a $2n$. En cada turno, un jugador cubre una casilla. El Jugador 1 gana si la suma total de casillas cubiertas al final es impar. Estrategia de emparejamiento del Jugador 2: parear las casillas $(1, 2n), (2, 2n-1), \ldots, (n, n+1)$. Cada par suma $2n+1$ (impar). El Jugador 2 responde al movimiento del Jugador 1 en la casilla $c$ con el movimiento en la casilla $2n+1-c$ (su pareja). Como todas las casillas se cubren en $2n$ turnos ($n$ pares de turnos), la suma total es la suma de todos los $2n$ números $= n(2n+1)$, que es fija e independiente del juego. Si $n$ es par, $n(2n+1)$ es par y el Jugador 2 gana independientemente; si $n$ es impar, el Jugador 1 gana independientemente. La estrategia de emparejamiento muestra quién tiene la ventaja.

Condición para estrategias de emparejamiento: Funcionan cuando el conjunto de posiciones admite una partición en pares $\{A_i, B_i\}$ tal que: (a) si la posición $A_i$ está disponible, también lo está $B_i$; (b) moverse a $A_i$ permite responder con $B_i$ (y viceversa); (c) el respondedor siempre tiene un par disponible mientras el iniciador tenga movimientos. La condición (c) es la más delicada y requiere verificarse cuidadosamente en cada problema.

Cómo escribir un argumento de estrategia robada en olimpiada

En un problema de olimpiada, el argumento de estrategia robada debe presentarse con rigor. Los componentes de una solución bien escrita son:

Paso 1 — Afirmar quién gana: Enunciar claramente la conclusión: "El primer jugador tiene estrategia ganadora" (o el segundo, según corresponda).

Paso 2 — Presentar la estrategia (o la contradicción): Si la estrategia es explícita, describirla con precisión: "El primer jugador responde siempre...". Si se usa el argumento de robo, describir exactamente cómo se adopta la estrategia del rival y qué movimiento se hace cuando la estrategia indica un lugar ya ocupado.

Paso 3 — Verificar la corrección: Demostrar que la estrategia descrita está bien definida en todo momento (el movimiento indicado es siempre válido) y que conduce a una victoria.

Paso 4 — Caso base: Verificar los casos pequeños ($n = 1, 2$) para que el grader confíe en el argumento.

Error frecuente: En el argumento de robo, asumir sin justificación que "tener un movimiento extra no es perjudicial". Esto es verdad en Hex (más fichas propias no impiden la conexión) y en Chomp, pero no en todos los juegos. Siempre hay que justificar por qué la asimetría no perjudica.

Otro error: Confundir "el Jugador 1 tiene estrategia ganadora" con "el Jugador 1 siempre gana". El argumento de estrategia robada muestra que el Jugador 2 no puede tener estrategia ganadora, lo que (en juegos sin empate con dos resultados posibles) equivale a que el Jugador 1 sí tiene estrategia ganadora. En juegos con empate posible, el argumento solo muestra que el Jugador 2 no puede ganar, pero el resultado podría ser empate.

Problema de olimpiada: estrategia robada aplicada

Problema (estilo Cono Sur): En un tablero de $1 \times 2n$ ($n \geq 1$), los jugadores alternan colocando dominós horizontales (que cubren 2 casillas consecutivas) o fichas únicas. El jugador que no puede colocar una pieza pierde. Demuestra que el primer jugador tiene estrategia ganadora.

Solución: Enumeramos las casillas $1, 2, \ldots, 2n$ y las emparejamos simétricamente: el par $i$ es $\{i, 2n+1-i\}$ para $i = 1, \ldots, n$. El tablero tiene simetría de reflexión respecto al centro.

Primer movimiento del Jugador 1: Colocar una ficha única en la casilla central $n$ (si $2n$ es impar no hay casilla exactamente central, así que el argumento se ajusta; para $2n$ par, la simetría es sobre el punto central, no una casilla). Más simplemente: el Jugador 1 coloca un dominó en las casillas centrales $n$ y $n+1$.

Estrategia de espejo: Después del primer movimiento, el tablero queda dividido en dos partes simétricas de $n-1$ casillas cada una. Cada vez que el Jugador 2 coloque una pieza en la mitad izquierda (casillas $1$ a $n-1$), el Jugador 1 coloca la pieza simétrica en la mitad derecha (casillas $n+2$ a $2n$), y viceversa.

Corrección: Como el tablero restante es siempre simétrico después del turno del Jugador 1, siempre que el Jugador 2 tenga un movimiento disponible, el Jugador 1 tiene el movimiento simétrico disponible. Luego el Jugador 2 es siempre el primero en quedarse sin movimientos. El Jugador 1 gana. $\square$