Poliomino

Los 18 pentominos de un lado, incluyendo 6 pares espejo

Los 35 hexominos libres, coloreados según su simetría.

El único domino libre.

Un poliominó es una figura geométrica plana formada por la unión de uno o más cuadrados iguales de lado a lado. Es una poliforma cuyas celdas son cuadrados. Puede considerarse como un subconjunto finito del mosaico cuadrado regular.

Los poliominós se han utilizado en acertijos populares desde al menos 1907, y la enumeración de los pentominós data de la antigüedad. Muchos resultados con las piezas de 1 a 6 casillas se publicaron por primera vez en Fairy Chess Review entre los años 1937 a 1957, bajo el nombre de "problemas de disección". El nombre poliomino fue inventado por Solomon W. Golomb en 1953, y Martin Gardner lo popularizó en noviembre de 1960 en "Mathematical Games" columna en Scientific American.

Relacionados con los poliominós están los polidiamantes, formados a partir de triángulos equiláteros; polihexágonos, formados por hexágonos regulares; y otras poliformas planas. Los poliominós se han generalizado a dimensiones superiores al unir cubos para formar policubos o hipercubos para formar polihipercubos.

En física estadística, el estudio de poliominós y sus análogos de dimensiones superiores (a los que a menudo se hace referencia como animales de celosía en esta literatura) se aplica a problemas de física y química. Los poliominós se han utilizado como modelos de polímeros ramificados y de grupos de percolación.

Al igual que muchos acertijos en las matemáticas recreativas, los poliominós plantean muchos problemas combinatorios. El más básico es enumerar poliominós de un tamaño determinado. No se ha encontrado ninguna fórmula excepto para clases especiales de poliominós. Se conocen varias estimaciones y existen algoritmos para calcularlas.

Los poliominós con agujeros son inconvenientes para algunos propósitos, como problemas de mosaico. En algunos contextos, se excluyen los poliominós con agujeros, lo que permite solo poliominós simplemente conectados.

Enumeración de poliominós

Poliominós libres, unilaterales y fijos

Hay tres formas comunes de distinguir los poliominós para la enumeración:

• gratis Los poliominos son distintos cuando ninguno es una transformación rígida (traducción, rotación, reflexión o reflexión de deslizamiento) de otro (pies que pueden ser recogidos y volteados). Traducir, rotar, reflexionar o deslizarse reflejando un poliomino libre no cambia su forma.
• poliominos unilaterales son distintos cuando ninguno es una traducción o rotación de otro (piezas que no pueden ser volteadas). Traducir o girar un poliomino unilateral no cambia su forma.
• fijo Los poliominos son distintos cuando ninguno es una traducción de otro (piezas que no pueden ser volteadas ni rotadas). Traducir un poliomino fijo no cambiará su forma.

La siguiente tabla muestra el número de poliominós de varios tipos con n celdas.

A partir de 2004, Iwan Jensen ha enumerado los poliominós fijos hasta n = 56, aproximadamente 6,915×10³¹.

Los poliominós libres fueron enumerados en 2007 hasta n = 28 por Tomás Oliveira e Silva, y en 2012 hasta n = 45 de Toshihiro Shirakawa.

Simetrías de poliominós

El grupo diédrico D₄ es el grupo de simetrías (grupo de simetría) de un cuadrado. Este grupo contiene cuatro rotaciones y cuatro reflexiones. Se genera alternando reflexiones sobre el eje x y sobre una diagonal. Un poliominó libre corresponde como máximo a 8 poliominós fijos, que son sus imágenes bajo las simetrías de D₄. Sin embargo, esas imágenes no son necesariamente distintas: cuanto más simetría tiene un poliominó libre, menos contrapartes fijas distintas tiene. Por lo tanto, un poliominó libre que es invariante bajo algunas o todas las simetrías no triviales de D₄ puede corresponder a solo 4, 2 o 1 poliominós fijos. Matemáticamente, los poliominós libres son clases de equivalencia de poliominós fijos bajo el grupo D₄.

Los poliominós tienen las siguientes simetrías posibles; en cada caso se da el menor número de cuadrados necesarios en un poliominó con esa simetría:

