Teselados aleatorios por revoltura de dominós

Pista azul El 17 febrero 2009  - Escrito por  Thierry de la Rue , Élise Janvresse
El 31 agosto 2021  - Traducido por  Andrés Navas
Artículo original : Pavages aléatoires par touillage de dominos Ver los comentarios
Leer el artículo en  

La física estadística se ocupa del estudio a gran escala de sistemas formados por una inmensa cantidad de componentes microscópicos. Una cuestión fundamental es saber cómo se organiza esta multitud de elementos según las limitaciones que se les imponen: ¿qué lugar se deja al azar?; ¿qué comportamiento observamos a escala macroscópica? Experimentar en esta área requiere poder generar configuraciones típicas utilizando algoritmos que simulen los efectos del azar.

Un embaldosado imposible

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ó.


Una región impossible de teselar

PNG - 4.4 KB
Un embaldosado imposible
Es imposible embaldosar el tablero astillado (de 62 casillas) con 32 dominós.

Este es un ejemplo de mosaico imposible: queremos teselar con fichas de dominó de tamaño $ 2 \times 1 $ el tablero de ajedrez de tamaño $ 8 \times 8 $ ’’astillado": hemos eliminado los cuadrados de dos esquinas opuestas. La superficie a cubrir es la unión de un número par de cuadrados del lado 1 ($ 8 \times 8 - 2 = 62 $). ¡Pero es imposible embaldosarla! En efecto, cualquiera que sea la forma en que se coloque una pieza de dominó, esta cubre una casilla negra y una blanca. Sin embargo, el tablero de ajedrez astillado contiene más casillas blancas (32) que negras (30). Por lo tanto, es imposible pavimentarlo con nuestras fichas de dominó.

PNG - 1.3 KB
Encore une figure non pavable
Et pourtant elle contient autant de cases noires que de cases blanches.

Debemos señalar, sin embargo, que la igualdad entre el número de celdas blancas y negras es necesaria, pero no suficiente, como lo prueba el ejemplo de la derecha. Para obtener más información sobre la condición de pavimentación con dominós, consulte [1].

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:

PNG - 2.4 KB
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:

PNG - 3.1 KB
Diamante azteca de orden 2
Los 8 embaldosados posibles.

¿Por qué nuestros dominós son de cuatro colores diferentes?

Para representar los mosaicos, usamos una convención de colores que permite distinguir 4 posibles tipos de colocación de un dominó. Primeramente, hay una distinción entre dominó horizontal y vertical, y en cada una de estas orientaciones hay dos formas de colocar el dominó: habiendo coloreado los cuadrados del diamante como un tablero de ajedrez, diferenciamos los dominós horizontales que cubren un cuadrado blanco a izquierda de los que cubren un recuadro blanco a derecha (y lo mismo para los verticales, según si el recuadro blanco está arriba o abajo). Este uso de colores se hace necesario para poder apreciar a escala macroscópica las tendencias de organización del embaldosado (ver el fenómeno del círculo ártico descrito a continuación).


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.


Detalle del algoritmo

¿Cómo pasar de un diamante de orden $ n-1 $ a uno de orden $ n $? Para esto, necesitamos la noción de celda activa. Una celda es un cuadrado de $ 2 \times 2 $ contenida en el diamante. Habiendo coloreado las casillas del diamante como en un tablero de ajedrez, podemos distinguir dos tipos de celdas: aquellas cuya casilla en la parte superior izquierda es negra y aquella para las que es blanca. Todas las celdas que tocan el borde son del mismo tipo.
Por ejemplo, en el diamante de orden 2, el cuadro de la parte superior izquierda es blanco (y este es el caso de todos los diamantes de orden par).
Diremos que una celda está activa si es del mismo tipo que las del borde.

PNG - 2 KB
Células activas
A izquierda: una de las 4 células activas del diamante de orden 2.
A derecha: 3 de las 9 células activas del diamante de orden 3.

Comenzamos con un diamante de orden $ n-1 $ y agregamos una capa de casillas para insertarlo en un diamante de orden $ n $. Considere una de las celdas activas del diamante grande y las fichas de dominó que contiene completamente. Si ella está cubierta por dos fichas de dominó enteras, entonces las dos fichas de dominó se eliminan. Si contiene exactamente un dominó completo, lo movemos al otro lado de la celda. Si no contiene ningún dominó completo, lo cubrimos con dos dominós, eligiendo al azar su orientación.

