Tableros y caminos en cuadrículas

Caminos en cuadrículas sin obstáculos

Un problema clásico: ¿cuántos caminos hay desde la esquina inferior izquierda $(0,0)$ hasta la esquina superior derecha $(m,n)$ de una cuadrícula, si solo se puede mover hacia la derecha (D) o hacia arriba (A)?

Todo camino consiste en exactamente $m$ movimientos D y $n$ movimientos A, en total $m + n$ movimientos. El camino queda determinado eligiendo en qué $m$ de los $m+n$ pasos se mueve a la derecha. Luego el número de caminos es $\binom{m+n}{m}$.

Recurrencia alternativa: sea $f(i,j)$ el número de caminos de $(0,0)$ a $(i,j)$. Como el último movimiento fue D (llegando desde $(i-1,j)$) o A (llegando desde $(i,j-1)$):

$f(i,j) = f(i-1,j) + f(i,j-1)$, con $f(i,0) = f(0,j) = 1$.

Esta es la recurrencia del triángulo de Pascal: $f(i,j) = \binom{i+j}{i}$. El triángulo de Pascal y las cuadrículas son la misma estructura combinatoria vista desde ángulos distintos.

Caminos con un obstáculo: el principio de reflexión

Ahora supongamos que cierto punto $(a,b)$ del interior está bloqueado (no se puede pasar por él). ¿Cuántos caminos de $(0,0)$ a $(m,n)$ evitan $(a,b)$?

Respuesta directa: total de caminos $-$ caminos que pasan por $(a,b)$.

Los caminos que pasan por $(a,b)$ son los que van de $(0,0)$ a $(a,b)$ multiplicados por los que van de $(a,b)$ a $(m,n)$: $\binom{a+b}{a} \cdot \binom{(m-a)+(n-b)}{m-a}$.

Luego los caminos que evitan $(a,b)$ son $\binom{m+n}{m} - \binom{a+b}{a}\binom{m+n-a-b}{m-a}$.

Este razonamiento se generaliza a múltiples obstáculos usando el PIE: restar los caminos que pasan por algún obstáculo, sumar los que pasan por dos obstáculos a la vez, etc.

Caminos de Catalan: no cruzar la diagonal

Un camino de Catalan (o camino de Dyck) de longitud $2n$ es un camino de $(0,0)$ a $(n,n)$ que nunca cruza por debajo de la diagonal principal (es decir, nunca tiene más pasos A acumulados que pasos D acumulados en ningún prefijo). El número de tales caminos es el $n$-ésimo número de Catalan:

$C_n = \frac{1}{n+1}\binom{2n}{n}$.

Los primeros valores son $C_0 = 1$, $C_1 = 1$, $C_2 = 2$, $C_3 = 5$, $C_4 = 14$, $C_5 = 42$.

Prueba por reflexión (de André, 1887): el número de caminos "malos" de $(0,0)$ a $(n,n)$ que tocan la línea $y = x + 1$ (cruzan la diagonal) es igual al número total de caminos de $(-1, 1)$ a $(n, n)$, que es $\binom{2n}{n-1}$. Luego:

$C_n = \binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n+1}\binom{2n}{n}$.

Los números de Catalan cuentan también: triangulaciones de polígonos convexos, expresiones con paréntesis balanceados, árboles binarios, y muchas otras estructuras. En problemas olímpicos aparecen siempre que hay una condición de "no cruzar" o "no exceder".

Recurrencias en tableros: coberturas y coloraciones

Los tableros $1 \times n$ ya aparecieron en la lección 6.1 (coberturas con fichas). Para tableros $2 \times n$, el conteo de coberturas con fichas $1 \times 2$ (dominós) también satisface una recurrencia. Sea $T_n$ el número de coberturas del tablero $2 \times n$ con dominós.

Si el último dominó cubre las columnas $n-1$ y $n$ en horizontal (dos dominós horizontales, uno arriba y otro abajo), queda el tablero $2 \times (n-2)$ por cubrir: $T_{n-2}$ opciones. Si el último dominó es vertical (cubre las dos casillas de la columna $n$), queda el tablero $2 \times (n-1)$: $T_{n-1}$ opciones. Luego $T_n = T_{n-1} + T_{n-2}$, con $T_0 = 1$ y $T_1 = 1$. Estos son los números de Fibonacci: $T_n = F_{n+1}$.

Para coloraciones de tableros con restricciones (por ejemplo, no dos casillas adyacentes del mismo color), también se establecen recurrencias similares según el "estado" de la última columna o fila.

La estrategia unificadora: definir el "estado" que resume la información necesaria de la configuración parcial, y escribir la recurrencia en términos de los estados posibles. Si hay $k$ estados posibles, la recurrencia tiene $k$ variables y puede representarse como una multiplicación de matrices (técnica de nivel superior, pero la idea es accesible desde el nivel regional).

Problemas de caminos con obstáculos múltiples y recurrencias

Cuando hay una "barrera" diagonal (por ejemplo, el camino no puede tocar la recta $y = x + k$), el número de caminos satisface una recurrencia que se puede calcular paso a paso.

Ejemplo: ¿cuántos caminos hay de $(0,0)$ a $(4,4)$ en la cuadrícula usando solo movimientos D y A, sin cruzar la recta $y = x + 1$ (es decir, sin que el número de pasos A supere al número de pasos D en ningún momento)? Este es exactamente $C_4 = 14$.

Para resolver con recurrencia en lugar de la fórmula de Catalan: define $f(i,j)$ como el número de caminos de $(0,0)$ a $(i,j)$ que satisfacen la restricción $j \le i$ en todo punto. La restricción impone $f(i,j) = 0$ cuando $j > i$. Los casos base y la recurrencia $f(i,j) = f(i-1,j) + f(i,j-1)$ (con el cero forzado cuando $j > i$) permiten llenar la tabla. Este método es completamente elemental y eficiente para problemas olímpicos con restricciones complicadas.

Principio general: cuando la fórmula cerrada no es obvia, construye la tabla de valores con la recurrencia. Para tableros de tamaño olímpico ($n \le 10$ habitualmente), calcular la tabla a mano es factible y da la respuesta exacta.