Clases de residuos que se conservan tras las operaciones.
Los invariantes modulares son una clase específica de invariantes que usas en la teoría de juegos combinatorios, procesos algorítmicos y problemas de teoría de números. Un invariante es una propiedad de un sistema que no cambia después de que realizas una operación específica. En el contexto de los invariantes modulares, esta propiedad es un valor asociado al estado del sistema que se queda congruente a un residuo fijo módulo $n$. Aunque los valores absolutos de los números en el sistema cambien drásticamente (creciendo sin parar o fluctuando), su residuo al dividirlos entre un entero $n$ bien elegido se queda igual.
Esta técnica es fundamental para demostrar resultados de "imposibilidad". Si un problema te pregunta si un estado inicial $S_{start}$ puede transformarse en un estado objetivo $S_{end}$ mediante un conjunto de movimientos permitidos, una estrategia efectiva es buscar una función $\Phi(S)$ tal que cada movimiento permitido preserve $\Phi(S) \pmod n$. Si puedes demostrar que $\Phi(S_{start}) \not\equiv \Phi(S_{end}) \pmod n$, habrás probado de forma rigurosa que el estado objetivo es inalcanzable. Esto es una generalización de los argumentos de paridad (que simplemente son invariantes modulares módulo 2).
El truco clave al aplicar este método está en elegir el módulo $n$ correcto y la función invariante $\Phi$ adecuada. Algunas opciones comunes para $\Phi$ incluyen la suma de los elementos, la suma alternada de los elementos o una suma ponderada basada en posiciones (que verás mucho en problemas de pavimentación o tableros de ajedrez). Por ejemplo, en problemas donde reemplazas dos números $a, b$ con un nuevo número derivado de ellos, busca simetrías algebraicas que preserven el valor módulo $k$, como la propiedad de que $a + b \equiv a + b - k \pmod k$.
1. El Principio del Invariante Modular Digamos que $\mathcal{S}$ es el conjunto de todos los estados posibles y $\mathcal{O}$ es un conjunto de operaciones permitidas. Si una función $\Phi: \mathcal{S} \to \mathbb{Z}$ cumple que: $$ \Phi(S') \equiv \Phi(S) \pmod n $$ para cada estado $S$ y cada estado $S'$ que resulte de aplicar una operación de $\mathcal{O}$ a $S$, entonces para cualquier secuencia de operaciones que transforme $S_{start}$ en $S_{end}$: $$ \Phi(S_{start}) \equiv \Phi(S_{end}) \pmod n $$
2. Invariantes de Suma Si una operación consiste en reemplazar un subconjunto de números ${x_1, \dots, x_k}$ con un nuevo conjunto ${y_1, \dots, y_m}$, la suma es un invariante modular módulo $n$ si: $$ \sum_{i=1}^k x_i \equiv \sum_{j=1}^m y_j \pmod n $$ Ejemplo común: Reemplazar los dígitos de un número por su suma preserva el valor módulo $9$.
3. Invariantes Polinomiales/Algebráicos Para operaciones que reemplazan $a, b$ por $a+b+kab$, la cantidad $\Phi(S)$ suele estar relacionada con productos o módulos específicos. $$ \text{Si } a, b \to a+b+ab, \text{ considera } (a+1)(b+1) - 1 $$ Esta operación preserva la cantidad $\prod (x_i + 1) - 1$.
4. Invariantes de Coloración/Posición Para problemas en cuadrículas, asígnale un valor $v(i,j)$ a la celda $(i,j)$. Un peso modular común es: $$ v(i,j) \equiv i + j \pmod 2 \quad \text{(Tablero de ajedrez/Paridad)} $$ $$ v(i,j) \equiv \omega^{i+j} \quad \text{(donde } \omega \text{ es una raíz de la unidad)} $$
Teorema: La imposibilidad de transición mediante invariancia modular.
Sea $S_0$ un estado inicial y $T$ un estado objetivo. Sea $\mathcal{F}$ un conjunto de operaciones permitidas tales que para cualquier operación $f \in \mathcal{F}$ y cualquier estado $S$, la función invariante $\Phi$ cumple $\Phi(f(S)) \equiv \Phi(S) \pmod n$. Si $\Phi(S_0) \not\equiv \Phi(T) \pmod n$, entonces no puedes llegar a $T$ desde $S_0$.
Demostración:
Paso 1: Define la secuencia de estados. Supón, por contradicción, que el estado objetivo $T$ es alcanzable desde $S_0$. Esto implica que existe una secuencia finita de operaciones $f_1, f_2, \dots, f_k \in \mathcal{F}$ que transforma $S_0$ en $T$. Sea la secuencia de estados intermedios $S_0, S_1, S_2, \dots, S_k$, donde: $$ S_{i} = f_i(S_{i-1}) \quad \text{para } 1 \le i \le k $$ y $S_k = T$.
Paso 2: Aplica inducción. Vas a probar por inducción que $\Phi(S_i) \equiv \Phi(S_0) \pmod n$ para todo $0 \le i \le k$.
Caso base: Para $i=0$, $\Phi(S_0) \equiv \Phi(S_0) \pmod n$ es trivialmente cierto.
Paso inductivo: Supón que para algún $j < k$, $\Phi(S_j) \equiv \Phi(S_0) \pmod n$. Sabes que $S_{j+1} = f_{j+1}(S_j)$. Por la definición del invariante modular que viste en el enunciado del teorema, aplicar cualquier operación preserva el valor módulo $n$. Por lo tanto: $$ \Phi(S_{j+1}) \equiv \Phi(S_j) \pmod n $$ Por la hipótesis inductiva, $\Phi(S_j) \equiv \Phi(S_0) \pmod n$. Por la transitividad de la congruencia modular: $$ \Phi(S_{j+1}) \equiv \Phi(S_0) \pmod n $$
Paso 3: Conclusión. Por inducción, la propiedad se cumple para todo $i$ hasta $k$. Por lo tanto, para el estado final $S_k = T$, debes tener: $$ \Phi(T) \equiv \Phi(S_0) \pmod n $$ Sin embargo, la condición inicial del teorema dice que $\Phi(S_0) \not\equiv \Phi(T) \pmod n$. Esto crea una contradicción (no puede ser que $x \equiv y$ y $x \not\equiv y$ al mismo tiempo).
Así que la suposición de que existe una secuencia de operaciones tiene que ser falsa. El estado $T$ es inalcanzable desde $S_0$.
$\square$