Usar colores para problemas de pavimentación.
Los argumentos de dominó en tableros son un tipo de pruebas combinatorias que sirven para determinar si una cuadrícula o forma se puede cubrir perfectamente con dominós (rectángulos de $2 \times 1$). La técnica principal se basa en invariantes que estableces al colorear la cuadrícula, casi siempre con el patrón estándar de "tablero de ajedrez" donde los cuadros blancos y negros se alternan. Esta técnica convierte un problema geométrico de teselado en uno de conteo numérico, lo que permite hacer demostraciones elegantes de imposibilidad.
La idea clave es que un solo dominó puesto en un tablero siempre tiene que cubrir exactamente un cuadro negro y un cuadro blanco, sin importar si lo pones horizontal o vertical. Por lo tanto, si puedes cubrir una región perfectamente con dominós, el conjunto de cuadros cubiertos debe tener la misma cantidad de cuadros negros que de blancos. Esto te da una condición necesaria muy potente: si una región tiene un número diferente de cuadros negros y blancos, no hay forma de cubrirla con dominós.
Aunque lo más común es usar el coloreado estándar de blanco y negro, puedes generalizar esta técnica para demostrar que no se pueden usar otras piezas (como los trominós) usando más colores o patrones complejos. En las olimpiadas de matemáticas (como el AMC 12 o el AIME), estos argumentos se aplican mucho en tableros "mutilados" —tableros normales a los que les quitas cuadros específicos— para demostrar que no existe un teselado sin tener que revisar cada combinación posible.
1. El Invariante del Tablero Para que una región $R$ se pueda cubrir con dominós, supón que $N_B$ es el número de cuadros negros y $N_W$ es el número de cuadros blancos usando el coloreado estándar. Una condición necesaria para un teselado perfecto es: $$N_B = N_W$$
2. El Teorema del Tablero Mutilado Para un tablero de $n \times n$ (donde $n$ es par) al que le quitas dos esquinas diagonalmente opuestas, los $n^2 - 2$ cuadros restantes no se pueden cubrir con dominós.
3. Formulación de Emparejamiento Bipartito Una región se puede cubrir con dominós si y solo si el grafo bipartito $G = (U, V, E)$ —donde $U$ representa los cuadros negros, $V$ los blancos y las aristas conectan cuadros adyacentes— tiene un emparejamiento perfecto. Por el Teorema de Matrimonio de Hall, para cualquier subconjunto $S \subseteq U$: $$|N(S)| \geq |S|$$ donde $N(S)$ es el conjunto de vecinos de $S$ en $V$.
4. Conteo de Teselados para $2 \times n$ El número de formas $T_n$ de cubrir un tablero de $2 \times n$ con dominós viene dado por la sucesión de Fibonacci: $$T_n = F_{n+1}$$ donde $F_1 = 1, F_2 = 1, F_3 = 2, \dots$
Teorema: Es imposible cubrir un tablero de ajedrez de $8 \times 8$ al que se le quitaron dos esquinas diagonalmente opuestas usando dominós estándar de $2 \times 1$.
Demostración:
Paso 1: Define el tablero y el coloreado Imagina un tablero de ajedrez estándar de $8 \times 8$ que tiene 64 cuadros. Aplica el coloreado normal donde los cuadros adyacentes son de colores distintos (negro y blanco). En un tablero completo de $8 \times 8$, tienes: $$N_{total} = 64$$ $$N_B = 32 \quad (\text{Cuadros negros})$$ $$N_W = 32 \quad (\text{Cuadros blancos})$$
Paso 2: Analiza los cuadros eliminados Quita dos esquinas diagonalmente opuestas. En un patrón de tablero normal, las esquinas opuestas siempre son del mismo color. Sin perder generalidad, supón que la esquina superior izquierda es blanca. Entonces la esquina inferior derecha también tiene que ser blanca.
Paso 3: Cuenta los cuadros que quedan Después de quitar estos dos cuadros blancos, la composición de la región $R$ que queda es: $$N_W' = 32 - 2 = 30$$ $$N_B' = 32 - 0 = 32$$ El número total de cuadros restantes es $30 + 32 = 62$.
Paso 4: Analiza las propiedades del dominó Un dominó cubre dos cuadros adyacentes. En un tablero, cualquier par de cuadros adyacentes debe tener colores distintos. Por lo tanto, cualquier dominó que pongas en el tablero cubre exactamente: $$1 \text{ cuadro negro y } 1 \text{ cuadro blanco.}$$
Paso 5: Encuentra la contradicción Supón, para llegar a una contradicción, que sí existe un teselado perfecto. Como hay 62 cuadros, necesitarías exactamente 31 dominós. Sea $k$ el número de dominós usados. El número total de cuadros negros cubiertos sería $1 \cdot k = k$. El número total de cuadros blancos cubiertos sería $1 \cdot k = k$.
Esto implica que para que exista un teselado, la región debe cumplir que $N_B' = N_W'$. Sin embargo, por el Paso 3, tienes que: $$N_B' = 32 \neq 30 = N_W'$$
Como el número de cuadros negros no es igual al de cuadros blancos, es imposible emparejarlos uno a uno usando dominós. Por lo tanto, no existe tal teselado.
$\square$