Teselar con dominós

El ejemplo que consideramos aquí es el de las teselaciones de una región del plano con fichas de dominó de tamaño $ 2 \times 1 $. Las reglas para el mosaico son las siguientes : las fichas de dominó deben ocupar toda el área y no deben superponerse. ¿Existe una tendencia general para todas las formas de pavimentar una gran región ?

Ciertamente, no siempre es posible pavimentar una región determinada. Una condición necesaria es claramente que la región sea la unión de un número par de cuadrados del lado 1. Pero incluso hay áreas del plano que cumplen con esta condición y que no se pueden pavimentar con dominó.

Teselado aleatorio

Cuando una región del plano se puede pavimentar con dominós, generalmente hay una gran cantidad de formas posibles de colocarlos. Para conocer la forma típica en que se organizan las fichas de dominó, es deseable poder hacer un sorteo para el pavimento. Pongamos todas las teselas posibles en un sombrero, mezclemos bien y saquemos una sin mirar. A esto se le llama empate equiprobable : todos los mosaicos tienen la misma probabilidad de ser elegidos.
Pero en la práctica, tal enumeración de todas las teselaciones es irrealizable, pues el número de teselaciones posibles aumenta extremadamente rápido con el tamaño de la región a embaldosar.

Por esta razón, los matemáticos han desarrollado algoritmos que permiten llevar a cabo un experimento de este tipo sin recurrir a un sombrero. El más conocido usa el enlace con ’’árboles cubrientes’’ [2] y el algoritmo de David Wilson [3] para generar los objetos deseados.

Presentaremos aquí otro método, llamado de ’’revoltura de dominós’’ (domino shuffling), para generar embaldosados aleatorios. Este ha sido desarrollado para una forma particular de región, el diamante azteca, pero puede ser generalizado para realizar otros tipos de embaldosados.

El algoritmo de la revoltura de dominós

Estos son los diamantes aztecas de orden 1, 2, 3 y 6 :

Diamantes aztecas de orden 1, 2, 3 y 6

Claramente, hay dos maneras de teselar el diamante de orden 1 :

Para el diamante de orden 2, podemos aún recurrir a nuestro sombrero de probabilidades. Así, vemos que hay una posibilidad sobre 8 de sacar de allí uno de los embaldosados siguientes :

Diamante azteca de orden 2

Los 8 embaldosados posibles.

También se podrían enumerar todas las teselaciones del diamante de tercer orden, aunque esto ya empieza a ser difícil. Pero para el diamante de orden 4, ya no es razonable construir todas las teselaciones posibles a mano : hay 1024 diferentes. En general, se puede demostrar que hay exactamente $ 2^{n (n + 1) / 2} $ formas de pavimentar un diamante de orden $ n $. Para el diamante de orden 100, hay $ 2^{5050} $ teselaciones posibles : ¡un número que tiene más de 1,500 dígitos !

Podemos pasar fácilmente de un diamante azteca de orden $ n-1 $ a uno de orden $ n $ : basta con añadir una capa adicional a su alrededor. Es esta propiedad geométrica la que hace posible construir un pavimento aleatorio de un diamante grande, mediante la construcción sucesiva de pavimentos de diamantes más pequeños : comenzamos con el diamante de primer orden lanzando una moneda al cara y sello para decidir la orientación de las dos fichas de dominó (ambas horizontales o ambas verticales). Luego, construimos sucesivamente mosaicos de diamantes de orden 2, 3, 4, ... hasta el orden deseado. El paso de un mosaico de orden $ n-1 $ a otro de orden $ n $ se realiza moviendo localmente las fichas de dominó (de ahí el nombre del algoritmo). A menudo surge una elección de orientación de las fichas de dominó : cada vez que este es el caso, tiramos una moneda para decidir. Al proceder de esta manera, obtenemos en cada paso un mosaico elegido por igual entre todos los mosaicos del mismo tamaño.

Las siguientes animaciones presentan etapas sucesivas de la ejecución del algoritmo de revoltura para los diamantes aztecas de orden 10 y luego 100.

Algoritmo de revoltura de dominós