• 8 poliominos fijos para cada poliomino libre:
  • sin simetría (4)
• 4 poliominos fijos para cada poliomino libre:
  • simetría de espejo con respecto a una de las direcciones de línea de red (4)
  • simetría del espejo con respecto a una línea diagonal (3)
  • Simetría rotacional doble: C₂ 4)
• 2 poliominos fijos para cada poliomino libre:
  • simetría con respecto a ambas direcciones de línea de red, y por lo tanto también simetría rotacional de dos veces: D₂ (2) (también conocido como los cuatro grupos Klein)
  • simetría con respecto a ambas direcciones diagonales, y por lo tanto también simetría rotacional doble: D₂ (7)
  • Simetría rotacional 4 veces: C₄ (8)
• 1 poliomino fijo para cada poliomino libre:
  • toda la simetría de la plaza: D₄ 1).

De la misma manera, el número de poliominós de un solo lado depende de la simetría del poliominó de la siguiente manera:

• 2 poliominos unilaterales para cada poliomino libre:
  • sin simetría
  • Simetría rotacional doble: C₂
  • Simetría rotacional 4 veces: C₄
• 1 poliomino unilateral para cada poliomino libre:
  • toda la simetría de la plaza: D₄
  • simetría de espejo con respecto a una de las direcciones de línea de red
  • simetría de espejo con respecto a una línea diagonal
  • simetría con respecto a ambas direcciones de línea de red, y por lo tanto también simetría rotacional de dos veces: D₂
  • simetría con respecto a ambas direcciones diagonales, y por lo tanto también simetría rotacional doble: D₂.

La siguiente tabla muestra el número de poliominós con n cuadrados, ordenados por grupos de simetría.

Algoritmos para enumeración de poliominós fijos

Algoritmos inductivos

Cada poliominó de orden n+1 se puede obtener sumando un cuadrado a un poliominó de orden n. Esto conduce a algoritmos para generar poliominós de forma inductiva.

Más simple, dada una lista de poliominós de orden n, se pueden agregar cuadrados al lado de cada poliominó en cada posición posible, y el poliominó resultante de orden n+ 1 agregado a la lista si no es un duplicado de uno ya encontrado; los refinamientos en el orden de la enumeración y el marcado de los cuadrados adyacentes que no deben considerarse reducen el número de casos que deben verificarse en busca de duplicados. Este método se puede utilizar para enumerar poliominós libres o fijos.

Un método más sofisticado, descrito por Redelmeier, ha sido utilizado por muchos autores como una forma no solo de contar poliominós (sin requerir que todos los poliominós de orden n se almacenen para enumerar los de orden n+1), pero también demostrando límites superiores en su número. La idea básica es que comenzamos con un solo cuadrado y, a partir de ahí, agregamos cuadrados recursivamente. Dependiendo de los detalles, puede contar cada n-omino n veces, una vez a partir de cada uno de sus cuadrados n, o puede organizarse para contar cada uno una sola vez.

La implementación más simple consiste en agregar un cuadrado a la vez. Comenzando con un cuadrado inicial, numere los cuadrados adyacentes, en el sentido de las agujas del reloj desde arriba, 1, 2, 3 y 4. Ahora elija un número entre 1 y 4, y agregue un cuadrado en esa ubicación. Numere los cuadrados adyacentes no numerados, comenzando con 5. Luego, elija un número más grande que el número elegido anteriormente y agregue ese cuadrado. Continúe eligiendo un número mayor que el número del cuadrado actual, sumando ese cuadrado y luego numerando los nuevos cuadrados adyacentes. Cuando se han creado n cuadrados, se ha creado un n-omino.

Este método asegura que cada poliominó fijo se cuente exactamente n veces, una vez por cada cuadrado inicial. Se puede optimizar para que cuente cada poliominó solo una vez, en lugar de n veces. Comenzando con el cuadrado inicial, decláralo como el cuadrado inferior izquierdo del poliominó. Simplemente no numere ningún cuadrado que esté en una fila inferior oa la izquierda del cuadrado en la misma fila. Esta es la versión descrita por Redelmeier.

