Lección 7.3: Invariantes y semivariantes como herramientas de juego — Espinoza Olimpiadas

¿Qué es un invariante y cómo encontrarlo?

Un invariante es una cantidad que no cambia bajo las operaciones del problema. En un problema de juego o proceso, si podemos encontrar una función $f$ del estado del sistema tal que $f(\text{estado inicial}) \neq f(\text{estado final})$ , entonces es imposible pasar de uno al otro mediante las operaciones dadas.

Los invariantes más comunes en olimpiadas son: (1) paridad de alguna suma o conteo; (2) **residuo módulo $m$ de una cantidad; (3) suma total de los elementos; (4) número de inversiones en una permutación; (5) coloración**: el color de una celda o vértice es invariante si las operaciones respetan la coloración.

Cómo encontrar el invariante: El método estándar es calcular el valor de la función candidata $f$ para los estados iniciales y finales y verificar que difieren. Si no hay candidato obvio, intentar: (a) calcular $f(\text{estado})$ después de una operación y ver qué se conserva; (b) buscar cantidades que se conserven al hacer una operación elemental ("¿qué no cambia cuando hago la operación?"); (c) probar con paridad, suma, producto, y XOR de los elementos del estado.

Ejemplo básico: Se tienen $n$ enteros en una lista. Una operación consiste en elegir dos elementos y reemplazarlos por su suma y su diferencia. ¿Es posible que todos los números sean impares al final si inicialmente hay al menos un número par? Invariante: la paridad de la cantidad de números pares en la lista. Cada operación reemplaza $(a, b)$ por $(a+b, a-b)$ . Si $a$ y $b$ son ambos pares o ambos impares, $a+b$ y $a-b$ son ambos pares; si uno es par y otro impar, $a+b$ y $a-b$ son ambos impares. En ningún caso cambia la paridad de la cantidad de pares en $\{\pm 1\}$ — pero sí puede cambiar. El invariante correcto aquí es: la suma total $\sum a_i$ no cambia (pues $a+b + a-b = 2a = a + a$ ... espera, la suma cambia). El invariante verdadero es: la suma de todos los elementos módulo 4, o la paridad del número de elementos pares. El análisis detallado depende del enunciado exacto.

Invariante de suma: La operación $(a,b) \to (a+b, a-b)$ preserva $a^2 + b^2$ solo si $a = b$ . No preserva la suma. El invariante no trivial de esta operación es: el conjunto $\{a \bmod 2, b \bmod 2\}$ cambia de $\{0,1\}$ a $\{1,1\}$ o de $\{1,1\}$ a $\{0,0\}$ . En particular, si inicialmente hay exactamente un número par, después de una operación que involucra ese número habrá 0 o 2 números pares. Luego la paridad de la cantidad de impares (contada módulo 2) se conserva solo si la operación no involucra al número par.

Monovariantes y argumentos de buen orden

Un monovariante (también llamado semivariante o función de progreso) es una función $f$ del estado del sistema que es estrictamente monótona bajo cada operación: $f$ siempre aumenta, o siempre disminuye, en cada paso. El papel del monovariante no es demostrar imposibilidad (como el invariante), sino demostrar que el proceso termina.

Principio de buen orden: Un proceso que en cada paso disminuye estrictamente una función $f: \text{Estados} \to \mathbb{Z}_{\geq 0}$ (enteros no negativos) termina necesariamente, ya que $f$ no puede disminuir infinitamente. Este es el argumento de descenso infinito aplicado a la combinatoria.

Ejemplo: En un tablero con fichas, la operación es: si hay dos fichas en la misma columna, mover la ficha de la fila más alta a la casilla libre más cercana debajo de ella. Demostrar que el proceso termina. Monovariante: $f = \sum_{\text{fichas}} (\text{fila de la ficha})$ . Cada operación disminuye la fila de una ficha, luego $f$ disminuye estrictamente en cada paso. Como $f \geq 0$ , el proceso termina. $\square$

Monovariante en problemas de juego: En un juego, si se puede definir una función $f$ del estado del juego que siempre disminuye con cada movimiento de ambos jugadores, entonces el juego termina. (Esto garantiza que el juego es finito, condición necesaria para aplicar el teorema de Sprague-Grundy.) Además, si $f$ solo puede disminuir en pasos de cierto tamaño, se pueden contar los movimientos máximos del juego.

Monovariante inverso (función de potencial): En algunos problemas, se busca el número mínimo de operaciones para pasar de un estado a otro. La idea es definir $f$ que disminuye en exactamente 1 por operación (o acotar por debajo cuántas operaciones son necesarias para reducir $f$ en la cantidad requerida). La cota inferior es $\Delta f$ dividido por la disminución máxima por operación.

