Un poliominó es una figura geométrica plana formada por la unión de uno o más cuadrados iguales borde con borde. Es una poliforma cuyas celdas son cuadrados. Puede considerarse como un subconjunto finito del mosaico de cuadrados regulares .
Los poliominós se han utilizado en los juegos de mesa populares desde al menos 1907, y la enumeración de los pentominós data de la antigüedad. [1] Muchos resultados con piezas de 1 a 6 casillas fueron publicados por primera vez en Fairy Chess Review entre los años 1937 y 1957, bajo el nombre de "problemas de disección". El nombre poliominó fue inventado por Solomon W. Golomb en 1953, [2] y fue popularizado por Martin Gardner en una columna de " Juegos matemáticos " de noviembre de 1960 en Scientific American . [3]
Los poliominós están relacionados con los polidiamantes , formados a partir de triángulos equiláteros ; los polihexágonos , formados a partir de hexágonos regulares ; y otras poliformas planas . Los poliominós se han generalizado a dimensiones superiores uniendo cubos para formar policubos , o hipercubos para formar polihipercubos.
En física estadística , el estudio de los poliominós y sus análogos de dimensiones superiores (que a menudo se denominan animales reticulares 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 cúmulos de percolación . [4]
Al igual que muchos acertijos de 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 resultan inconvenientes para algunos propósitos, como los problemas de teselación. En algunos contextos, se excluyen los poliominós con agujeros, lo que permite solo poliominós conexos simples . [5]
Hay tres formas comunes de distinguir poliominós para enumeración: [6] [7]
La siguiente tabla muestra el número de poliominós de varios tipos con n celdas.
Los poliominós fijos fueron enumerados en 2004 hasta n = 56 por Iwan Jensen, [8] y en 2024 hasta n = 70 por Gill Barequet y Gil Ben-Shachar. [9]
Los poliominós libres fueron enumerados en 2007 hasta n = 28 por Tomás Oliveira e Silva [10] , en 2012 hasta n = 45 por Toshihiro Shirakawa [11] y en 2023 hasta n = 50 por John Mason. [12]
Las secuencias OEIS anteriores, con excepción de A001419, incluyen el recuento de 1 para el número de poliominós nulos; un poliominó nulo es uno que está formado por cero cuadrados.
El grupo diedro D 4 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 a un máximo de 8 poliominós fijos, que son sus imágenes bajo las simetrías de D 4 . Sin embargo, esas imágenes no son necesariamente distintas: cuanto más simetría tenga un poliominó libre, menos contrapartes fijas distintas tendrá. Por lo tanto, un poliominó libre que sea invariante bajo algunas o todas las simetrías no triviales de D 4 puede corresponder a solo 4, 2 o 1 poliominó fijo. Matemáticamente, los poliominós libres son clases de equivalencia de poliominós fijos bajo el grupo D 4 .
Los poliominós tienen las siguientes simetrías posibles; [13] el menor número de cuadrados necesarios en un poliominó con esa simetría se da en cada caso:
De la misma manera, el número de poliominós unilaterales depende de la simetría del poliominó de la siguiente manera:
La siguiente tabla muestra el número de poliominós con n cuadrados, ordenados por grupos de simetría.
[14]
Cada poliominó de tamaño n +1 se puede obtener sumando un cuadrado a un poliominó de tamaño n . Esto conduce a algoritmos para generar poliominós de manera inductiva.
En términos más simples, dada una lista de poliominós de tamaño n , se pueden agregar cuadrados al lado de cada poliominó en cada posición posible, y el poliominó resultante de tamaño n +1 se agrega 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 cuadrados adyacentes que no se deben considerar reducen la cantidad de casos que se deben verificar en busca de duplicados. [15] Este método se puede utilizar para enumerar poliominós libres o fijos.
Muchos autores han utilizado un método más sofisticado, descrito por Redelmeier, como una forma no solo de contar poliominós (sin requerir que todos los poliominós de tamaño n se almacenen en tamaño para enumerar los de tamaño n +1), sino también para demostrar límites superiores en su número. La idea básica es que comenzamos con un solo cuadrado y, a partir de allí, agregamos cuadrados recursivamente. Dependiendo de los detalles, puede contar cada n -ómino n veces, una vez a partir de cada uno de sus n cuadrados, o puede estar organizado para contar cada uno solo una vez.
La implementación más simple implica 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 sin numerar, comenzando con 5. Luego, elija un número mayor que el número elegido anteriormente y agregue ese cuadrado. Continúe eligiendo un número mayor que el número del cuadrado actual, agregue ese cuadrado y luego numere los nuevos cuadrados adyacentes. Cuando se hayan creado n cuadrados, se habrá creado un n -ómino.
Este método garantiza que cada poliominó fijo se cuente exactamente n veces, una 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, declare que es el cuadrado inferior izquierdo del poliominó. Simplemente no numere ningún cuadrado que esté en una fila inferior o a la izquierda del cuadrado en la misma fila. Esta es la versión descrita por Redelmeier.
Si en cambio se desea contar poliominós libres, se pueden verificar las simetrías después de crear cada n -ominó. Sin embargo, es más rápido [16] generar poliominós simétricos por separado (mediante una variación de este método) [17] y así determinar el número de poliominós libres mediante el lema de Burnside .
El algoritmo más moderno para enumerar los poliominós fijos fue descubierto por Iwan Jensen. [18] Es una mejora del método de Andrew Conway, [19] 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 la matriz de transferencia implican contar el número de poliominós que tienen un ancho determinado. 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 las 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 mucho más rápido que los métodos que tienen que generar cada poliominó.
Si bien tiene un excelente tiempo de ejecución, la desventaja es que este algoritmo utiliza 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.
Argumentos teóricos y cálculos numéricos respaldan la estimación del número de poliominós fijos de tamaño n
donde λ = 4,0626 y c = 0,3169. [20] 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 demostrado que
existe. En otras palabras, A n crece exponencialmente . El límite inferior más conocido para λ , encontrado en 2016, es 4.00253. [21] El límite superior más conocido es λ < 4.5252 . [22]
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 ( n + m )-ominó único. Esto demuestra que A n A m ≤ A n + m . Usando esta ecuación, uno puede mostrar λ ≥ ( A n ) 1/ n para todo n . Los refinamientos de este procedimiento combinados con datos para A n producen el límite inferior dado anteriormente.
El límite superior se obtiene generalizando el método inductivo de enumeración de poliominós. En lugar de sumar un cuadrado a la vez, se suman un grupo de cuadrados a la vez. Esto se suele describir como sumar ramitas . Al demostrar que cada n -ominó es una secuencia de ramitas, y al demostrar límites a las combinaciones de ramitas posibles, se obtiene un límite superior al número de n -ominós. Por ejemplo, en el algoritmo descrito anteriormente, en cada paso debemos elegir un número mayor, y como máximo se añaden tres números nuevos (ya que como máximo tres cuadrados no numerados son adyacentes a cualquier cuadrado numerado). Esto se puede utilizar para obtener un límite superior de 6,75. Utilizando 2,8 millones de ramitas, Klarner y Rivest obtuvieron un límite superior de 4,65, [23] que posteriormente fue mejorado por Barequet y Shalah a 4,5252. [22]
Las aproximaciones para el número de poliominós fijos y poliominós libres están relacionadas de una manera simple. Un poliominó libre sin simetrías (rotación o reflexión) corresponde a 8 poliominós fijos distintos, y para n grande , la mayoría de los n -ominós no tienen simetrías. Por lo tanto, el número de n -ominós fijos es aproximadamente 8 veces el número de n -ominós libres. Además, esta aproximación es exponencialmente más precisa a medida que n aumenta. [13]
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 la envoltura convexa ortogonal . Se dice que un poliominó es convexo vertical o en columna 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 convexo horizontal o 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. [24]
Se dice que un poliominó está dirigido si contiene un cuadrado, conocido como raíz , tal que se puede llegar a cualquier otro cuadrado con movimientos de un cuadrado hacia arriba o hacia la derecha, sin salir del poliominó.
Los poliominós dirigidos, [25] poliominós convexos de columna (o fila), [26] y poliominós convexos [27] 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 formado por un número par de cuadrados; todo número par mayor que 15 es posible. Por ejemplo, el 16-ominó en forma de cuadrado de 4 × 4 y el 18-ominó en forma de rectángulo de 3 × 6 son ambos iguales. Para los poliominós con 15 cuadrados o menos, el perímetro siempre excede el área. [28]
En matemáticas recreativas , a menudo se plantean desafíos para cubrir una región prescrita, o todo el plano, con poliominós, [29] y los problemas relacionados se investigan en matemáticas y ciencias de la computación .
Los acertijos suelen pedir que se embaldose una región dada con un conjunto dado de poliominós, como los 12 pentominós. Los libros de Golomb y Gardner tienen muchos ejemplos. Un acertijo típico es el de embaldosar un rectángulo de 6×10 con los doce pentominós; las 2339 soluciones para esto se encontraron en 1960. [30] Cuando se permiten múltiples copias de los poliominós en el conjunto, Golomb define una jerarquía de diferentes regiones que un conjunto puede ser capaz de embaldosar, como rectángulos, tiras y todo el plano, y muestra que es indecidible si los poliominós de un conjunto dado pueden embaldosar el plano , al mapear conjuntos de fichas de Wang a conjuntos de poliominós. [31]
Debido a que el problema general de agrupar regiones del plano con conjuntos de poliominós es NP-completo , [32] agrupar 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 agrupar regiones finitas del plano utiliza una técnica en informática llamada retroceso . [33]
En Jigsaw Sudokus, una cuadrícula cuadrada está cubierta de regiones con forma de polinomio (secuencia A172477 en la OEIS ).
Otra clase de problemas pregunta si las copias de un poliominó dado pueden teselar un rectángulo y, si es así, qué rectángulos pueden teselar. [34] Estos problemas han sido estudiados extensamente para poliominós particulares, [35] y hay tablas de resultados disponibles para poliominós individuales. [36] Klarner y Göbel demostraron que para cualquier poliominó hay un conjunto finito de rectángulos primos que tesela, de modo que todos los demás rectángulos que tesela pueden ser teselados por esos rectángulos primos. [37] [38] Kamenetsky y Cooke demostraron cómo varios poliominós disjuntos (llamados "agujereados") pueden teselar rectángulos. [39]
Además de los rectángulos, Golomb dio su jerarquía para los poliominós individuales: un poliominó puede teselar un rectángulo, una media tira, una tira doblada, una copia ampliada de sí mismo, un cuadrante, una tira, un semiplano , todo el plano, ciertas combinaciones o ninguna de ellas. Hay ciertas implicaciones entre ellas, tanto obvias (por ejemplo, si un poliominó tesela el semiplano, entonces tesela todo el plano) como menos obvias (por ejemplo, si un poliominó tesela una copia ampliada de sí mismo, entonces tesela el cuadrante). Los poliominós de tamaño hasta 6 se caracterizan en esta jerarquía (con el estado de un hexominó, que más tarde se descubrió que tesela un rectángulo, sin resolver en ese momento). [40]
En 2001, Cristopher Moore y John Michael Robson demostraron que el problema de teselar un poliominó con copias de otro es NP-completo . [41] [42]
También se ha discutido mucho sobre el teselado del plano con copias de un único poliominó. En 1965 se observó que todos los poliominós hasta los hexominós [43] y todos los heptominós menos cuatro teselados del plano. [44] David Bird estableció entonces que todos los octominós menos 26 teselados del plano. [45] Rawsthorne descubrió que todos los poliominós de tamaño 9 menos 235 teselados, [46] y Rhoads y otros extendieron estos resultados a áreas mayores (hasta tamaño 14) [47] y otros. Los poliominós que teselados del plano se clasificaron por las simetrías de sus teselados y por el número de aspectos (orientaciones) en los que aparecen los teselados en ellos. [48] [49]
El estudio de qué poliominós pueden teselar el plano se ha facilitado utilizando el criterio de Conway : a excepción de dos nonominós, todos los poliominós de teselación hasta un tamaño 9 forman un parche de al menos una tesela que lo satisface, siendo más frecuentes las excepciones de tamaño mayor. [50]
Varios poliominós pueden teselar copias más grandes de sí mismos, y repetir este proceso recursivamente da como resultado un teselado de rep-tiles del plano. Por ejemplo, para cada entero positivo n , es posible combinar n 2 copias del L-trominó, L-tetrominó o P-pentominó en una única forma más grande similar al poliominó más pequeño del que se formó. [51]
El problema de compatibilidad consiste en tomar dos o más poliominós y encontrar una figura que pueda ser teselada con cada uno de ellos. La compatibilidad de 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, [52] [53] y Livio Zucca muestra resultados para algunos casos complicados como tres pentominós diferentes. [54] 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 teselas de cada tipo. [55] 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.
Además de los problemas de teselación descritos anteriormente, existen juegos matemáticos recreativos que requieren doblar un poliominó para crear otras formas. Gardner propuso varios juegos simples con un conjunto de pentominós libres y un tablero de ajedrez. Algunas variantes del sudoku utilizan regiones con forma de no-nominó en la cuadrícula. El videojuego Tetris se basa en los siete tetrominós de un solo lado (que se escriben "Tetriminos" en el juego), y el juego de mesa Blokus utiliza todos los poliominós libres hasta los pentominós.
La palabra polyomino y los nombres de los distintos tamaños de polyomino son todos retroformaciones de la palabra domino , una pieza de juego común que consta de dos cuadrados. Se cree que el nombre domino para la pieza de juego proviene de la prenda de mascarada con manchas domino , del latín dominus . [56] A pesar de este origen de la palabra, al nombrar poliominós, la primera letra d- de domino se interpreta fantasiosamente como una versión del prefijo di- que significa "dos", y se reemplaza por otros prefijos numéricos .