Si uno desea contar poliominós libres en su lugar, puede verificar si hay simetrías después de crear cada n-omino. Sin embargo, es más rápido generar poliominós simétricos por separado (mediante una variación de este método) y así determinar el número de poliominós libres mediante el lema de Burnside.

Método de matriz de transferencia

Iwan Jensen descubrió el algoritmo más moderno para enumerar los poliominós fijos. Una mejora del método de Andrew Conway, es exponencialmente más rápido que los métodos anteriores (sin embargo, su tiempo de ejecución sigue siendo exponencial en n).

Tanto la versión de Conway como la de Jensen del método de matriz de transferencia implican contar el número de poliominós que tienen un cierto ancho. Calcular el número para todos los anchos da el número total de poliominós. La idea básica detrás del método es que se consideran posibles filas iniciales y luego se determina el número mínimo de cuadrados necesarios para completar el poliominó del ancho dado. Combinada con el uso de funciones generadoras, esta técnica puede contar muchos poliominós a la vez, lo que le permite ejecutarse muchas veces más rápido que los métodos que tienen que generar cada poliominó.

Aunque tiene un excelente tiempo de ejecución, la contrapartida es que este algoritmo usa cantidades exponenciales de memoria (se necesitan muchos gigabytes de memoria para n por encima de 50), es mucho más difícil de programar que los otros métodos, y actualmente no se puede usar para contar poliominós libres.

Crecimiento asintótico del número de poliominós

Polominós fijos

Los argumentos teóricos y los cálculos numéricos respaldan la estimación del número de poliominós fijos de tamaño n

