Teselaciones con Dominós

Teoría

Las teselaciones con dominós son un problema combinatorio que trata sobre cubrir una cuadrícula (normalmente un subconjunto de la cuadrícula entera $\mathbb{Z}^2$, como un rectángulo de $m \times n$) usando rectángulos de $1 \times 2$, conocidos como dominós. Para que una teselación sea válida, cada cuadrado de la cuadrícula debe estar cubierto por exactamente un dominó, sin que se encimen y sin que los dominós se salgan de los bordes. Este tema sirve de puente entre la teoría de gráficas y la combinatoria; en términos de teoría de gráficas, una teselación con dominós de una gráfica de cuadrícula corresponde a un matching perfecto de esa gráfica.

Las dos estrategias principales para resolver problemas de teselaciones con dominós en competencias como el AMC 12 y el AIME son los argumentos de coloración y la recursión. Los argumentos de coloración (específicamente la coloración de tablero de ajedrez) te dan invariantes muy potentes. Como un dominó siempre cubre un cuadrado negro y uno blanco, una condición necesaria para que una región se pueda teselar es que debe tener el mismo número de cuadrados negros y blancos. Esta técnica es esencial para demostrar que ciertas figuras (como un tablero de ajedrez al que se le quitaron esquinas opuestas) no se pueden cubrir.

Para contar el número de teselaciones válidas, el enfoque estándar son las relaciones de recurrencia. Si analizas cómo se comporta una teselación en el borde del tablero, puedes expresar el número de teselaciones para un tablero de tamaño $n$ en términos de tableros de tamaño $n-1$ y $n-2$. Esto suele llevarte a conexiones con sucesiones famosas, como los números de Fibonacci para cuadrículas de $2 \times n$. En contextos más avanzados, se usa el álgebra lineal y los números complejos (el método de Kasteleyn) para contar teselaciones en cuadrículas de tamaños arbitrarios.

Fórmulas Clave

1. Condiciones Necesarias para la Existencia Para que una región $R$ de la cuadrícula tenga una teselación con dominós, se debe cumplir lo siguiente:

• Paridad del Área: El número total de cuadrados $|R|$ tiene que ser par.
• Invariante de Coloración: Si coloreas la cuadrícula como un tablero de ajedrez, el número de cuadrados negros ($N_B$) debe ser igual al número de cuadrados blancos ($N_W$): $$ N_B = N_W $$

2. Conteo de Teselaciones en un Tablero de $2 \times n$ Sea $T_n$ el número de formas de cubrir un rectángulo de $2 \times n$. La sucesión cumple con la recurrencia de Fibonacci: $$ T_n = T_{n-1} + T_{n-2} $$ Con los casos base $T_1 = 1$ and $T_2 = 2$. (Nota: $T_n = F_{n+1}$ donde $F_n$ es la sucesión de Fibonacci estándar que empieza $1, 1, 2...$).

3. Conteo de Teselaciones en un Tablero de $3 \times n$ Sea $U_n$ el número de formas de cubrir un rectángulo de $3 \times n$.

• Si $n$ es impar, $U_n = 0$.
• Si $n$ es par, sea $n=2k$. El número de teselaciones cumple: $$ U_{2k} = 4U_{2k-2} - U_{2k-4} $$ Con los casos base $U_0 = 1$ y $U_2 = 3$.

4. Fórmula de Temperley-Fisher (Cuadrícula General de $m \times n$) El número de teselaciones con dominós distintas de una cuadrícula de $m \times n$ está dado por: $$ \prod_{j=1}^{\lceil m/2 \rceil} \prod_{k=1}^{\lceil n/2 \rceil} 4 \left( \cos^2 \frac{j\pi}{m+1} + \cos^2 \frac{k\pi}{n+1} \right) $$

Demostración

Teorema: El número de formas de cubrir un rectángulo de $2 \times n$ con dominós de $1 \times 2$, denotado como $T_n$, cumple la relación de recurrencia $T_n = T_{n-1} + T_{n-2}$.

Demostración: Usa un argumento de conteo constructivo basado en el extremo derecho del rectángulo de $2 \times n$.

Imagina que el rectángulo está definido en los puntos de la cuadrícula ${(x,y) : 1 \le x \le n, 1 \le y \le 2}$. Considera las posibles configuraciones de los dominós que cubren la última columna (la columna $n$).

Paso 1: Analiza la columna del extremo derecho. Solo hay dos formas de cubrir los cuadrados en la columna $n$:

1. Colocación vertical: Un solo dominó vertical cubre las posiciones $(n, 1)$ y $(n, 2)$.
2. Colocación horizontal: Se apilan dos dominós horizontales. Uno cubre $(n-1, 1)$ y $(n, 1)$, y el otro cubre $(n-1, 2)$ y $(n, 2)$. Nota que no puedes tener solo un dominó horizontal terminando en la columna $n$ sin el otro, ya que eso dejaría un hueco de $1 \times 1$ en la columna $n-1$, el cual no se podría llenar con un dominó.

Paso 2: Establece la relación recursiva.

• Caso 1 (Vertical): Si pones un dominó vertical en la columna $n$, el área que queda por cubrir es un rectángulo de $2 \times (n-1)$. Por definición, hay $T_{n-1}$ formas de cubrir lo que sobra.
• Caso 2 (Horizontal): Si pones dos dominós horizontales cubriendo las columnas $n-1$ y $n$, el área que queda por cubrir es un rectángulo de $2 \times (n-2)$. Por definición, hay $T_{n-2}$ formas de cubrir lo que sobra.

Como estos dos casos son mutuamente excluyentes y cubren todas las configuraciones válidas para el borde derecho, el número total de teselaciones es la suma de los conteos de estos casos: $$ T_n = T_{n-1} + T_{n-2} $$

Paso 3: Verifica los casos base.

• Para $n=1$: Un tablero de $2 \times 1$ es simplemente un dominó vertical. $T_1 = 1$.
• Para $n=2$: Un tablero de $2 \times 2$ se puede cubrir con dos dominós verticales o dos dominós horizontales. $T_2 = 2$.

Si checas la recurrencia para $n=3$: $T_3 = T_2 + T_1 = 2 + 1 = 3$. (Las teselaciones son: tres verticales; dos horizontales a la izquierda + una vertical; una vertical + dos horizontales a la derecha). Esto se cumple.

Por lo tanto, el número de teselaciones sigue la recurrencia $T_n = T_{n-1} + T_{n-2}$. $\square$