stringtranslate.com

Pentominó

Los 12 pentominós pueden formar 18 formas diferentes, y 6 de ellas (los pentominós quirales) son reflejadas.

Derivado de la palabra griega para ' 5 ', y " dominó ", un pentominó (o 5-ominó ) es un poliominó de orden 5; es decir, un polígono en el plano formado por 5 cuadrados de igual tamaño conectados borde con borde. Cuando las rotaciones y las reflexiones no se consideran formas distintas, hay 12 pentominós libres diferentes . Cuando las reflexiones se consideran distintas, hay 18 pentominós de un solo lado . Cuando las rotaciones también se consideran distintas, hay 63 pentominós fijos .

Los juegos y rompecabezas de pentominós son populares en las matemáticas recreativas . [1] Por lo general, los videojuegos como las imitaciones de Tetris y Rampart consideran que los reflejos en los espejos son distintos y, por lo tanto, utilizan el conjunto completo de 18 pentominós de un solo lado. (El propio Tetris utiliza formas de 4 cuadrados).

Cada uno de los doce pentominós satisface el criterio de Conway ; por lo tanto, cada pentominó es capaz de teselar el plano . [2] Cada pentominó quiral puede teselar el plano sin reflejarse. [3]

Historia

Comparación de los esquemas de etiquetado para las 12 posibles formas de pentominó. La primera convención de nomenclatura es la que se utiliza en este artículo. El segundo método es el de Conway.

El primer rompecabezas que contenía un conjunto completo de pentominós apareció en el libro de Henry Dudeney , The Canterbury Puzzles , publicado en 1907. [4] Los primeros mosaicos de rectángulos con un conjunto completo de pentominós aparecieron en el Problemist Fairy Chess Supplement en 1935, y se exploraron más problemas de mosaicos en el PFCS y su sucesor, el Fairy Chess Review . [5] [6] : 127 

Los pentominós fueron definidos formalmente por el profesor estadounidense Solomon W. Golomb a partir de 1953 y más tarde en su libro Polyominoes: Puzzles, Patterns, Problems, and Packings de 1965. [1] [7] Fueron presentados al público general por Martin Gardner en su columna Mathematical Games de octubre de 1965 en Scientific American . Golomb acuñó el término "pentominó" del griego antiguo πέντε / pénte , "cinco", y el -omino de dominó , interpretando fantasiosamente la "d-" de "dominó" como si fuera una forma del prefijo griego "di-" (dos). Golomb nombró a los 12 pentominós libres con letras del alfabeto latino a las que se parecen, usando el mnemónico FILiPiNo junto con el final del alfabeto (TUVWXYZ). [8] : 23 

John Horton Conway propuso un esquema de etiquetado alternativo para los pentominós, utilizando O en lugar de I, Q en lugar de L, R en lugar de F y S en lugar de N. El parecido con las letras es más forzado, especialmente para el pentominó O, pero este esquema tiene la ventaja de utilizar 12 letras consecutivas del alfabeto. Se utiliza por convención al hablar de El juego de la vida de Conway , donde, por ejemplo, se habla del pentominó R en lugar del pentominó F.

Simetría

Los pentominós F, L, N, P, Y y Z son quirales ; sumando sus reflexiones (F′, J, N′, Q, Y′, S) el número de pentominós unilaterales asciende a 18. Si las rotaciones también se consideran distintas, entonces los pentominós de la primera categoría cuentan ocho veces, los de las siguientes tres categorías (T, U, V, W, Z) cuentan cuatro veces, I cuenta dos veces y X cuenta solo una vez. Esto da como resultado 5×8 + 5×4 + 2 + 1 = 63 pentominós fijos .

Se ilustran las ocho orientaciones posibles de los pentominós F, L, N, P e Y, y las cuatro orientaciones posibles de los pentominós T, U, V, W y Z:

Para las figuras 2D en general hay dos categorías más:

Juegos

Rompecabezas de mosaicos (2D)

Ejemplos de mosaicos

Un rompecabezas de pentominó estándar consiste en colocar los pentominós en una caja rectangular, es decir, cubrirla sin superponer ni dejar espacios vacíos. Cada uno de los 12 pentominós tiene un área de 5 cuadrados unitarios, por lo que la caja debe tener un área de 60 unidades. Los tamaños posibles son 6×10, 5×12, 4×15 y 3×20.