Estapas sucesivas del algoritmo para la generación de un teselado del diamante de orden 10. Cada teselado aparece de manera equiprobable entre todos los teselados posibles.

El mismo algoritmo ejecutado para el diamante de orden 100

El fenómeno del círculo ártico

Si se lanza al azar uno de los teselados posibles de un diamante de orden suficientemente grande (como se muestra en la animación de abajo), se ve aparecer con una probabilidad próxima a 1 el famoso círculo ártico [4] : en el exterior del círculo inscrito del diamante, las fichas de dominó están todas ’’congeladas’’ en la misma dirección, mientras que en el interior reina el desorden.

El fenómeno del círculo ártico para el embaldosado aleatorio del diamante azteca es de especial interés : en este modelo, los efectos de borde se propagan a una gran distancia del límite del dominio y, por lo tanto, son visibles a escala macroscópica. Este no es el caso del cuadrado, por ejemplo.

Efecto del borde

A izquierda : un embaldosado típico del diamante azteca de orden 100 sobre el cual se observa el fenómeno de círculo ártico. A derecha : un embaldosado típico del cuadrado de lado 60.

Teselado aleatorio de otras regiones del plano : el algoritmo de la revoltura con pesos

Al aplicar el algoritmo de la revoltura, es necesario lanzar una moneda para pasar de un diamante de orden $ n-1 $ a un diamante de orden $ n $. Naturalmente, utilizamos una moneda equilibrada para decidir entre las dos posibles formas de orientar determinadas fichas de dominó, pues no queremos favorecer una dirección sobre la otra. Pero hay una versión [5] más sofisticada del algoritmo que favorece o desfavorece determinadas colocaciones de dominó. Asociamos un peso con cada posible posición de un dominó : la posición será tanto más favorecida cuanto más importante sea el peso. A continuación, los sorteos se realizan con piezas sesgadas (que favorecen o perjudican a las caras).

De hecho, incluso es posible prohibir la colocación de dominó en determinados lugares asignándoles un peso cero [6]. Esto es lo que se hizo para obtener un teselado aleatorio del cuadrado de lado 60 que se muestra arriba. Este ha sido ’’insertado’’ en un diamante azteca, y se ha prohibido ciertos posicionamientos de los dominós.

Fuera del cuadrado, las fichas de dominó deben disponerse todas de la misma manera (horizontalmente en la parte inferior y superior, y verticalmente a derecha e izquierda). Con la ayuda del algoritmo de la revoltura, obtenemos un mosaico aleatorio equiprobable del cuadrado.

Por supuesto, se puede hacer lo mismo para pavimentar un rectángulo (cuyo ancho o largo sea par) o alguna otra región de forma más complicada. Incluso podemos divertirnos asignando pesos según la intensidad de los píxeles de una fotografía. Esto es lo que da :

Teselados con pesos

Teselado aleatorio de un cuadrado cuando las orientaciones se ponderan en función de la intensidad de los píxeles de una foto.

Otros teselados aleatorios

Es posible hacer mosaicos con formas distintas al dominó utilizando el algoritmo del revolvedor : por ejemplo, alicatar un hexágono con diamantes. La idea es reemplazar la celosía cuadrada, que es en cierto modo el ’’esqueleto’’ del diamante azteca, por otra celosía regular : la celosía hexagonal (arriba a la derecha), la celosía cuadrado-octógono (abajo a la izquierda), o la red hecha de cuadrados, hexágonos y octógonos (abajo a la derecha).

Un teselado típico del hexágono con ayuda de diamantes hace aparecer un fenómeno similar al círculo ártico en el diamante azteca.

Teselado aleatorio de un hexágono

Las otras redes presentadas anteriormente dan lugar a mosaicos en los que aparecen simultáneamente mosaicos de diferentes formas (cuadrados, triángulos, etc.). La siguiente figura presenta dos mosaicos aleatorios obtenidos de estas redes (con detalles de los mosaicos dentro de los discos).

Se observa nuevamente sobre estos teselados un fenómeno de congelemiento de los bordes, pero no se sabe aún cómo identificar la forma de la parte congelada.