Ir al contenido

Teselado en dominó

De Wikipedia, la enciclopedia libre
Teselado en dominó de un cuadrado

En geometría, un teselado en dominó de una región en el espacio bidimensional es un recubrimiento de la región mediante dominós, piezas formadas por la unión de dos cuadrados iguales lado a lado. Equivalentemente, es un pareado perfecto sobre el gráfico de celosía formado al colocar un vértice en el centro de cada cuadrado de la región y conectando dos vértices cuando corresponden a cuadrados adyacentes.

Funciones de altura

[editar]

Para algunas clases de mosaicos sobre una rejilla en dos dimensiones, es posible definir una función de altura asociando un entero a cada vértice de la rejilla. Por ejemplo, sobre un tablero de ajedrez, se asigna el nodo con altura 0, y para cualquier nodo hay una ruta desde hasta él. En esta ruta, se define la altura de cada nodo (es decir, las esquinas de los cuadrados) como la altura del nodo anterior más uno si el cuadrado a la derecha de la ruta de a es negro, y menos uno en caso contrario.

Se pueden encontrar más detalles en Kenyon y Okounkov (2005).

Condición de altura de Thurston

[editar]

William Thurston (1990) describe una prueba para determinar si una región simplemente conectada, formada como la unión de cuadrados unitarios en el plano, puede recubrirse con un mosaico en dominó. Forma un grafo que tiene como vértices los puntos (x,y,z) en una rejilla tridimensional de valores enteros, donde cada punto está conectado a cuatro vecinos: si x + y es par, entonces (x,y,z) está conectado a (x + 1,y,z + 1), (x - 1,y,z + 1), (x,y + 1, z - 1), y (x,y - 1,z - 1), mientras que si x + y es impar, entonces (x,y,z) está conectado a (x + 1,y,z - 1), (x  1,y,z - 1), (x,y + 1,z + 1), y (x,y - 1,z + 1). El límite de la región, visto como una secuencia de puntos enteros en el plano (x,y), se levanta de forma única (una vez que se elige una altura de inicio) a una ruta en este grafo tridimensional. Una condición necesaria para que esta región sea enlosable es que esta ruta debe cerrarse para formar una curva cerrada simple en tres dimensiones, sin embargo, esta condición no es suficiente. Utilizando un análisis más cuidadoso de la ruta límite, Thurston dio un criterio para determinar la idoneidad de una región que era suficiente y necesaria.

Recuento de teselados de regiones

[editar]
Teselado en dominó de un cuadrado de 8×8 usando la cantidad mínima de pares de borde largo a borde largo (1 par en el centro). Esta disposición también es un mosaico válido tatami de un cuadrado de 8x8, sin cuatro fichas de dominó coincidiendo en un punto interno.

El número de formas de cubrir un rectángulo de con dominós, calculado independientemente por Temperley y Fisher (1961) y Kasteleyn (1961), viene dado por

Cuando ambos m y n son impares, la fórmula reduce correctamente a cero los posibles recubrimientos en dominó.

Se produce un caso especial cuando se embaldosa el rectángulo con n dominós: la secuencia se reduce a la sucesión de Fibonacci (sucesión A000045 en OEIS) (Klarner y Pollack, 1980).

Otro caso especial se produce para cuadrados con m = n = 0, 2, 4, 6, 8, 10, 12, ... cuyos números de soluciones distintas coinciden con

1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, ... (sucesión A004003 en OEIS).

Estos números se pueden encontrar escribiéndolos como el pfaffiano de una matriz antisimétrica cuyos vectores y autovalores se pueden encontrar explícitamente. Esta técnica se puede aplicar en muchos temas relacionados con las matemáticas, por ejemplo, en el cálculo clásico bidimensional de la función de correlación dimer-dimer en física estadística.

El número de ajustes de una región es muy sensible a las condiciones de contorno y puede cambiar drásticamente con modificaciones aparentemente insignificantes en la forma de la región. Esto queda ilustrado por el número de mosaicos de un diamante azteca de orden n, donde el número de mosaicos es 2(n + 1)n/2. Si esto es reemplazado por el "diamante azteca aumentado" de orden n con 3 filas largas en el medio en lugar de 2, el número de ajustes cae al número mucho más pequeño D (n,n), un número de Delannoy, que tiene solo carácter exponencial en lugar de tetración en n. Para el "diamante azteca reducido" de orden n con solo una fila media larga, solo existe un mosaico.

Tatamis

[editar]

Los tatamis son tapetes japoneses en forma de dominó (rectángulo de 1x2). Se usan para colocar mosaicos en habitaciones, pero con reglas adicionales sobre cómo se pueden colocar. En particular, típicamente, las uniones donde se encuentran tres tatamis se consideran favorables, mientras que las uniones donde se unen cuatro esquinas se consideran desfavorables, por lo que una disposición de tatamis apropiada es aquella en la que solo tres tatamis se juntan en cualquier esquina (Mathar, 2013;Ruskey y Woodcock, 2009). El problema de embaldosar una habitación irregular con un tatami que se une a una esquina es NP-completo(Erickson y Ruskey, 2013).

Véase también

[editar]

Referencias

[editar]