Un pentomino (o 5-omino) es un poliomino de orden 5, es decir, un polígono en el plano formado por 5 cuadrados de igual tamaño conectados de borde a borde. Cuando las rotaciones y reflexiones no se consideran formas distintas, hay 12 pentominós libres diferentes . Cuando los reflejos se consideran distintos, hay 18 pentominós unilaterales . Cuando las rotaciones también se consideran distintas, hay 63 pentominós fijos .
Los rompecabezas y juegos de mosaico Pentomino son populares en las matemáticas recreativas . [1] Por lo general, los videojuegos como las imitaciones de Tetris y Rampart consideran que los reflejos del espejo son distintos y, por lo tanto, utilizan el conjunto completo de 18 pentominós unilaterales.
Cada uno de los doce pentominós satisface el criterio de Conway ; de ahí que todo pentomino sea capaz de embaldosar el avión. [2] Cada pentomino quiral puede enlosar el plano sin reflejarse. [3]
Historia
Los pentominós fueron definidos formalmente por el profesor estadounidense Solomon W. Golomb a partir de 1953 y más tarde en su libro de 1965 Polyominós: rompecabezas, patrones, problemas y empaquetaduras . [1] [4] Fueron presentados al público en general por Martin Gardner en su columna Mathematical Games de octubre de 1965 en Scientific American . Golomb acuñó el término "pentomino" del griego antiguo πέντε / pénte , "cinco", y el -omino de dominó , interpretando fantasiosamente la "d-" de "domino" como si fuera una forma del prefijo griego "di- " (dos). Golomb nombró a los 12 pentominós libres según las letras del alfabeto latino al que se asemejan.
John Horton Conway propuso un esquema de etiquetado alternativo para los pentominós, usando 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 tenso, especialmente para el O pentomino, pero esto El esquema tiene la ventaja de utilizar 12 letras consecutivas del alfabeto. Se usa por convención al discutir el Juego de la vida de Conway , donde, por ejemplo, se habla de R-pentomino en lugar de F-pentomino.
Simetría
- F, L, N, P e Y se pueden orientar de 8 formas: 4 por rotación y 4 más para la imagen especular. Su grupo de simetría consiste solo en el mapeo de identidad .
- T y U se pueden orientar de 4 formas mediante rotación. Tienen un eje de reflexión alineado con las líneas de la cuadrícula. Su grupo de simetría tiene dos elementos, la identidad y el reflejo en una línea paralela a los lados de los cuadrados.
- V y W también se pueden orientar de 4 formas mediante rotación. Tienen un eje de simetría de reflexión a 45 ° de las líneas de la cuadrícula. Su grupo de simetría tiene dos elementos, la identidad y un reflejo diagonal.
- Z se puede orientar de 4 formas: 2 por rotación y 2 más para la imagen especular. Tiene simetría puntual, también conocida como simetría rotacional de orden 2. Su grupo de simetría tiene dos elementos, la identidad y la rotación de 180 °.
- Puedo orientarme de 2 formas por rotación. Tiene dos ejes de simetría de reflexión, ambos alineados con las líneas de la cuadrícula. Su grupo de simetría tiene cuatro elementos, la identidad, dos reflejos y la rotación de 180 °. Es el grupo diedro de orden 2, también conocido como el grupo de cuatro Klein .
- X solo se puede orientar de una manera. Tiene cuatro ejes de simetría de reflexión, alineados con las líneas de cuadrícula y las diagonales, y simetría rotacional de orden 4. Su grupo de simetría, el grupo diedro de orden 4, tiene ocho elementos.
Los pentominós F, L, N, P, Y y Z son quirales ; sumando sus reflexiones (F ′, L ′, N ′, Q, Y ′, Z ′) lleva el número de pentominós unilaterales a 18. Si las rotaciones también se consideran distintas, entonces los pentominós de la primera categoría cuentan ocho veces, el 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 .
Por ejemplo, las ocho posibles orientaciones de los pentominós L, F, N, P e Y son las siguientes:
Para las figuras 2D en general, hay dos categorías más:
- Siendo orientable de 2 formas mediante una rotación de 90 °, con dos ejes de simetría de reflexión, ambos alineados con las diagonales. Este tipo de simetría requiere al menos un heptomino .
- Siendo orientables de 2 maneras, que son imágenes especulares de cada uno, por ejemplo, una esvástica . Este tipo de simetría requiere al menos un octomino .
Construir dimensiones rectangulares
Un rompecabezas de pentomino estándar consiste en colocar en mosaico una caja rectangular con los pentominós, es decir, cubrirla sin superposición y sin espacios. 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 de 6 × 10 fue resuelto por primera vez en 1960 por Colin Brian y Jenifer Haselgrove . [5] 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 simple). La caja de 5 × 12 tiene 1010 soluciones, la caja de 4 × 15 tiene 368 soluciones y la caja de 3 × 20 tiene solo 2 soluciones (una se muestra en la figura y la otra se puede obtener de la solución que se muestra girando, en su conjunto, el bloque que consta de los pentominós L, N, F, T, W, Y y Z).
Un rompecabezas algo más fácil (más simétrico), el rectángulo de 8 × 8 con un agujero de 2 × 2 en el centro, fue resuelto por Dana Scott ya en 1958. [6] 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. 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 ajustadas por un P-pentomino, o forzando un T-pentomino o U-pentomino en un esquina de modo que se cree otro agujero.
Se han descrito algoritmos eficientes para resolver tales problemas, por ejemplo, por Donald Knuth . [7] Estos rompecabezas de pentomino se ejecutan en hardware moderno y ahora se pueden resolver en cuestión de segundos.
La solución de mosaicos de rectángulos de poliominós con n celdas existe solo para n = 0, 1, 2 y 5; los tres primeros son triviales.
Llenado de cajas
Un pentacubo es un policubo de cinco cubos. De los 29 pentacubos, exactamente doce pentacubos son planos (1 capa) y corresponden a los doce pentominós extruidos a una profundidad de un cuadrado.
Un pentacubo o un pentomino 3D , equivale a llenar una caja tridimensional con los 12 pentacubos planos, es decir, cubrirla sin superposición y sin huecos. Dado que cada pentacubo tiene un volumen de 5 unidades de cubos, 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). A continuación se muestra una solución para cada caso. [8]
Alternativamente, también se podrían considerar combinaciones de cinco cubos que son en sí mismos 3D, es decir, que no forman parte de una capa de cubos. Sin embargo, además de los 12 pentominós extruidos, 6 conjuntos de pares quirales y 5 piezas suman un total de 29 piezas, lo que da como resultado 145 cubos, que no formarán una caja 3D (ya que 145 solo pueden ser 29 × 5 × 1, que el no -los pentominós planos no pueden encajar).
Juego de mesa
Hay juegos de mesa de habilidad basados completamente en pentominós. Estos juegos a menudo se denominan simplemente "Pentominós".
Uno de los juegos se juega en una cuadrícula de 8 × 8 por dos o tres jugadores. Los jugadores se turnan para colocar pentominós en el tablero para que no se superpongan con las fichas existentes y no se use ninguna ficha más de una vez. El objetivo es ser el último jugador en colocar una ficha en el tablero. Esta versión de Pentominoes se llama "Golomb's Game". [9]
La versión para dos jugadores ha sido 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 en el tablero. [10]
Los pentominós y formas similares también son la base de una serie de otros juegos de mosaico, patrones y rompecabezas. Por ejemplo, el tablero de juego francés Blokus se juega con 4 conjuntos de colores de polyominoes , cada uno consistente en cada pentomino (12), tetromino (5), triominó (2) Dominó (1) y monomino (1). Al igual que el juego Pentominoes , el objetivo es usar todas tus fichas, y se otorga una bonificación si el monomino se juega en el último movimiento. El jugador con la menor cantidad de bloques restantes gana.
El juego de la Catedral también se basa en poliominós . [11]
Parker Brothers lanzó un juego de mesa pentomino multijugador llamado Universe en 1966. Su tema se basa en una escena eliminada de la película de 1968 2001: A Space Odyssey en la que un astronauta está jugando un juego de pentomino para dos jugadores contra la computadora HAL 9000 ( se retuvo 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 usan los mismos pentominós, pero en diferentes planos de juego. Su juego 101 tiene un plano de 5 x 11. Al cambiar la forma del avión, se pueden jugar miles de rompecabezas, aunque solo una selección relativamente pequeña de estos rompecabezas está disponible impresa.
Literatura
El primer problema del pentomino, escrito por Henry Dudeney , se publicó en 1907 en Canterbury Puzzles. [12]
Los pentominós aparecieron en una subtrama prominente de la novela Imperial Earth de Arthur C. Clarke de 1975 . Clarke también escribió un ensayo en el que describía el juego y cómo se enganchó a él. [13]
También se presentaron en azul Balliett 's Chasing Vermeer , que fue publicado en 2003 e ilustrada por Brett Helquist , así como sus secuelas, The Wright 3 y La Calder juego . [14]
Videojuegos
- Tetris se inspiró en los rompecabezas de pentominos, aunque usa tetrominós de cuatro bloques. Algunos clones y variantes de Tetris, como el juego 5 incluido con Plan 9 de Bell Labs y Magical Tetris Challenge , usan pentominós.
- Daedalian Opus usa rompecabezas de pentomino durante todo el juego.
Ver también
Pedidos anteriores y siguientes
- Tetromino
- Hexomino
Otros
- Video-enciclopedia sobre Pentamino
- Rompecabezas de mosaico
- Juego de mesa de la catedral
- Solomon W. Golomb
Notas
- ^ a b Eric Harshbarger - Pentominós
- ^ Rhoads, Glenn C. (2003). Azulejos planos y la búsqueda de un prototipo aperiódico . Tesis doctoral, Universidad de Rutgers.
- ^ Gardner, Martin (agosto de 1975). "Más sobre embaldosar el avión: las posibilidades de poliominós, poliamantes y polihexes". Scientific American . 233 (2): 112-115.
- ^ people.rit.edu - Introducción - polyomino y pentomino
- ^ CB Haselgrove; Jenifer Haselgrove (octubre de 1960). "Un programa de computadora para Pentominoes" (PDF) . Eureka . 23 : 16-18.
- ^ Dana S. Scott (1958). "Programación de un rompecabezas combinatorio". Informe técnico No. 1, Departamento de Ingeniería Eléctrica, Universidad de Princeton.
- ^ Donald E. Knuth. "Enlaces de baile" (Postscript, 1,6 megabytes). Incluye un resumen de los artículos de Scott y Fletcher.
- ^ Barequet, Gill; Tal, Shahar (2010). "Resolver rompecabezas de celosía general". En Lee, Der-Tsai; Chen, Danny Z .; Ying, Shi (eds.). Fronteras en algoritmos . Berlín Heidelberg: Springer Science + Business Media . pp. 124 -135. doi : 10.1007 / 978-3-642-14553-7_14 .
- ^ Pritchard (1982) , p. 83.
- ^ Hilarie K. Orman. Pentominoes: Una victoria del primer jugador (Pdf).
- ^ Preguntas frecuentes
- ^ Pentominós
- ^ ¿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
- ^ Persiguiendo a Vermeer , por Blue Balliett, Scholastic Paperbacks, ISBN 0439372976
Referencias
- Persiguiendo a Vermeer , con información sobre el libro Persiguiendo a Vermeer y un tablero de pentomino de hacer clic y arrastrar.
- Pritchard, DB (1982). "Juego de Golomb". Juegos mentales . Penguin Books Ltd . págs. 83–85. ISBN 0-14-00-5682-3.
enlaces externos
- Configuraciones y soluciones de Pentomino Una lista exhaustiva de soluciones para muchos de los problemas clásicos que muestra cómo se relaciona cada solución con las demás.