El caso 6×10 fue resuelto por primera vez en 1960 por Colin Brian Haselgrove y Jenifer Haselgrove . [9] Hay exactamente 2339 soluciones, excluyendo variaciones triviales obtenidas por rotación y reflexión de todo el rectángulo, pero incluyendo la rotación y reflexión de un subconjunto de pentominós (que a veces proporciona una solución adicional de una manera sencilla). La caja 5×12 tiene 1010 soluciones, la caja 4×15 tiene 368 soluciones y la caja 3×20 tiene solo 2 soluciones (una se muestra en la figura y la otra se puede obtener a partir de la solución mostrada rotando, como un todo, el bloque que consiste en los pentominós L, N, F, T, W, Y y Z).

Un rompecabezas algo más sencillo (más simétrico), el rectángulo de 8×8 con un agujero de 2×2 en el centro, fue resuelto por Dana Scott en 1958. [10] Hay 65 soluciones. El algoritmo de Scott fue una de las primeras aplicaciones de un programa informático de retroceso . Las variaciones de este rompecabezas permiten colocar los cuatro agujeros en cualquier posición. Uno de los enlaces externos utiliza esta regla.

Se han descrito algoritmos eficientes para resolver tales problemas, por ejemplo, por Donald Knuth . [11] Al ejecutarse en hardware moderno , estos rompecabezas de pentominó ahora se pueden resolver en cuestión de segundos.

Patrones irresolubles

La mayoría de estos patrones se pueden resolver, con la excepción de colocar cada par de agujeros cerca de dos esquinas del tablero de tal manera que ambas esquinas solo puedan ser colocadas por un pentominó P, o forzar un pentominó T o un pentominó U en una esquina de tal manera que se cree otro agujero.

El conjunto pentominó es el único conjunto poliominó libre que se puede empaquetar en un rectángulo, con la excepción de los conjuntos monominó y dominó triviales , cada uno de los cuales consta solo de un único rectángulo.

Rompecabezas de llenar cajas (3D)

Soluciones de muestra para rompecabezas de pentacube de las dimensiones indicadas, dibujadas una capa a la vez.

Un pentacubo es un policubo de cinco cubos. De los 29 pentacubos, exactamente doce son planos (de una sola capa) y corresponden a los doce pentominós extruidos hasta una profundidad de un cuadrado.

Un rompecabezas de pentacubos o rompecabezas pentominó 3D , consiste en llenar una caja tridimensional con los 12 pentacubos planos, es decir, cubrirla sin superposición y sin huecos. Como cada pentacubo tiene un volumen de 5 cubos unitarios, la caja debe tener un volumen de 60 unidades. Los tamaños posibles son 2×3×10 (12 soluciones), 2×5×6 (264 soluciones) y 3×4×5 (3940 soluciones). [12]

Como alternativa, también se podrían considerar combinaciones de cinco cubos que sean en sí mismos tridimensionales, es decir, que incluyan más que las 12 combinaciones de cubos "planos" de una sola capa de espesor. Sin embargo, además de los 12 pentacubos "planos" formados mediante la extrusión de los pentominós, hay 6 conjuntos de pares quirales y 5 piezas adicionales, que forman un total de 29 piezas de pentacubo potenciales, lo que da 145 cubos en total (=29×5); como 145 solo se pueden empaquetar en una caja que mide 29×5×1, no se puede formar incluyendo los pentominós no planos.

Juegos de mesa comerciales

Existen juegos de mesa de habilidad basados ​​íntegramente en pentominós. Estos juegos suelen llamarse simplemente "Pentominós".

Uno de los juegos se juega en una cuadrícula de 8x8 con dos o tres jugadores. Los jugadores se turnan para colocar pentominós en el tablero de modo que no se superpongan con las fichas existentes y ninguna ficha se use más de una vez. El objetivo es ser el último jugador en colocar una ficha en el tablero. Esta versión de Pentominós se llama "Juego de Golomb". [13]

La versión para dos jugadores fue resuelta débilmente en 1996 por Hilarie Orman. Se demostró que era una victoria para el primer jugador al examinar alrededor de 22 mil millones de posiciones del tablero. [14]

Los pentominós y otras formas similares también son la base de otros juegos de mosaicos, patrones y rompecabezas. Por ejemplo, el juego de mesa francés Blokus se juega con 4 conjuntos de poliominós de colores , cada uno de los cuales consta de cada pentominó (12), tetrominó (5), triominó (2), dominó (1) y monominó (1). Al igual que el juego Pentominós , el objetivo es utilizar todas las fichas y se otorga una bonificación si se juega el monominó en el último movimiento. El jugador con menos bloques restantes gana.

El juego de la Catedral también se basa en poliominós . [15]

