Usar múltiples colores para encontrar invariantes.
Los invariantes de colores múltiples son una técnica combinatoria que te sirve para analizar los estados de un sistema, sobre todo en problemas de cubrimientos (tilings), transformaciones en cuadrículas y juegos. Mientras que los argumentos de paridad simples (coloreado con 2 colores) te ayudan a distinguir entre dos estados (como blanco y negro), los invariantes de colores múltiples extienden este concepto al partir los elementos de un conjunto o cuadrícula en $n$ clases distintas (colores). Al asignar valores o colores específicos a las casillas —muchas veces usando aritmética modular o raíces de la unidad— puedes detectar restricciones que la paridad simple no puede ver.
Esta técnica es esencial cuando analizas cómo cubrir tableros con poliominós de tamaño $n > 2$ (como trominós o tetrominós) o cuando los movimientos en un juego afectan el tablero de una forma que es invariante módulo $n$. La idea clave es construir un coloreado tal que cada "movimiento" o "ficha" válida interactúe con los colores de una forma constante y predecible (por ejemplo, que cada ficha cubra exactamente una casilla de cada color). Si la configuración final o el tablero completo no cumple con la distribución total de colores que requieren las fichas, entonces la configuración es imposible.
En contextos avanzados, puedes formalizar los invariantes de colores múltiples usando técnicas algebraicas. En lugar de colores literales, puedes asignar raíces de la unidad complejas o polinomios a las casillas de la cuadrícula. Por ejemplo, asignar el peso $\omega^{i+j}$ (donde $\omega$ es una raíz de la unidad) a la casilla $(i,j)$ permite hacer demostraciones algebraicas rigurosas de imposibilidades combinatorias, funcionando básicamente como una versión "continua" del coloreado discreto.
1. Coloreado Modular Lineal Para una casilla en la fila $i$ y la columna $j$ (empezando en 1), un esquema de coloreado común usando $n$ colores es: $$C(i, j) \equiv i + j \pmod n$$ O bien, para restricciones direccionales específicas: $$C(i, j) \equiv i \pmod n \quad \text{o} \quad C(i, j) \equiv j \pmod n$$
2. La Condición del Invariante Sea $N_k$ el número de casillas de color $k$ en el tablero. Si cada ficha válida cubre exactamente una casilla de cada color $0, 1, \dots, n-1$, entonces una condición necesaria para que el cubrimiento sea válido es: $$N_0 = N_1 = \dots = N_{n-1}$$
3. Raíces de la Unidad (Coloreado Algebraico) Para capturar invariantes más complejos, asigna un peso $w(i,j)$ a la casilla $(i,j)$ usando raíces $n$-ésimas de la unidad $\omega = e^{2\pi i / n}$: $$w(i, j) = \omega^{i} \quad \text{o} \quad w(i, j) = \omega^{i+j}$$ Si una ficha cubre casillas cuyos pesos suman $S$, y $S=0$, entonces la suma de los pesos de todo el tablero también debe ser $0$.
4. Condición del Teorema de De Bruijn Puedes cubrir un rectángulo de $a \times b$ con rectángulos de $1 \times n$ si y solo si: $$n \mid a \quad \text{o} \quad n \mid b$$
Teorema: No puedes cubrir un tablero de $10 \times 10$ con tetrominós de $1 \times 4$ (fichas rectas de $1 \times 4$).
Demostración: Usa un argumento de invariante de colores múltiples con 4 colores.
Paso 1: Define el coloreado Asigna un color $c$