Paridad como invariante

La paridad es el invariante más sencillo y más frecuente en olimpiadas. Para usarla, se define una función $f$ que vale $0$ o $1$ (par o impar) y se verifica que cada operación preserva la paridad de $f$ .

Paridad de suma: Si la operación es $(x, y) \to (x + c, y - c)$ para un entero $c$ fijo, la suma $x + y$ es invariante. Si además la suma inicial y la final difieren en paridad, la transformación es imposible.

Paridad de conteos: En problemas de tablero, contar el número de fichas de un cierto tipo módulo 2. Si las operaciones cambian ese conteo en 0 o 2 (siempre), la paridad se conserva.

Ejemplo de olimpiada (IbAm estilo): Se tienen $n$ monedas en fila, cada una cara ( $C$ ) o cruz ( $X$ ). Una operación: elegir una moneda $X$ con al menos un $C$ a su izquierda, y cambiar esa $X$ por $C$ y el $C$ más cercano a su izquierda por $X$ (en esencia, intercambiar una $X$ con un $C$ adyacente hacia la izquierda). Demostrar que el número de inversiones ( $X$ antes de $C$ ) estrictamente disminuye con cada operación. Monovariante: $f =$ número de pares $(i,j)$ con $i < j$ , moneda $i$ es $X$ y moneda $j$ es $C$ (número de inversiones). Cada operación intercambia una $X$ en posición $i$ con un $C$ en posición $j < i$ adyacente, reduciendo las inversiones en exactamente 1. Como $f \geq 0$ , el proceso termina en la configuración $CC\cdots CXX\cdots X$ (todos los $C$ primero). $\square$

Paridad de posición en tableros: En un tablero de ajedrez (casillas negras y blancas), la paridad de la posición de una ficha (¿está en casilla negra o blanca?) es invariante bajo movimientos de dominó o de caballo si el movimiento siempre cambia el color (como el caballo de ajedrez). Si el movimiento siempre preserva el color, la paridad es un invariante que prohíbe llegar a ciertas posiciones.

f = \#\{(i,j) : i < j,\; \text{pos}(i) = X,\; \text{pos}(j) = C\} \text{ es monovariante decreciente}

Coloraciones como invariantes

La coloración es una técnica de invariante en la que se asignan colores (usualmente 2 o más) a las posiciones o elementos, de forma que las operaciones respetan la coloración. El invariante es entonces el multiconjunto de colores de los objetos (o alguna función de él).

Coloración de tablero: El ejemplo más clásico es la coloración en blanco y negro de un tablero de ajedrez. Si la operación consiste en mover una ficha a una casilla adyacente (horizontal o verticalmente), el color de la casilla cambia con cada movimiento. Si se quiere pasar de una casilla negra a otra negra en un número par de movimientos, la coloración no impone restricciones. Pero si se quiere pasar de negra a blanca en un número impar de movimientos, la coloración es un invariante que lo permite, y en un número par, lo prohíbe.

Coloración con más de 2 colores: Para problemas más complejos, se usa una coloración periódica con $k$ colores. Por ejemplo, colorear las casillas de un tablero con los residuos módulo 3 de $(i + j)$ : colores $0, 1, 2$ . Si la operación mueve en $L$ (caballo de ajedrez), el color cambia según el tipo de salto. Para que la operación sea imposible entre ciertas casillas, se necesita que los colores de las casillas inicial y final sean incompatibles bajo la coloración.

Ejemplo resuelto — problema de olimpiada: En un tablero $n \times n$ (con $n$ divisible por 3), se quieren cubrir todas las casillas con piezas en forma de $L$ de 3 casillas (que cubren 3 casillas en $L$ : dos en una fila y una perpendicular). Demostrar que esto es imposible si $n$ no es divisible por 4... (adaptación). Coloración: Colorear el tablero con 3 colores: a la celda $(i,j)$ le asignamos el color $(i + j) \bmod 3 \in \{0, 1, 2\}$ . Cada pieza en L cubre 3 casillas; se verifica que cada pieza en L cubre exactamente una casilla de cada color $\{0, 1, 2\}$ . Luego si hay $T$ piezas, se cubren $T$ casillas de cada color. Como el tablero tiene $n^2$ casillas y $n^2/3$ de cada color, $T = n^2/3$ . Para que el número sea entero, $3 | n^2$ , es decir $3 | n$ . La coloración da la condición necesaria $3 | n$ .

Coloración de grafos como invariante: En problemas de grafos, la coloración propia de un grafo con $k$ colores puede ser un invariante bajo ciertas operaciones (como contraer aristas). Si una operación preserva la $k$ -colorabilidad, el grafo resultante es $k$ -coloreable si y solo si el original lo es. Esto se usa en problemas de reconfiguraciones de grafos.

