Usar coloraciones para demostrar que algo es imposible.
Los invariantes por coloración son una técnica combinatoria muy poderosa que se usa principalmente para demostrar que no puedes llegar a un cierto estado desde un estado inicial dado, o que una configuración específica (como una pavimentación) es imposible. La idea central es partir los elementos de un conjunto del problema (que suelen ser casillas de una cuadrícula, vértices de una gráfica o regiones en el plano) en clases separadas, asignando un "color" o valor a cada clase. Si los movimientos válidos o los componentes del sistema interactúan con estos colores de una forma constante y preservada, estableces un invariante.
Esta técnica se aplica con muchísima frecuencia en problemas de pavimentación (tilings), teoría de juegos y preguntas de alcanzabilidad algorítmica. Por ejemplo, en los problemas de pavimentación, analizas cuántas casillas de cada color cubre una sola ficha. Si existe una pavimentación completa, el número total de casillas de cada color en el tablero debe coincidir con la combinación lineal de los colores que cubren las fichas individuales. Si la distribución real de colores del tablero rompe este requisito, la pavimentación es imposible.
La intuición detrás de los invariantes por coloración es una generalización de la paridad. Mientras que la paridad suele implicar una distinción binaria (par/impar, blanco/negro), los invariantes por coloración pueden utilizar $k$ colores, aritmética modular o incluso raíces complejas de la unidad. Elegir la coloración es el "arte" de la técnica; aunque el patrón de tablero de ajedrez (2 colores) es el estándar, para resolver problemas complejos de Olimpiada a veces necesitas construir patrones de coloración específicos que no son tan obvios (como franjas, diagonales o bloques recursivos) que revelen las restricciones estructurales del problema.
El Principio del Invariante Sea $S$ el conjunto de todos los estados posibles y $T$ el conjunto de transformaciones válidas. Sea $I: S \to V$ una función (el invariante) que mapea estados a un conjunto de valores $V$. Si $I(s) = I(t)$ para todos los estados $s$ y cualquier estado $t$ al que puedas llegar desde $s$ mediante una sola transformación en $T$, entonces: $$ \text{Si } I(\text{inicio}) \neq I(\text{objetivo}), \text{ entonces el estado objetivo es inalcanzable.} $$
Coloración Estándar de Ajedrez (Bipartita) Para una casilla $(i, j)$, asigna el color $C(i, j)$: $$ C(i, j) = (i + j) \pmod 2 $$ Es útil para pavimentaciones con dominós ($1 \times 2$) y movimientos de caballo.
$k$-Coloración (Diagonal/Franjas) Para analizar fichas de $1 \times n$, solemos usar $n$ colores. Una asignación común para una casilla $(i, j)$ es: $$ C(i, j) = (i + j) \pmod n \quad \text{o} \quad C(i, j) = i \pmod n $$
Coloración con Raíces de la Unidad Para restricciones avanzadas, asigna un peso complejo $\omega^k$ a las casillas, donde $\omega$ es una raíz de la unidad. Para una ficha que cubre las casillas $c_1, \dots, c_k$: $$ \sum_{m=1}^k \text{peso}(c_m) = 0 \quad \text{(o alguna constante)} $$
Teorema: Es imposible pavimentar un tablero de $10 \times 10$ usando tetrominós de $1 \times 4$ (fichas rectas de longitud 4).
Demostración: La idea es proceder por contradicción. Supón que existe una pavimentación válida de un tablero de $10 \times 10$ usando fichas de $1 \times 4$.
Paso 1: Construir la coloración Aplica una 4-coloración específica a las casillas $(i, j)$ para $1 \le i, j \le 10$. Asigna un color $k \in {1, 2, 3, 4}$ a cada casilla basándote en su índice de fila y de columna. Definimos el color de la casilla $(i, j)$ mediante un patrón de coloración diagonal: $$ C(i, j) \equiv (i + j) \pmod 4 $$ (Para simplificar, mapeamos el resultado $0$ al color $4$).
Paso 2: Analizar una sola ficha Considera cualquier ficha de $1 \times 4$ colocada en el tablero. Ya sea que se coloque horizontal o verticalmente, la ficha cubre cuatro enteros consecutivos en términos de la suma de coordenadas $(i+j)$.
En módulo 4, la sucesión $S, S+1, S+2, S+3$ es una permutación de $1, 2, 3, 0$. Por lo tanto, cada ficha de $1 \times 4$ cubre exactamente una casilla de color 1, una de color 2, una de color 3 y una de color 4.
Paso 3: Analizar la pavimentación total Si el tablero se puede pavimentar con $N$ fichas de tamaño $1 \times 4$, el área total es $4N = 100$, así que $N=25$. Como cada ficha cubre exactamente una casilla de Color 2, el número total de casillas de Color 2 en el tablero debe ser exactamente $N = 25$.
Paso 4: Calcular los colores reales del tablero Ahora cuenta el número real de casillas de Color 2 en el tablero de $10 \times 10$. Una casilla $(i, j)$ tiene el Color 2 si $i + j \equiv 2 \pmod 4$. Busca estas ocurrencias. Las sumas posibles $k = i+j$ van desde $1+1=2$ hasta $10+10=20$. Busca las sumas $k \in {2, 6, 10, 14, 18}$. El número de soluciones para $i+j=k$ con $1 \le i, j \le 10$ lo puedes obtener con el coeficiente de $x^k$ en $(\sum_{m=1}^{10} x^m)^2$, o simplemente contando las diagonales:
Total de casillas de Color 2: $$ 1 + 5 + 9 + 7 + 3 = 25 $$ Esto coincide con lo que esperabas. Sin embargo, también debes revisar el Color 1 (o el Color 3). Una casilla tiene el Color 1 si $i+j \equiv 1 \pmod 4$. Las sumas son $k \in {5, 9, 13, 17}$.
Total de casillas de Color 1: $$ 4 + 9 + 8 + 4 = 25 $$ Esta coloración diagonal específica no produjo una contradicción de inmediato porque resulta que las cuentas para este tamaño de tablero coinciden para esta coloración. Tienes que elegir un invariante de coloración diferente.
Paso 5: La coloración correcta (Tipo 2) Usa una coloración más simple. Colorea la casilla $(i, j)$ con el color $i \pmod 2$. Esto crea filas alternadas de un solo color.