LABERINTOS VERANIEGOS
El
viaje a Francia en pos del eclipse de agosto de 1999 permitió interesantes
visitas, como la de la catedral de Chartres, entre cuyas bellezas no ocupa el
último lugar su famoso laberinto, que recorrían los antiguos peregrinos como
etapa final de su viaje. En otras ocasiones hemos hablado y hablaremos en [C]
de los laberintos, pero quisiera referirme a otro problema, tampoco inédito en
nuestra revista, aunque enfocado hoy con una nueva perspectiva.
Se
trata de la inscripción SANCTAECLESIA, que aparece en el núcleo central del
laberinto de una antigua iglesia cristiana en Argel. Según la leyenda, también
los peregrinos recorrían las letras que la forman paso a paso hasta completar
las palabras. ¿De cuántas maneras se puede leer la inscripción? Para mayor
sencillez, consideraremos sólo la cuarta parte de los caminos, los que se
mueven sólo hacia el N derecha y hacia el E.
Solución
El
problema, así planteado, no revista una excesiva dificultad. Si, partiendo de
la S central, representamos cada paso con la letra respectiva de su dirección
(N o E), un camino cualquiera será equivalente a un esquema del tipo
NENN...EEN, en el que siempre habrán 6 N y 6 E. Es inmediato que el número de
combinaciones de este tipo es:
En términos generales, si es n el número de
letras a un lado:
Pero ahora viene la complicación. Supongamos que el
preboste del templo, para respetar la dirección de Jerusalén, prohíbe dar más
pasos hacia el N que hacia el E (dicho de otra forma, no puede sobrepasarse por
encima la diagonal SNTELSA). ¿Cuántos caminos posibles habrá entonces? Hay que
advertir que el problema reviste ahora mucha mayor dificultad, y son precisos
recursos del cálculo superior.
SOLUCIÓN AL PROBLEMA
SANCTAECLESIA
En este caso hay que recurrir a los llamados números
de Catalan, que aparecen en multitud de problemas combinatorios referidos a
descomposiciones de polígonos en triángulos, árboles plantados, caminos de torres
sobre el tablero de ajedrez, etc.
Los números de Catalan tienen como expresión
general:
Forman la sucesión:
1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796…
La solución es C6, o sea 132 caminos posibles.
Sin embargo, Andrés García Parrilla resolvió el
problema de una forma intuitivamente más atractiva. Veámosla:
Para
resolver el problema plantearemos una serie de problemas equivalentes y podemos
hallar la solución con cálculos
relativamente sencillos.
Utilizaré
un gráfico para simplificar la explicación. El gráfico representa (con un giro
de 45º en el sentido de las agujas del reloj) un camino desde la S inicial
hasta la A final de SANCTA ECLESIA. Así lo que antes era la diagonal ahora es
el eje horizontal.
Todos
los caminos posibles constan de 6 pasos arriba y 6 abajo; luego el número de
caminos distintos son 
.
La
restricción de que no debe superarse la diagonal es equivalente a no tocar la
línea de puntos horizontal. Podemos hallar el número de caminos que cumplen
esta condición restando del total el número de aquellos que no la cumplen.
En
el momento que un camino toque la línea de puntos (ver gráfico) podemos hacer
una simetría del resto del camino respecto a la línea de puntos.
Con
esta trasformación, el problema de hallar los caminos que tocan la línea de
puntos es equivalente a hallar los caminos que van desde la S inicial hasta A*
con 7 pasos arriba y 5 abajo.
Restando del total obtenemos la solución buscada:
Planteándolo
de un modo general para el caso de n pasos arriba y n abajo, o un cuadrado de
lado n (para acercarnos más al enunciado original del problema) la solución
general es:
que puede
simplificarse con unas simples manipulaciones matemáticas para llegar, como era
de esperar, a la fórmula mencionada por Josep Maria en el número anterior.
Andrés
García Parrilla