Poliomino

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 10 de julio de 2019; las comprobaciones requieren 3 ediciones .

Polyomino , o polyomino ( inglés  polyomino ) - formas geométricas planas formadas al conectar varios cuadrados unicelulares en sus lados. Estas son poliformas cuyos segmentos son cuadrados [1] .

Una pieza de poliominó se puede ver como un subconjunto finito conectado de un tablero de ajedrez infinito que se puede pasar por alto con una torre [1] [3] .

Nombres de poliominós

Los poliominós ( n -minos) reciben el nombre del número n de los cuadrados que los componen:

norte Nombre norte Nombre
una monomino 6 hexamino
2 dominó 7 heptamino
3 tromino ocho octamino
cuatro tetramino 9 nonamino o enneomino
5 pentominó diez Decamino

Historia

Los poliominós se han utilizado para entretener a las matemáticas desde al menos 1907 [4] [5] y se conocen desde la antigüedad. Muchos resultados con figuras que contienen de 1 a 6 cuadrados se publicaron por primera vez en Fairy Chess Review entre 1937 y 1957 bajo el título " problemas de disección " .  El nombre "poliomino" o "poliomino" ( ing. polyomino ) fue acuñado por Solomon Golomb [1] en 1953 y luego popularizado por Martin Gardner [6] [7] .  

En 1967 la revista Science and Life publicó una serie de artículos sobre pentominós . Posteriormente se publicaron durante varios años problemas relacionados con poliominós y otras poliformas [8] .

Generalizaciones de poliominós

Dependiendo de si se permite voltear o rotar las figuras, se distinguen los siguientes tres tipos de poliominós [1] [2] :

Dependiendo de las condiciones de conectividad de las celdas vecinas, se distinguen [1] [9] [10] :

La siguiente tabla recopila datos sobre el número de figuras poliominó y sus generalizaciones. El número de cuasi - n -minos es 1 para n  = 1 y ∞ para n  > 1.

norte poliominós pseudopoliomino
bilateral unilateral fijado bilateral unilateral fijado
todos con agujeros sin agujeros
A000105 A001419 A000104 A000988 A001168 A030222 A030233 A006770
una una 0 una una una una una una
2 una 0 una una 2 2 2 cuatro
3 2 0 2 2 6 5 6 veinte
cuatro 5 0 5 7 19 22 34 110
5 12 0 12 Dieciocho 63 94 166 638
6 35 0 35 60 216 524 991 3832
7 108 una 107 196 760 3031 5931 23 592
ocho 369 6 363 704 2725 18 770 37 196 147 941
9 1285 37 1248 2500 9910 118 133 235 456 940 982
diez 4655 195 4460 9189 36 446 758 381 1 514 618 6 053 180
once 17 073 979 16 094 33 896 135 268 4 915 652 9 826 177 39 299 408
12 63 600 4663 58 937 126 759 505 861 32 149 296 64 284 947 257 105 146

Poliformas

Las poliformas  son una generalización de los poliominós, cuyas celdas pueden ser cualquier polígono o poliedro idéntico. En otras palabras, una poliforma es una figura plana o un cuerpo espacial, que consta de varias copias conectadas de una forma básica dada [11] .

Las poliformas planas (bidimensionales) incluyen poliamantes , formadas a partir de triángulos equiláteros; polihexágonos , formados por hexágonos regulares; polyabolo , que consta de triángulos rectángulos isósceles, y otros.

Ejemplos de poliformas espaciales (tridimensionales): policubos, que consisten en cubos tridimensionales; polirones ( ing.  polyrhons ), que consisten en rombododecaedros [12] .

Las poliformas también se generalizan al caso de dimensiones superiores (por ejemplo, las formadas a partir de hipercubos - polihipercubos).

Tareas

Recubrimiento de rectángulos por poliominós congruentes

El orden del poliomino P  es el número mínimo de copias congruentes de P suficientes para plegar un rectángulo. Para poliominós, a partir de las cuales no se puede agregar ningún rectángulo, el orden no está definido. El orden del poliomino P es igual a 1 si y solo si P  es un rectángulo [13] .

Si hay al menos un rectángulo que puede cubrirse con un número impar de copias congruentes de P , el poliominó P se llama poliominó impar ; si el rectángulo se puede doblar solo a partir de un número par de copias P , P se llama un poliominó par .

Esta terminología fue introducida en 1968 por D. A. Klarner [1] [14] .

Hay un conjunto de poliominós de orden 2; un ejemplo son los llamados L - poliominós [15] .

Problemas sin resolver en Matemáticas : ¿Existe un poliominó cuyo orden sea un número impar?

No existen poliominós de orden 3 ; una prueba de esto fue publicada en 1992 [16] . Cualquier poliominó cuyas tres copias puedan formar un rectángulo es en sí mismo un rectángulo y tiene orden 1. No se sabe si existe un poliominó cuyo orden sea un número impar mayor que 3 [14] .

Hay poliominós de orden 4 , 10 , 18 , 24 , 28 , 50 , 76 , 92 , 312 ; existe una construcción que permite obtener un poliominó de orden 4 s para cualquier s natural [14] .