Parker Brothers lanzó un juego de mesa de pentominó para varios jugadores llamado Universe en 1966. Su tema está basado en una escena eliminada de la película de 1968 2001: A Space Odyssey en la que un astronauta está jugando una partida de pentominó para dos jugadores contra la computadora HAL 9000 ( se conservó una escena con un astronauta diferente jugando al ajedrez ). El frente de la caja del juego de mesa presenta escenas de la película, así como una leyenda que lo describe como el "juego del futuro". El juego viene con cuatro juegos de pentominós en rojo, amarillo, azul y blanco. El tablero tiene dos áreas jugables: un área base de 10x10 para dos jugadores con 25 cuadrados adicionales (dos filas más de 10 y una fila desplazada de cinco) en cada lado para más de dos jugadores.

El fabricante de juegos Lonpos tiene varios juegos que utilizan los mismos pentominós, pero en planos de juego diferentes. Su juego 101 tiene un plano de 5 x 11. Al cambiar la forma del plano, se pueden jugar miles de rompecabezas, aunque solo una selección relativamente pequeña de estos rompecabezas está disponible en formato impreso.

Juegos de vídeo

Literatura

Los pentominós aparecieron en una subtrama destacada de la novela Imperial Earth de Arthur C. Clarke de 1975. Clarke también escribió un ensayo en el que describió el juego y cómo se volvió adicto a él. [16]

También aparecieron en Chasing Vermeer de Blue Balliett , que se publicó en 2003 e ilustró por Brett Helquist , así como en sus secuelas, The Wright 3 y The Calder Game . [17]

En el crucigrama del New York Times del 27 de junio de 2012, la pista para una palabra de 11 letras de 37 caracteres de ancho era "Conjunto completo de 12 formas formadas por los cuadrados negros de este crucigrama". [18]

Véase también

Pedidos anteriores y siguientes

Otros

Notas

  1. ^ ab "Eric Harshbarger - Pentominós".
  2. ^ Rhoads, Glenn C. (2003). Teselación plana y búsqueda de un prototipo aperiódico . Tesis doctoral, Universidad Rutgers.
  3. ^ Gardner, Martin (agosto de 1975). "Más sobre el teselado del plano: las posibilidades de los poliominós, polidiamantes y polihexágonos". Scientific American . 233 (2): 112–115. doi :10.1038/scientificamerican0775-112.
  4. ^ "El libro electrónico del Proyecto Gutenberg de Los rompecabezas de Canterbury, de Henry Ernest Dudeney". www.gutenberg.org . Consultado el 26 de marzo de 2022 .
  5. ^ "Problemas de disección en PFCS/FCR: resumen de resultados en orden de fecha". www.mayhematics.com . Consultado el 26 de marzo de 2022 .
  6. ^ Gardner, Martin (1988). "13: Poliominós". Hexaflexágonos y otras diversiones matemáticas. The University of Chicago Press. pp. 124–140. ISBN 0-226-28254-6.
  7. ^ "people.rit.edu - Introducción - poliominó y pentominó".
  8. ^ Golomb, Solomon W. ; Lushbaugh, Warren (1965). Poliominós. Nueva York: Charles Scribner's Sons. LCCN  64-24805.
  9. ^ CB Haselgrove; Jenifer Haselgrove (octubre de 1960). "Un programa informático para pentominós" (PDF) . Eureka . 23 : 16–18.
  10. ^ Dana S. Scott (1958). "Programación de un rompecabezas combinatorio". Informe técnico n.º 1, Departamento de Ingeniería Eléctrica, Universidad de Princeton.
  11. ^ Donald E. Knuth. "Dancing links" (Postscript, 1,6 megabytes). Incluye un resumen de los artículos de Scott y Fletcher.
  12. ^ Barequet, Gill; Tal, Shahar (2010). "Resolución de acertijos generales de red". En Lee, Der-Tsai; Chen, Danny Z.; Ying, Shi (eds.). Frontiers in Algorithmics . Apuntes de clase en informática. Vol. 6213. Berlín Heidelberg: Springer Science+Business Media . págs. 124–135. doi :10.1007/978-3-642-14553-7_14. ISBN 978-3-642-14552-0.
  13. ^ Pritchard (1982), pág. 83.
  14. ^ Hilarie K. Orman. Pentominós: la victoria de un primer jugador (Pdf).
  15. ^ "Preguntas frecuentes".
  16. ^ ¿ Podrías resolver pentominós? por Arthur C. Clarke, Sunday Telegraph Magazine , 14 de septiembre de 1975; reimpreso en Clarke's Ascent to Orbit: A Scientific Autobiography , Nueva York: John Wiley & Sons, 1984. ISBN 047187910X 
  17. ^ En busca de Vermeer , de Blue Balliett, Scholastic Paperbacks, ISBN 0439372976 
  18. ^ Buckley, Mike (27 de junio de 2012). Shortz, Will (ed.). "The Crossword". New York Times . Consultado el 30 de julio de 2020 .

Referencias

Enlaces externos