Invariantes

Teoría

Un invariante es una propiedad, cantidad o estado de un sistema que no cambia cuando aplicas ciertas operaciones o transformaciones permitidas. En el contexto de la combinatoria y los procesos algorítmicos, los problemas suelen presentarte un estado inicial y un conjunto de reglas para moverte a nuevos estados. La estrategia principal consiste en identificar una característica —como la paridad, un residuo modular o una suma ponderada— que se mantenga igual con cada movimiento legal. Si el estado inicial tiene un valor invariante específico y el estado final tiene uno diferente, es totalmente imposible llegar del inicio al final.

Esta técnica es fundamental para demostrar que algo es imposible y para analizar cómo se comportan los sistemas dinámicos. Aunque casi siempre se asocia con "pruebas de imposibilidad" (demostrar que una tarea no se puede hacer), los invariantes también son cruciales para clasificar estados alcanzables y analizar si los algoritmos terminan (usando monovariantes, que son cantidades que siempre aumentan o siempre disminuyen). El poder del principio del invariante está en que te permite ignorar los detalles complejos y caóticos de los pasos intermedios para enfocarte solo en una propiedad fundamental que se conserva.

Algunos tipos comunes de invariantes incluyen la paridad (revisar si una cantidad sigue siendo par o impar), los invariantes modulares (revisar los residuos módulo $n$) y los invariantes de coloración (asignar valores o colores a una cuadrícula para rastrear los cambios). Por ejemplo, en problemas de pavimentación, colorear un tablero como si fuera uno de ajedrez suele revelar que una pieza debe cubrir colores específicos, lo que crea una proporción de colores que debe existir en cualquier pavimentación válida.

Fórmulas Clave

Puedes formalizar el principio fundamental de invarianza así. Digamos que $S$ es un estado y $T$ es una transformación permitida. Una función $I$ es un invariante si: $$I(S) = I(T(S))$$ Por lo tanto, si $S_{start}$ es el estado inicial y $S_{end}$ es el estado al que quieres llegar, para que sea posible alcanzarlo necesitas que: $$I(S_{start}) = I(S_{end})$$

Tipos comunes de invariantes:

1. Invariante de paridad: Si una operación cambia un valor por $2k$, la paridad no cambia: $$x_{new} \equiv x_{old} \pmod 2$$

2. Invariante modular: Para un módulo $n$ específico, el valor del estado se conserva: $$S_{new} \equiv S_{old} \pmod n$$

3. Invariante de suma: En procesos donde reemplazas elementos $a, b$ por $a+b$ (u operaciones similares que conserven la suma), la suma total $S$ es constante: $$\sum_{x \in \mathcal{S}{new}} x = \sum{x \in \mathcal{S}_{old}} x$$

4. Invariante de coloración (Tablero de ajedrez): Para un conjunto de piezas que cubren una cuadrícula, si cada pieza cubre exactamente $w$ casillas blancas y $b$ casillas negras, el número total de casillas cubiertas debe cumplir: $$N_{white} = k \cdot w \quad \text{y} \quad N_{black} = k \cdot b$$ donde $k$ es el número de piezas.

Demostración

Teorema (Problema del tablero de ajedrez mutilado): Es imposible cubrir un tablero de ajedrez de $8 \times 8$ al que se le quitaron dos esquinas opuestas diagonalmente usando dominós estándar de $2 \times 1$.

Demostración: La idea es usar un invariante de coloración para demostrar que esto es imposible.

Paso 1: Define la propiedad invariante del dominó Imagina una coloración estándar de un tablero de ajedrez de $8 \times 8$ con casillas negras y blancas alternadas. Un dominó estándar de $2 \times 1$ cubre exactamente dos casillas adyacentes. En un tablero de ajedrez, cualquier par de casillas adyacentes siempre tiene colores distintos (una es negra y la otra es blanca). Digamos que $B$ es el número de casillas negras cubiertas y $W$ es el número de casillas blancas cubiertas por un conjunto de dominós. Para un solo dominó: $$b_i = 1, \quad w_i = 1$$ Entonces, para cualquier pavimentación perfecta que use $k$ dominós, el número total de casillas negras y blancas cubiertas debe ser igual: $$B_{total} = \sum_{i=1}^k b_i = k, \quad W_{total} = \sum_{i=1}^k w_i = k$$ Así que la condición invariante para cualquier área que se pueda cubrir con dominós es: $$B_{total} = W_{total}$$

Paso 2: Analiza el estado del tablero mutilado Un tablero de ajedrez estándar de $8 \times 8$ tiene 64 casillas: 32 negras y 32 blancas. El problema dice que quitemos dos esquinas opuestas diagonalmente. En una coloración estándar de ajedrez, las esquinas opuestas son del mismo color. Sin perder generalidad, supón que la esquina superior izquierda es blanca. Entonces la esquina inferior derecha también es blanca.

Después de quitar estas dos casillas blancas, la composición del tablero queda así: $$W_{board} = 32 - 2 = 30$$ $$B_{board} = 32 - 0 = 32$$

Paso 3: Compara los invariantes y concluye Compara el invariante necesario para una pavimentación válida con el estado real del tablero. Para que exista una pavimentación válida, necesitas que: $$W_{board} = B_{board}$$ Sin embargo, en nuestro tablero mutilado: $$30 \neq 32$$ Como el número de casillas negras no es igual al número de casillas blancas, la condición invariante se rompe. Por lo tanto, no hay forma de que un conjunto de dominós de $2 \times 1$ cubra el tablero mutilado.

$\square$