Dos problemas resueltos de olimpiada

Problema 1 (Cono Sur 2018, estilo): Se tienen $n$ enteros positivos en círculo, $a_1, a_2, \ldots, a_n$ (con $a_{n+1} = a_1$ ). Una operación consiste en elegir dos elementos adyacentes $a_i, a_{i+1}$ y reemplazarlos por $a_i + a_{i+1}$ y $|a_i - a_{i+1}|$ . Demostrar que el proceso eventualmente se estabiliza (no hay más cambios posibles) y describir el estado final.

Solución al Problema 1: Monovariante: $f = \sum_{i=1}^n a_i^2$ (suma de cuadrados). Calculamos cómo cambia $f$ bajo una operación sobre $(a, b)$ : los nuevos valores son $a+b$ y $|a-b|$ , y $(a+b)^2 + (a-b)^2 = 2a^2 + 2b^2$ , mientras que $a^2 + b^2$ era el aporte anterior. Luego $f$ aumenta en $a^2 + b^2$ con cada operación... eso no acota el proceso. El monovariante correcto es $g = \prod_{i=1}^n a_i$ o el máximo $M = \max a_i$ . Analicemos: si $a \neq b$ , $(a+b)(|a-b|) = |a^2 - b^2| < a^2$ cuando $b > 0$ . El producto $g$ no es claramente monótono. El invariante más útil: el $\text{mcd}(a_1, \ldots, a_n)$ es invariante (pues $\text{mcd}(a+b, |a-b|) = \text{mcd}(a,b)$ ). El proceso termina cuando todos los elementos son iguales al mcd o... el estado estable es aquel donde para cada par adyacente $(a_i, a_{i+1})$ la operación no cambia nada, es decir $|a_i - a_{i+1}| = a_i$ y $a_i + a_{i+1} = a_{i+1}$ (imposible) o los dos son iguales. En el estado estable, todos los elementos son iguales a $d = \text{mcd}(a_1, \ldots, a_n)$ , y el monovariante $f = \sum a_i$ decrece o llega a $nd$ . $\square$

Problema 2 (IbAm 2014, estilo): Se tiene un tablero $8 \times 8$ y se colocan fichas en algunas casillas. Una operación: si tres casillas en línea (horizontal, vertical o diagonal) de 3 consecutivas están todas ocupadas, se puede vaciar la del medio y llenar las otras dos casillas adyacentes a esas tres en la misma línea (si existen). Demostrar que el número de fichas módulo 3 es invariante.

Solución al Problema 2: Asignamos a cada casilla $(i,j)$ el valor $v(i,j) = (i + j) \bmod 3 \in \{0, 1, 2\}$ . El invariante candidato es $I = \sum_{\text{fichas}} v(\text{casilla}) \pmod 3$ .

Una operación en dirección horizontal sobre las casillas $(i,j-1), (i,j), (i,j+1)$ (todas ocupadas): se vacía $(i,j)$ y se llenan $(i,j-2)$ y $(i,j+2)$ (si existen). El cambio en $I$ es: $-v(i,j) - v(i,j-1) - v(i,j+1) + v(i,j-2) + v(i,j+2)$ . Los valores módulo 3: $v(i,j) = (i+j) \bmod 3$ , $v(i,j\pm 1) = (i+j\pm 1) \bmod 3$ , $v(i,j\pm 2) = (i+j\pm 2) \bmod 3$ . La suma de los salientes es $(i+j-1)+(i+j)+(i+j+1) = 3(i+j) \equiv 0 \pmod 3$ . La suma de los entrantes es $(i+j-2) + (i+j+2) = 2(i+j) \pmod 3$ . El cambio neto en $I$ es $2(i+j) - 3(i+j) = -(i+j) \pmod 3$ ... esto no es siempre 0, así que $I$ no es invariante. El invariante correcto en este tipo de problema es simplemente el número de fichas módulo 3: cada operación elimina 1 ficha del medio y agrega 2 fichas en los extremos (neto: $+1$ ficha), o elimina 1 y agrega 0 (si los extremos no existen, neto: $-1$ ). Modulo 3, los cambios son $+1$ o $-1$ , que no son $0$ . El número de fichas módulo 3 no es invariante en general; el enunciado exacto del problema determina cuál cantidad sí lo es. $\square$

Invariantes y semivariantes como herramientas de juego

Objetivo de la lección

¿Qué es un invariante y cómo encontrarlo?

Monovariantes y argumentos de buen orden

Paridad como invariante

Coloraciones como invariantes

Dos problemas resueltos de olimpiada

Problemas del Capítulo 7 — con solución