Usar dos colores para probar que un teselado es imposible.
La coloración de tablero de ajedrez es una técnica combinatoria muy potente que se usa principalmente para demostrar que es imposible cubrir una cuadrícula o región específica con un conjunto de piezas dado. La idea fundamental se basa en los invariantes: propiedades del sistema que no cambian sin importar cómo pongas las piezas. Al asignar valores específicos o "colores" (normalmente blanco y negro) a las casillas de una cuadrícula, puedes convertir un problema geométrico de piezas en un problema aritmético de conteo. Si los requisitos aritméticos de las piezas no coinciden con las propiedades aritméticas de la región, entonces cubrirla es imposible.
Esta técnica se aplica casi siempre a problemas de piezas de poliominós, especialmente los que usan dominós (piezas de $2 \times 1$). En un tablero de ajedrez normal, cualquier dominó que pongas en la cuadrícula tiene que cubrir exactamente una casilla negra y una blanca. Por lo tanto, para que puedas cubrir una región con dominós, una condición necesaria (aunque no suficiente) es que la región tenga la misma cantidad de casillas negras y blancas. Si una región rompe este equilibrio de colores, puedes concluir de inmediato que no existe forma de cubrirla, ahorrándote el trabajo de revisar todas las combinaciones posibles.
Aunque la coloración de 2 colores es la más común, el concepto se puede extender a patrones más complejos para resolver problemas difíciles. Por ejemplo, cubrir con trominós rectos (piezas de $3 \times 1$) suele requerir 3 colores, y formas específicas como trominós en L o tetrominós pueden necesitar coloraciones por franjas o por cuadrantes. El método de "Coloración de Tablero de Ajedrez" es la puerta de entrada al estudio más amplio de los invariantes y argumentos de coloración en la geometría combinatoria.
1. Condición necesaria para cubrir con dominós Para que una región $R$ se pueda cubrir perfectamente con dominós de $2 \times 1$, supón que $B$ es el conjunto de casillas negras y $W$ el de casillas blancas bajo una coloración estándar de tablero de ajedrez. Una condición necesaria es: $$|B| = |W|$$ Si $|B| \neq |W|$, la región $R$ no se puede cubrir con dominós.
2. Invariante general de piezas Supón que una región $R$ se cubre con $k$ piezas $T$ idénticas. Si aplicas un esquema de coloración tal que cada vez que pones una pieza $T$ cubres exactamente $b$ casillas negras y $w$ casillas blancas, entonces el total de casillas negras $|B_R|$ y blancas $|W_R|$ en la región debe cumplir: $$|B_R| = k \cdot b \quad \text{y} \quad |W_R| = k \cdot w$$ Esto implica que la proporción de colores en la región debe ser igual a la proporción de colores que cubre una sola pieza: $$\frac{|B_R|}{|W_R|} = \frac{b}{w}$$
3. Condición de paridad del área Un requisito básico que sale de lo anterior para cubrir con dominós es que el área total $A$ debe ser par: $$A \equiv 0 \pmod 2$$
Teorema (Problema del tablero de ajedrez mutilado): Considera un tablero de ajedrez estándar de $8 \times 8$. Si quitas dos casillas de esquinas opuestas diagonalmente, la región que queda (que tiene 62 casillas) no se puede cubrir con dominós de $2 \times 1$.
Demostración:
Paso 1: Define la coloración Aplica la coloración estándar de tablero de ajedrez a la cuadrícula de $8 \times 8$, donde las casillas adyacentes tienen colores diferentes (negro y blanco). En un tablero normal de $8 \times 8$, hay: $$Total_{casillas} = 64$$ $$|B_{total}| = 32, \quad |W_{total}| = 32$$
Paso 2: Analiza las propiedades de las piezas Un dominó consiste en dos casillas de $1 \times 1$ adyacentes. En una cuadrícula coloreada como tablero de ajedrez, cualquier par de casillas adyacentes debe tener colores distintos. Por lo tanto, sin importar la posición o la orientación (horizontal o vertical), cada dominó que pongas en el tablero cubre exactamente: $$1 \text{ casilla Negra y } 1 \text{ casilla Blanca.}$$
Paso 3: Establece el invariante Si una región se puede cubrir con $k$ dominós, el número total de casillas negras cubiertas debe ser igual al número total de casillas blancas cubiertas, porque: $$\sum_{i=1}^{k} 1_{negra} = k \quad \text{y} \quad \sum_{i=1}^{k} 1_{blanca} = k$$ Así que, para cualquier región que se pueda cubrir con dominós, tienes que tener $|B| = |W|$.
Paso 4: Analiza la región mutilada El problema dice que se quitan dos esquinas opuestas diagonalmente. Supón que la esquina superior izquierda está en la posición $(1,1)$. Si $(1,1)$ es de color Blanco, entonces por el patrón alternado de la cuadrícula, la esquina opuesta en $(8,8)$ también tiene que ser Blanca. (Nota: En un tablero de $n \times n$, las esquinas opuestas son del mismo color si y solo si $n$ es par).
Las casillas que quitaste son ambas blancas. Calcula el conteo de colores para el tablero mutilado: $$|B_{nueva}| = |B_{total}| - 0 = 32$$ $$|W_{nueva}| = |W_{total}| - 2 = 30$$
Paso 5: Conclusión Nota que en la región mutilada: $$|B_{nueva}| = 32 \neq 30 = |W_{nueva}|$$ Como el número de casillas negras no es igual al número de casillas blancas, se rompe la condición del invariante que estableciste en el Paso 3. Por lo tanto, es imposible cubrir el tablero de ajedrez mutilado con dominós.
$\square$