An♪ ♪ cλ λ nn{displaystyle A_{n}sim {frac {clambda.

donde λ = 4,0626 y c = 0,3169. Sin embargo, este resultado no está probado y los valores de λ y c son solo estimaciones.

Los resultados teóricos conocidos no son tan específicos como esta estimación. Se ha probado que

limn→ → JUEGO JUEGO ()An)1n=λ λ {displaystyle lim _{nrightarrow infty}(A_{n})^{frac {1}{n}=lambda }

existe. En otras palabras, A_n crece exponencialmente. El límite inferior más conocido para λ, encontrado en 2016, es 4,00253. El límite superior más conocido, que no ha mejorado desde la década de 1970, es λ < 4,65.

Para establecer un límite inferior, un método simple pero altamente efectivo es la concatenación de poliominós. Defina el cuadrado superior derecho como el cuadrado más a la derecha en la fila superior del poliominó. Defina el cuadrado inferior izquierdo de manera similar. Luego, el cuadrado superior derecho de cualquier poliominó de tamaño n se puede unir al cuadrado inferior izquierdo de cualquier poliominó de tamaño m para producir un único ( n+m)-omino. Esto prueba que A_nA_m ≤ A _n+m. Usando esta ecuación, uno puede mostrar λ ≥ (A_n)^{1/ n} para todos los n. Los refinamientos de este procedimiento combinados con datos para A_n producen el límite inferior dado anteriormente.

El límite superior se logra generalizando el método inductivo de enumeración de poliominós. En lugar de agregar un cuadrado a la vez, uno agrega un grupo de cuadrados a la vez. Esto a menudo se describe como agregar ramitas. Al probar que cada n-omino es una secuencia de ramitas, y al probar los límites en las combinaciones de ramitas posibles, se obtiene un límite superior en el número de n-ominoes. Por ejemplo, en el algoritmo descrito anteriormente, en cada paso debemos elegir un número mayor y, como máximo, se agregan tres números nuevos (ya que, como máximo, hay tres cuadrados sin numerar adyacentes a cualquier cuadrado numerado). Esto se puede utilizar para obtener un límite superior de 6,75. Usando 2,8 millones de ramitas, Klarner y Rivest obtuvieron un límite superior de 4,65, que posteriormente Barequet y Shalah mejoraron a 4,5252.

Poliominós libres

Las aproximaciones para el número de poliominós fijos y poliominós libres se relacionan de manera sencilla. Un poliominó libre sin simetrías (rotación o reflexión) corresponde a 8 poliominós fijos distintos, y para n grandes, la mayoría de los ominós n no tienen simetrías. Por lo tanto, el número de n-ominoes fijos es aproximadamente 8 veces el número de n-ominoes libres. Además, esta aproximación es exponencialmente más precisa a medida que aumenta n.

Clases especiales de poliominós

Se conocen fórmulas exactas para enumerar poliominós de clases especiales, como la clase de poliominós convexos y la clase de poliominós dirigidos.

La definición de un poliominó convexo es diferente de la definición habitual de convexidad, pero es similar a la definición utilizada para el casco convexo ortogonal. Se dice que un poliominó es verticalmente o columna convexa si su intersección con cualquier línea vertical es convexa (en otras palabras, cada columna no tiene agujeros). De manera similar, se dice que un poliominó es horizontalmente o convexo en fila si su intersección con cualquier línea horizontal es convexa. Se dice que un poliominó es convexo si es convexo en fila y columna.

Se dice que un poliominó está dirigido si contiene un cuadrado, conocido como raíz, de modo que se puede llegar a cualquier otro cuadrado mediante movimientos hacia arriba o hacia la derecha. cuadrado, sin salir del poliomino.

Los poliominós dirigidos, los poliominós convexos de columna (o fila) y los poliominós convexos se han enumerado de manera efectiva por área n, así como por algunos otros parámetros como el perímetro, utilizando funciones generadoras.

Un poliominó es igual si su área es igual a su perímetro. Un poliominó igual debe estar hecho de un número par de cuadrados; todo número par mayor que 15 es posible. Por ejemplo, el 16-omino en forma de cuadrado de 4 × 4 y el 18-omino en forma de rectángulo de 3 × 6 son iguales. Para poliominós con menos de 15 cuadrados, el perímetro siempre excede el área.

Teselado con poliominós

En matemáticas recreativas, a menudo se plantean desafíos para teselar una región prescrita, o todo el plano, con poliominós, y los problemas relacionados se investigan en matemáticas e informática.

Regiones de mosaico con conjuntos de poliominós

Los rompecabezas normalmente piden que se coloquen mosaicos en una región determinada con un conjunto dado de poliominós, como los 12 pentominós. Los libros de Golomb y Gardner tienen muchos ejemplos. Un rompecabezas típico es teselar un rectángulo de 6×10 con los doce pentominós; las 2339 soluciones a esto se encontraron en 1960. Donde se permiten múltiples copias de los poliominós en el conjunto, Golomb define una jerarquía de diferentes regiones que un conjunto puede colocar en mosaico, como rectángulos, tiras y todo el plano, y muestra que si los poliominós de un conjunto dado pueden teselar el plano es indecidible, mediante la asignación de conjuntos de teselas Wang a conjuntos de poliominós.

Debido a que el problema general de teselar regiones del plano con conjuntos de poliominós es NP-completo, teselar con más de unas pocas piezas rápidamente se vuelve intratable y, por lo tanto, se requiere la ayuda de una computadora. El enfoque tradicional para teselar regiones finitas del plano utiliza una técnica informática llamada backtracking.

En Jigsaw Sudokus, una cuadrícula cuadrada está dividida en mosaicos con regiones en forma de polinóminos (secuencia A172477 en el OEIS).

Regiones en mosaico con copias de un solo poliomino

Otra clase de problemas pregunta si las copias de un poliominó determinado pueden teselar un rectángulo y, de ser así, qué rectángulos pueden teselar. Estos problemas han sido ampliamente estudiados para poliominós particulares, y están disponibles tablas de resultados para poliominós individuales. Klarner y Göbel demostraron que para cualquier poliominó hay un conjunto finito de rectángulos principales que enlosa, de modo que todos los demás rectángulos que enlosa pueden ser enlosados por esos rectángulos primos. Kamenetsky y Cooke mostraron cómo varios poliominós disjuntos (llamados 'agujeros') pueden teselar rectángulos.

Más allá de los rectángulos, Golomb dio su jerarquía para poliominós individuales: un poliominó puede formar un rectángulo, una media tira, una tira doblada, una copia ampliada de sí mismo, un cuadrante, una tira, un medio plano, todo el plano, ciertos combinaciones, o ninguna de estas. Hay ciertas implicaciones entre estas, tanto obvias (por ejemplo, si un poliominó enlosa el medio plano, entonces enlosa todo el plano) y menos (por ejemplo, si un poliominó enlosa una copia ampliada de sí mismo, entonces enlosa el cuadrante).. Los poliominós de órdenes hasta 6 se caracterizan en esta jerarquía (con el estado de un hexominó, que luego se encontró para enlosar un rectángulo, sin resolver en ese momento).

En 2001, Cristopher Moore y John Michael Robson demostraron que el problema de teselar un poliominó con copias de otro es NP-completo.

Alicatar el plano con copias de un solo poliomino

Los dos nonominos de nivel no satisfacen el criterio de Conway.

También se ha discutido mucho la colocación de mosaicos en el plano con copias de un solo poliominó. En 1965 se observó que todos los poliominós hasta los hexominós y todos menos cuatro heptominós forman mosaicos en el plano. Luego, David Bird estableció que todos menos 26 octominós embaldosan el avión. Rawsthorne descubrió que todos menos 235 poliominós de orden 9 son mosaicos, y Rhoads (al orden 14) y otros han extendido tales resultados a órdenes superiores. Los poliominós que teselan el plano han sido clasificados por las simetrías de sus teselados y por el número de aspectos (orientaciones) en que aparecen los teselados en ellos.

El estudio de qué poliominós pueden teselar el plano se ha facilitado utilizando el criterio de Conway: excepto dos nonominós, todos los poliominós teselados hasta el orden 9 forman un parche de al menos una tesela que lo satisface, con excepciones de orden superior más frecuentes.

Varios poliominós pueden teselar copias más grandes de sí mismos y, al repetir este proceso recursivamente, se obtiene un teselado de reptiles del plano. Por ejemplo, para cada entero positivo n, es posible combinar n² copias del L-tromino, L-tetromino o P-pentomino en una sola forma más grande similar al poliomino más pequeño a partir del cual se formó.

Teselado de una figura común con varios poliominós

Una figura de compatibilidad mínima para los pentominos T y W.

El problema de compatibilidad consiste en tomar dos o más poliominós y encontrar una figura que se pueda teselar con cada uno. La compatibilidad con poliominós ha sido ampliamente estudiada desde la década de 1990. Jorge Luis Mireles y Giovanni Resta han publicado sitios web de resultados sistemáticos, y Livio Zucca muestra resultados para algunos casos complicados como tres pentominós diferentes. El problema general puede ser difícil. La primera figura de compatibilidad para los pentominós L y X se publicó en 2005 y tenía 80 mosaicos de cada tipo. Se ha demostrado que muchos pares de poliominós son incompatibles por agotamiento sistemático. No se conoce ningún algoritmo para decidir si dos poliominós arbitrarios son compatibles.

Poliominós en rompecabezas y juegos

Además de los problemas de mosaico descritos anteriormente, existen acertijos matemáticos recreativos que requieren doblar un poliominó para crear otras formas. Gardner propuso varios juegos sencillos con un conjunto de pentominós libres y un tablero de ajedrez. Algunas variantes del rompecabezas de Sudoku usan regiones en forma de nonomino en la cuadrícula. El videojuego Tetris se basa en los siete tetrominós de una cara (deletreados "Tetriminos" en el juego), y el juego de mesa Blokus utiliza todos los los poliominós libres hasta los pentominós.

Etimología

La palabra poliominó y los nombres de los distintos órdenes de poliominó son todas formaciones posteriores de la palabra dominó, una pieza de juego común que consta de dos cuadrados, con el primera letra d- interpretada imaginativamente como una versión del prefijo di- que significa "dos." Se cree que el nombre domino de la pieza del juego proviene de la prenda de disfraces manchada domino, del latín dominus.

La mayoría de los prefijos numéricos son griegos. Los poliominós de orden 9 y 11 toman más a menudo los prefijos latinos nona- (nonomino) y undeca- (undecomino) que los prefijos griegos ennea- (eneomino) y hendeca- (hendecomino).