Problemas sin resolver en matemáticas : ¿Cuál es la multiplicidad impar más pequeña posible de cubrir un rectángulo por un poliominó no rectangular?

Klarner logró encontrar un poliominó no rectangular de orden 2, 11 copias del cual pueden formar un rectángulo [1] [14] [17] , y un número impar no menor de copias de este poliominó puede cubrir el rectángulo. A octubre de 2015, no se sabe si existe un poliominó no rectangular cuyas 9, 7 o 5 copias puedan formar un rectángulo; no se conocen otros ejemplos de poliominós con una multiplicidad impar mínima de cubrir 11 (excepto el encontrado por Klarner).

Áreas mínimas

Región mínima (eng. región mínima , superforma común mínima ) para un conjunto dado de poliominós - poliominós del área más pequeña posible, que contiene cada poliominó del conjunto dado [1] [14] [18] . El problema de encontrar el área mínima para un conjunto de doce pentominós fue planteado por primera vez por T. R. Dawson en Fairy Chess Review en 1942 [18] .

Para un conjunto de 12 pentominoes, hay dos regiones mínimas de nueve celdas, que representan 2 de 1285 nonominoes [1] [14] [18] :

### ### ##### ##### # #

Véase también

Notas

  1. ↑ 1 2 3 4 5 6 7 8 9 10 Golomb S. V. Polimino, 1975
  2. ↑ 1 2 Weisstein, Eric W. Polyomino  (inglés) en el sitio web de Wolfram MathWorld .
  3. ↑ 1 2 La definición popular de poliominós que usan una torre de ajedrez no es estricta: hay subconjuntos desconectados de parquetaje cuadrado que una torre puede pasar por alto (por ejemplo, un grupo de cuatro cuadrados de un tablero de ajedrez a1, a8, h1, h8 no es un tetramino , aunque una torre situada en uno de estos campos, puede sortear otros tres campos en tres movimientos). Una definición más rigurosa de poliominós sería con la ayuda de la figura del "visir" utilizada en el ajedrez de Tamerlán : el visir mueve solo una celda horizontal o verticalmente.
  4. ↑ Henry E. Dudeney. Canterbury Puzzles, 1975, págs. 111–113
  5. ↑ Alejandro Owen Muñiz. Algunos buenos problemas de coloración de Pentomino . Consultado el 24 de octubre de 2015. Archivado desde el original el 4 de marzo de 2016.
  6. ↑ Gardner M. Rompecabezas matemáticos y entretenimiento, 1971. - Capítulo 12. Polyomino. - p.111-124
  7. ↑ Gardner M. Novelas matemáticas, 1974. - Capítulo 7. Pentominoes y polyominoes: cinco juegos y una serie de problemas. - p.81-95
  8. ↑ Science and Life Nos. 2-12 (1967), 1, 6, 9, 11 (1968), etc.
  9. ↑ Poliformas . Consultado el 22 de agosto de 2013. Archivado desde el original el 11 de septiembre de 2015.
  10. ↑ Weisstein, Eric W. Polyplet  en el sitio web de Wolfram MathWorld .
  11. ↑ Weisstein, Eric W. Polyform  en el sitio web de Wolfram MathWorld .
  12. ↑ col. Página de inicio de Sicherman. Curiosidades de Polyform Archivado el 14 de diciembre de 2014 en Wayback Machine . Catálogo de Polyrhons Archivado el 11 de septiembre de 2015 en Wayback Machine .
  13. ↑ Karl Dahlke. Mosaico de rectángulos con poliominós . Consultado el 25 de agosto de 2013. Archivado desde el original el 15 de febrero de 2020.
  14. ↑ 1 2 3 4 5 6 Golomb, S. V. Polyominoes : rompecabezas, patrones, problemas y empaques  . - 2ª ed. - Prensa de la Universidad de Princeton, 1994. - ISBN 0-691-08573-0 .
  15. ↑ Weisstein, Eric W. L-Polyomino  en el sitio web de Wolfram MathWorld .
  16. ↑ EN Stewart, A. Wormstein. Los poliominós de orden 3 no existen  //  Revista de teoría combinatoria, serie A  : revista. - 1992. - Septiembre ( vol. 61 , no. 1 ). - P. 130-136 .
  17. ↑ Michael Reid. Primos del P hexomino . Consultado el 24 de octubre de 2015. Archivado desde el original el 22 de marzo de 2016.
  18. ↑ 1 2 3 Alexandre Owen Muñiz. Superformas comunes de poliomino . Consultado el 24 de octubre de 2015. Archivado desde el original el 21 de mayo de 2017.

Literatura

Enlaces


  Ir al elemento de Wikidata  diccionarios y enciclopedias
En catálogos bibliográficos
 poliformas
Tipos de poliformas
Poliomino por número de células
Rompecabezas con policubos
tarea de apilamiento
  • Problema de cobertura exacta
  • Algoritmo
  • Enlaces
Alusiones personales
Temas relacionados
Otros rompecabezas y juegos