Un poliominó es una figura geométrica plana formada al unir uno o más cuadrados iguales borde con borde. 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 pentominós se remonta a la antigüedad. [1] Muchos resultados con 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 poliominó fue inventado por Solomon W. Golomb en 1953, [2] y fue popularizado por Martin Gardner en una columna de noviembre de 1960 sobre " Juegos matemáticos " en Scientific American . [3]
Relacionados con los poliominós están las polidiamantes , formadas a partir de triángulos equiláteros ; 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 (a los que a menudo se hace referencia como 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 grupos de percolación . [4]
Como muchos acertijos de matemáticas recreativas , los poliominós plantean muchos problemas combinatorios . Lo 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 los problemas de mosaico. En algunos contextos se excluyen los poliominós con agujeros, permitiendo sólo poliominós simplemente conectados . [5]
Hay tres formas comunes de distinguir poliominós para la enumeración: [6] [7]
La siguiente tabla muestra el número de poliominós de varios tipos con n celdas.
En 2004 [actualizar], Iwan Jensen ha enumerado los poliominós fijos hasta n = 56 – aproximadamente 6,915 × 1031 . [8]
Los poliominós libres fueron enumerados en 2007 hasta n = 28 por Tomás Oliveira e Silva, [9] en 2012 hasta n = 45 por Toshihiro Shirakawa, [10] y en 2023 hasta n = 50 por John Mason. [11]
Las secuencias OEIS anteriores, con la excepción de A001419, incluyen el recuento de 1 para el número de poliominós nulos; un poliominó nulo es aquel que está formado por cero cuadrados.
El grupo diédrico 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 como máximo a 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 tiene un poliomino 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 4 puede corresponder sólo a 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; [12] el menor número de cuadrados necesarios en un poliominó con esa simetría viene dado en cada caso:
De la misma manera, el número de poliominos unilaterales depende de la simetría del poliomino de la siguiente manera:
La siguiente tabla muestra el número de poliominós con n cuadrados, ordenados por grupos de simetría.
[13]
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 forma inductiva.
De manera más simple, 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 al ordenar la enumeración y marcar los cuadrados adyacentes que no deben considerarse reducen el número de casos que deben verificarse para detectar duplicados. [14] 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 sólo 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 la superioridad de los poliominós. límites en su número. La idea básica es que comenzamos con un solo cuadrado y, a partir de ahí, agregamos cuadrados de forma recursiva. Dependiendo de los detalles, puede contar cada n -omino n veces, una vez a partir de cada uno de sus n cuadrados, o puede disponerse para contar cada uno solo una vez.
La implementación más sencilla consiste en añadir 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. Numera los cuadrados adyacentes sin numerar, comenzando con 5. Luego, elige un número mayor que el número elegido anteriormente y suma 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 -ominó.
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 poliomino solo una vez, en lugar de n veces. Comenzando con el cuadrado inicial, declara 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, entonces se pueden verificar las simetrías después de crear cada n -ominó. Sin embargo, es más rápido [15] generar poliominós simétricos por separado (mediante una variación de este método) [16] y así determinar el número de poliominós libres mediante el lema de Burnside .
Iwan Jensen descubrió el algoritmo más moderno para enumerar poliominós fijos. [17] Una mejora del método de Andrew Conway, [18] 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 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 considerar las posibles filas iniciales y luego determinar 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 es capaz de 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 tiempo de ejecución excelente, la desventaja es que este algoritmo utiliza cantidades exponenciales de memoria (se necesitan muchos gigabytes de memoria para n superior a 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 yc = 0,3169. [19] Sin embargo, este resultado no está probado y los valores de λ y c son sólo estimaciones.
Los resultados teóricos conocidos no son tan específicos como esta estimación. Se ha demostrado que
existe. En otras palabras, An crece exponencialmente . El límite inferior más conocido de λ , encontrado en 2016, es 4,00253. [20] El límite superior más conocido es λ < 4,5252 . [21]
Para establecer un límite inferior, un método simple pero muy eficaz 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 A n A m ≤ A n + m . Usando esta ecuación, se puede mostrar λ ≥ ( A n ) 1/ n para todo n . Los refinamientos de este procedimiento combinados con datos para An producen el límite inferior indicado anteriormente.
El límite superior se alcanza generalizando el método inductivo de enumerar poliominós. En lugar de agregar un cuadrado a la vez, se agrega un grupo de cuadrados a la vez. Esto a menudo se describe como agregar ramitas . Al demostrar que cada n -ominó es una secuencia de ramitas y al demostrar límites a las combinaciones de posibles ramitas, se obtiene un límite superior para el número de n -ominó. 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 tres cuadrados sin numerar 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, [22] que posteriormente fue mejorado por Barequet y Shalah a 4,5252. [21]
Las aproximaciones para el número de poliominós fijos y poliominós libres se relacionan de forma 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 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. [12]
Se conocen fórmulas exactas para enumerar poliominós de clases especiales, como la clase de poliominó convexo y la clase de poliominó dirigido .
La definición de poliomino 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 convexo 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 horizontalmente o por filas si su intersección con cualquier línea horizontal es convexa. Se dice que un poliominó es convexo si es convexo en filas y columnas. [23]
Se dice que un poliominó está dirigido si contiene un cuadrado, conocido como raíz , de modo que se pueda llegar a cada dos cuadrados mediante movimientos de un cuadrado hacia arriba o hacia la derecha, sin salir del poliominó.
Los poliominós dirigidos, [24] poliominós convexos de columna (o fila), [25] y los poliominós convexos [26] se han enumerado efectivamente 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 poliomino 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 un cuadrado de 4 × 4 y el 18 ominó en forma de un rectángulo de 3 × 6 son ambos iguales. Para poliominós con 15 cuadrados o menos, el perímetro siempre excede el área. [27]
En matemáticas recreativas , a menudo se plantean desafíos para revestir una región determinada, o todo el plano, con poliominós, [28] y se investigan problemas relacionados en matemáticas e informática .
Los rompecabezas suelen pedir que se coloque en mosaico una región determinada con un conjunto determinado de poliominós, como los 12 pentominós. Los libros de Golomb y Gardner tienen muchos ejemplos. Un rompecabezas típico consiste en colocar un rectángulo de 6 × 10 con los doce pentominós; las 2339 soluciones a esto se encontraron en 1960. [29] 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 colocar en mosaico, como rectángulos, tiras y todo el conjunto. plano, y muestra que es indecidible si los poliominós de un conjunto dado pueden formar mosaicos en el plano , al mapear conjuntos de mosaicos de Wang a conjuntos de poliominós. [30]
Debido a que el problema general de mosaico de regiones del plano con conjuntos de poliominós es NP-completo , [31] el mosaico 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 colocar en mosaico regiones finitas del plano utiliza una técnica en informática llamada retroceso . [32]
En Jigsaw Sudokus, una cuadrícula cuadrada está en mosaico con regiones en forma de polinominó (secuencia A172477 en OEIS ).
Otra clase de problemas pregunta si las copias de un poliominó dado pueden formar mosaicos en un rectángulo y, de ser así, qué rectángulos pueden formar mosaicos. [33] Estos problemas se han estudiado ampliamente para poliominós particulares, [34] y se encuentran disponibles tablas de resultados para poliominós individuales. [35] Klarner y Göbel demostraron que para cualquier poliomino hay un conjunto finito de rectángulos primos que mosaico, de modo que todos los demás rectángulos que mosaico pueden ser mosaicos por esos rectángulos primos. [36] [37] Kamenetsky y Cooke demostraron cómo varios poliominós disjuntos (llamados "agujeros") pueden formar rectángulos en mosaico. [38]
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 franja, una franja doblada, una copia ampliada de sí mismo, un cuadrante, una franja, un semiplano , el plano completo, ciertas combinaciones o ninguno de esos. Hay ciertas implicaciones entre ellas, tanto obvias (por ejemplo, si un poliominó coloca el semiplano en mosaico, entonces coloca en mosaico todo el plano) como menos (por ejemplo, si un poliominó coloca en mosaico una copia ampliada de sí mismo, entonces coloca en mosaico el cuadrante). . Los poliominós de tamaño hasta 6 se caracterizan en esta jerarquía (con el estado de un hexominó, que luego se descubrió que formaba un rectángulo, sin resolver en ese momento). [39]
En 2001, Cristopher Moore y John Michael Robson demostraron que el problema de unir un poliominó con copias de otro es NP-completo . [40] [41]
También se ha debatido mucho sobre el mosaico del plano con copias de un solo poliominó. En 1965 se observó que todos los poliominós hasta los hexominós [42] y todos los heptominós menos cuatro forman mosaicos en el plano. [43] David Bird estableció entonces que todos menos 26 octominós forman mosaicos en el avión. [44] Rawsthorne descubrió que todos menos 235 poliominós de tamaño 9, [45] y Rhoads (al tamaño 14 ) y otros han extendido tales resultados a áreas más altas . Los poliominós que embaldosan el plano se han clasificado por las simetrías de sus mosaicos y por el número de aspectos (orientaciones) en los que aparecen los mosaicos en ellos. [47] [48]
El estudio de qué poliominós pueden enlosar el plano se ha facilitado utilizando el criterio de Conway : excepto dos nonominós, todos los poliominós de mosaico hasta el tamaño 9 forman un parche de al menos una losa que lo satisface, siendo más frecuentes las excepciones de mayor tamaño. [49]
Varios poliominós pueden formar mosaicos con copias más grandes de sí mismos, y al repetir este proceso de forma recursiva se obtiene un mosaico de reptiles del plano. Por ejemplo, para cada número entero positivo n , es posible combinar n 2 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ó. [50]
El problema de compatibilidad es tomar dos o más polióminos y encontrar una figura que pueda combinarse con cada uno. La compatibilidad con poliomino ha sido ampliamente estudiada desde la década de 1990. Jorge Luis Mireles y Giovanni Resta han publicado sitios web con resultados sistemáticos, [51] [52] y Livio Zucca muestra resultados para algunos casos complicados como tres pentominós diferentes. [53] El problema general puede ser difícil. La primera cifra de compatibilidad de los pentominós L y X se publicó en 2005 y tenía 80 fichas de cada tipo. [54] Se ha demostrado que muchos pares de poliominós son incompatibles mediante agotamiento sistemático. No se conoce ningún algoritmo para decidir si dos poliominós arbitrarios son compatibles.
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 juego de pentominós libres y un tablero de ajedrez. Algunas variantes del Sudoku utilizan regiones con forma de nominó 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 poliominós libres hasta los pentominós.
La palabra poliominó y los nombres de los distintos tamaños de poliominó son formaciones posteriores de la palabra dominó , una pieza de juego común que consta de dos cuadrados, con la primera letra d- interpretada fantasiosamente como una versión del prefijo di- que significa "dos ". Se cree que el nombre dominó de la pieza del juego proviene de la prenda de disfraces manchada dominó , del latín dominus . [55]
La mayoría de los prefijos numéricos son griegos. Los poliominós de tamaño 9 y 11 toman con más frecuencia los prefijos latinos nona- (nonomino) y undeca- (undecomino) que los prefijos griegos ennea- (enneomino) y hendeca- (hendecomino). [ ¿ por qué? ]
