De los laberintos a las matemáticas
El hecho básico que permite el estudio matemático de los laberintos de tránsito simple alternante es el siguiente. La topología de un laberinto de tránsito alterno simple está completamente determinada por su secuencia de niveles. Más adelante se explica cómo funciona esto; significa que si dos laberintos de t.a.s. (digamos, ambos en forma desenrollada) tienen la misma secuencia de niveles, entonces uno puede cambiarse para que coincida con el otro, o con la imagen especular del otro mediante una deformación continua que preserve el nivel.
De ello se deduce que una clasificación topológica completa de los laberintos de tránsito alterno simple equivale a determinar qué secuencias de números pueden aparecer como secuencias de nivel y, de hecho, hay tres condiciones que son necesarias y suficientes para que una permutación de los números de 0 a n sea la secuencia de nivel de un laberinto s.a.t. de profundidad n.
- La secuencia debe empezar por 0 y terminar por n.
- Los números enteros pares e impares deben alternarse en la secuencia.
- Considere los pares de números consecutivos en la secuencia de niveles que comienzan con un número par; éstos corresponden a los segmentos verticales en el lado derecho del laberinto. (*)Si dos de estos segmentos se superponen, uno debe estar anidado dentro del otro. Lo mismo ocurre con los pares que comienzan con un número impar, que corresponden a los segmentos verticales de la izquierda.
Ejemplo: en la secuencia de niveles del laberinto de Constantinopla, los segmentos (10,1) y (2,11) se solapan, pero ninguno está anidado en el otro, por lo que no puede tratarse de la secuencia de niveles de un laberinto s.a.t..
He aquí cómo se demuestra esto:
Necesidad de 1: obvia.
Necesidad de 2: Supongamos que dos capas consecutivas unidas por un segmento vertical a la derecha, por ejemplo, tienen la misma paridad; el espacio entre ellas debe tener un número impar de niveles. Cualquier camino que atraviese ese espacio debe entrar y salir por la izquierda, por lo que sólo puede utilizar un número par de niveles. Contradicción.
Necesidad de 3: Piensa en el laberinto desenrollado, con la entrada, digamos, a la derecha. El camino comienza a la derecha en el nivel 0 y desciende hasta un nivel impar. Luego cruza a la izquierda y pasa al siguiente nivel de la secuencia, que será par, luego vuelve a cruzar a la derecha, etc. Así, los pares de números consecutivos de la secuencia de niveles que empiezan por un número par corresponden a los segmentos verticales de la derecha del laberinto, y los que empiezan por un número impar, a los segmentos de la izquierda. Consideremos ahora dos segmentos verticales cualesquiera del camino de la derecha. Si se solapan, uno debe estar anidado dentro del otro. De lo contrario, no podrían conectarse ambos al lado izquierdo mediante segmentos horizontales, ya que el camino del laberinto no puede intersecarse a sí mismo; y lo mismo debe ocurrir con los segmentos del camino vertical de la izquierda.
Suficiencia: Supongamos dada una permutación de los enteros de 0 a n, que satisfaga las condiciones 1, 2 y 3. He aquí cómo convertirla en un laberinto. En un trozo de papel rayado, numera las líneas de 0 a n, empezando por arriba. Para cada uno de los pares consecutivos de números enteros de la secuencia que empiece por un número par, une las líneas numeradas correspondientes con un segmento vertical en la parte derecha de la página. Si dos de estos segmentos están anidados, dibuja el más corto a la izquierda del más largo. Ahora haz lo mismo con los pares que comienzan impares, excepto en el lado izquierdo, con los segmentos más cortos colocados a la derecha. Ahora, en cada una de las líneas numeradas 1,...,n-1 habrá dos extremos libres de la figura. Únelos a lo largo de esa línea; esto deja un extremo libre arriba y otro abajo. Habrás dibujado el hilo de Ariadna de la forma desenrollada del laberinto s.a.t. correspondiente a la secuencia de niveles con la que empezaste. Ahora es fácil dibujar el laberinto propiamente dicho. Además, con sólo dibujar la parte del laberinto cercana a los bordes derecho e izquierdo de la página, y unir estas dos piezas a lo largo de sus espinas exteriores, se produce el núcleo a partir del cual se puede dibujar la forma enrollada.
Tony Phillips
Departamento de Matemáticas SUNY Stony Brook
tony at math.stonybrook.edu
5 de junio de 2018
Original article: https://www.math.stonybrook.edu/~tony/mazes/levelseq.html
