Cada dominó cubre un cuadro de cada color.
La técnica de demostración por coloración es un método combinatorio muy potente que se usa principalmente para determinar si un tablero o región específica se puede cubrir con un conjunto dado de piezas (como dominós, trominós o tetrominós). La idea fundamental es dividir las casillas del tablero en conjuntos disjuntos, asignándoles "colores" distintos para crear un invariante. Al analizar cómo una sola pieza interactúa con estos colores, puedes sacar condiciones necesarias para que exista un recubrimiento. Si el tablero no cumple con estas condiciones de conteo de colores, entonces el recubrimiento es imposible.
Esta técnica casi siempre se presenta con la coloración clásica de tablero de ajedrez (blanco y negro) para cubrir con dominós. En un tablero estándar, cualquier dominó de $2 \times 1$ que pongas horizontal o verticalmente tiene que cubrir exactamente una casilla negra y una blanca. Por lo tanto, para que una región se pueda cubrir con dominós, debe tener el mismo número de casillas negras que blancas. Si a una región le sobra un color, queda demostrado de inmediato que es imposible cubrirla.
Aunque el patrón estándar de 2 colores es suficiente para problemas simples de dominós, los problemas de competencias avanzadas (nivel AIME u Olimpiada) suelen requerir esquemas de coloración más complejos. Estos pueden usar 3, 4 o más colores, o patrones específicos (como franjas o diagonales) para detectar restricciones de paridad o invariantes de aritmética modular que un simple patrón de ajedrez no puede revelar. Por ejemplo, para determinar si un tablero se puede cubrir con piezas de $1 \times n$, muchas veces necesitas colorear la cuadrícula con $n$ colores donde el color de una casilla en $(i, j)$ depende de $(i+j) \pmod n$.
La Condición para Cubrir con Dominós Para que una región $R$ se pueda cubrir con dominós estándar de $2 \times 1$, una condición necesaria es: $$|B| = |W|$$ donde $|B|$ es el número de casillas negras y $|W|$ es el número de casillas blancas en la región usando una coloración de ajedrez estándar.
Invariante General de Recubrimiento Imagina que coloreas un tablero con un conjunto de colores $C$. Sea $n_c$ el número de casillas del color $c$ en el tablero. Si una sola pieza cubre $k_c$ casillas del color $c$, y el tablero se cubre con $N$ de esas piezas, entonces para cada color $c \in C$ se debe cumplir: $$n_c = N \cdot k_c$$
El Teorema del Tablero de Ajedrez Mutilado Para un tablero de $n \times n$ donde $n$ es par, si quitas dos casillas del mismo color, el tablero restante no se puede cubrir con dominós. $$\text{If } S = \text{Board} \setminus {s_1, s_2} \text{ and } \text{color}(s_1) = \text{color}(s_2), \text{ then } |B_S| \neq |W_S|.$$
Teorema: Es imposible cubrir un tablero de ajedrez de $8 \times 8$ al que se le quitaron dos esquinas opuestas usando dominós estándar de $2 \times 1$.
Demostración:
Define el tablero y la coloración: Considera un tablero de ajedrez estándar de $8 \times 8$ que tiene 64 casillas. Aplica la coloración alternada de blanco y negro. En esta configuración, el tablero tiene exactamente 32 casillas negras y 32 blancas. $$|B_{total}| = 32, \quad |W_{total}| = 32$$
Analiza el invariante del dominó: Un dominó estándar cubre dos casillas adyacentes. En un tablero de ajedrez, cualquier par de casillas adyacentes siempre tiene colores distintos. Por lo tanto, cada dominó que pongas en el tablero cubre exactamente una casilla negra y una blanca.
Si una región se puede cubrir con $k$ dominós, el número total de casillas negras cubiertas debe ser $k \times 1 = k$, y el número total de casillas blancas cubiertas debe ser $k \times 1 = k$. Así que, una condición necesaria para que cualquier región se pueda cubrir con dominós es que el número de casillas negras sea igual al número de casillas blancas.
Analiza el tablero mutilado: El problema dice que se quitan dos esquinas opuestas. En una coloración de ajedrez estándar, las esquinas opuestas (por ejemplo, la superior izquierda en $(1,1)$ y la inferior derecha en $(8,8)$) siempre son del mismo color. Sin perder generalidad, supón que ambas esquinas son negras.
Sea $S'$ el conjunto de casillas del tablero mutilado. Calcula el número de casillas que quedan de cada color: $$|B_{S'}| = 32 - 2 = 30$$ $$|W_{S'}| = 32 - 0 = 32$$
Conclusión: Para que el tablero $S'$ se pueda cubrir con dominós, necesitas que $|B_{S'}| = |W_{S'}|$. Sin embargo, viste que: $$30 \neq 32$$ Como el número de casillas negras no es igual al número de casillas blancas, es imposible emparejarlas una a una usando dominós. Por lo tanto, no existe tal recubrimiento.
$\square$