PNG - 2.7 KB
Efecto de la revoltura
Ejemplos de células activas que contienen 2, 1 o 0 dominós enteros.

A priori, no es evidente que se pueda aplicar este proceso simultáneamente a cada una de las $n^2$ células activas del diamante de orden $n$, puesto que estas se superponen unas con otras. Sin embargo, siempre es posible, y esto da lugar a un diamante de orden $n$.

PNG - 3 KB
Paso de un embaldosado del diamante de orden 2 a uno del diamante de orden 3.
A derecha, se ha tirado al azar las orientaciones de los dominós en las células activas de borde punteado.

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

GIF - 76.2 KB
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.
GIF - 1.8 MB
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.

PNG - 251.4 KB
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:

GIF - 475.6 KB
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).


Emparejamientos perfectos de un grafo

Para comprender la transición a otros tipos de teselaciones, necesitamos la noción de coincidencia perfecta de un grafo. Asociamos un grafo a una región formada por casillas: los vértices son los centros de cada casilla, y dos vértices pertenecientes a casillas que tienen un lado común están conectados entre sí por una arista.

Cada arista del grafo corresponde a una posible ubicación de un dominó. Partiendo de una teselación de la región por dominós, consideramos el conjunto de aristas asociadas: obtenemos así un acoplamiento perfecto del grafo, es decir, una colección de aristas que cubren una y solo una vez cada vértice del grafo. Recíprocamente, a cualquier acoplamiento perfecto del grafo corresponde una teselación por dominós.

PNG - 3.7 KB
Relación entre un teselado del diamante de orden 3 y un acoplamiento perfecto del grafo asociado.

Asignar un peso cero a una posición de dominó equivale a borrar el borde correspondiente en el grafo. El algoritmo del revolvedor con peso permite obtener un acoplamiento perfecto de los subgrafos del grafo asociado con el diamante azteca. A priori, esto puede funcionar incluso con diferentes grafos. Por ejemplo, el grafo asociado con la celosía hexagonal a continuación puede identificarse con un subgrafo de un diamante azteca lo suficientemente grande.

PNG - 37.5 KB
Red hexagonal
A izquierda: un grafo representado como una red hexagonal. A derecha: el mismo grafo visto como un subgrafo del diamante azteca (las aristas intermitentes son borradas al atribuírseles un peso nulo).

Una vez generado un acoplamiento perfecto del subgrafo correspondiente a la red hexagonal, se le asocia un mosaico del hexágono. Esta vez los adoquines utilizados ya no son dominós rectangulares, sino diamantes. Hay tres tipos, según su orientación.

PNG - 62.9 KB
Acoplamiento y embaldosado
Acoplamiento perfecto de una red hexagonal y el correspondiente embaldosado por diamantes.

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.

PNG - 23.1 KB
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.

Artículo original editado por Jacques Istas

Notas

[1J. C. Fournier. Tiling pictures of the plane with dominoes. Discrete Mathematics 165-166, (1997), 313-320: Graphs and Combinatorics

[2R. Kenyon, J. Propp, D. Wilson. Trees and matchings. Electron. J. Combin. 7 (2000), Research Paper 25, 34 pp.

[4W. Jockusch, J. Propp et P. Shor. Random domino tilings and the arctic circle theorem (1998).

[5J. Propp. Generalized domino-shuffling. Theoretical Computer Science 303 (2003), p. 267-301

[6É. Janvresse, T. de la Rue, Y. Velenik. A note on domino shuffling. Electron. J. Combin. 13 (2006), no 1.

Comparte este artículo

Para citar este artículo:

Andrés Navas — «Teselados aleatorios por revoltura de dominós» — Images des Mathématiques, CNRS, 2021

Comentario sobre el artículo

Dejar un comentario

Foro sólo para inscritos

Para participar en este foro, debe registrarte previamente. Gracias por indicar a continuación el identificador personal que se le ha suministrado. Si no está inscrito/a, debe inscribirse.

Conexióninscribirse¿contraseña olvidada?

La traducción del sitio del francés al castellano se realiza gracias al apoyo de diversas instituciones de matemáticas de América Latina.