stringtranslate.com

Torre de Hanoi

Un juego de maquetas de la Torre de Hanoi (con 8 discos)
Una solución animada del rompecabezas de la Torre de Hanoi para T (4, 3)
Exposición interactiva de la Torre de Hanoi en el Museo Universum de la Ciudad de México

La Torre de Hanoi (también llamada El problema del Templo de Benarés [1] o Torre de Brahma o Torre de Lucas [2] y a veces pluralizada como Torres , o simplemente rompecabezas de la pirámide [3] ) es un juego matemático o rompecabezas que consiste en tres varillas y una serie de discos de varios diámetros , que pueden deslizarse sobre cualquier varilla. El rompecabezas comienza con los discos apilados sobre una varilla en orden de tamaño decreciente, el más pequeño en la parte superior, aproximándose así a una forma cónica . El objetivo del rompecabezas es mover toda la pila a una de las otras varillas, obedeciendo las siguientes reglas: [4]

  1. Sólo se puede mover un disco a la vez.
  2. Cada movimiento consiste en tomar el disco superior de una de las pilas y colocarlo encima de otra pila o sobre una varilla vacía.
  3. No se podrá colocar ningún disco encima de otro disco de menor tamaño.

Con tres discos, el rompecabezas se puede resolver en siete movimientos. El número mínimo de movimientos necesarios para resolver un rompecabezas de la Torre de Hanoi es 2 n − 1 , donde n es el número de discos.

Orígenes

El rompecabezas fue inventado por el matemático francés Édouard Lucas , presentado por primera vez en 1883 como un juego descubierto por "N. Claus (de Siam)" (un anagrama de "Lucas d'Amiens"), [5] [6] [7] y luego publicado como un folleto en 1889 [8] y en un volumen publicado póstumamente de Lucas' Récréations mathématiques . [9] Acompañando al juego había un folleto de instrucciones, que describía los supuestos orígenes del juego en Tonkín , y afirmaba que según la leyenda, los brahmanes en un templo en Benarés han estado llevando a cabo el movimiento de la "Torre Sagrada de Brahma ", que consiste en sesenta y cuatro discos dorados, de acuerdo con las mismas reglas que en el juego, y que la finalización de la torre conduciría al fin del mundo. [10] Numerosas variaciones sobre esta leyenda con respecto a la naturaleza antigua y mística del rompecabezas aparecieron casi de inmediato. [5]

Si la leyenda fuera cierta, y si los sacerdotes fueran capaces de mover discos a un ritmo de uno por segundo, utilizando el menor número de movimientos, les llevaría 2,64  1 segundos o aproximadamente 585 mil millones de años terminarlo, [11] lo que es aproximadamente 42 veces la edad actual estimada del universo .

Existen muchas variantes de esta leyenda. Por ejemplo, en algunas versiones, el templo es un monasterio y los sacerdotes son monjes . El templo o monasterio puede estar en varios lugares, incluido Hanoi , y puede estar asociado con cualquier religión . En algunas versiones, se introducen otros elementos, como el hecho de que la torre fue creada al principio del mundo o que los sacerdotes o monjes solo pueden hacer un movimiento por día.

Solución

El rompecabezas se puede jugar con cualquier cantidad de discos, aunque muchas versiones de juguete tienen entre 7 y 9. El número mínimo de movimientos necesarios para resolver un rompecabezas de la Torre de Hanoi con n discos es 2 n − 1 . [12]

Solución iterativa

Animación de un algoritmo iterativo que resuelve un problema de 6 discos

Una solución sencilla para el rompecabezas de juguete es alternar movimientos entre la pieza más pequeña y una pieza que no sea la más pequeña. Al mover la pieza más pequeña, muévala siempre a la siguiente posición en la misma dirección (a la derecha si el número inicial de piezas es par, a la izquierda si el número inicial de piezas es impar). Si no hay una posición de torre en la dirección elegida, mueva la pieza al extremo opuesto, pero luego continúe moviéndose en la dirección correcta. Por ejemplo, si comenzó con tres piezas, movería la pieza más pequeña al extremo opuesto y luego continuaría en la dirección izquierda después de eso. Cuando sea el turno de mover la pieza que no sea la más pequeña, solo hay un movimiento legal. Hacer esto completará el rompecabezas en la menor cantidad de movimientos. [13]

Enunciado más simple de solución iterativa

La solución iterativa equivale a la ejecución repetida de la siguiente secuencia de pasos hasta alcanzar el objetivo:

Siguiendo este enfoque, la pila terminará en la clavija B si el número de discos es impar y en la clavija C si es par.

Solución recursiva

Ilustración de una solución recursiva para el rompecabezas de las Torres de Hanoi con 4 discos. En el archivo SVG, haga clic en el botón gris para expandirlo o contraerlo

La clave para resolver un problema de forma recursiva es reconocer que se puede dividir en una colección de subproblemas más pequeños, a cada uno de los cuales se aplica el mismo procedimiento de resolución general que buscamos [ cita requerida ] , y la solución total se encuentra entonces de alguna manera simple a partir de las soluciones de esos subproblemas. El hecho de que cada uno de estos subproblemas creados sea "más pequeño" garantiza que finalmente se alcanzará el caso base. Para las Torres de Hanoi:

Suponiendo que todos los n discos están distribuidos en arreglos válidos entre las clavijas; suponiendo que hay m discos superiores en una clavija de origen , y que todos los demás discos son más grandes que m , por lo que se pueden ignorar de forma segura; para mover m discos desde una clavija de origen a una clavija de destino usando una clavija de repuesto , sin violar las reglas:

  1. Mueva m − 1 discos desde la clavija de origen a la clavija de repuesto , mediante el mismo procedimiento de resolución general . No se violan las reglas, por suposición. Esto deja el disco m como disco superior en la clavija de origen.
  2. Mueva el disco m desde la clavija de origen a la clavija de destino , lo que está garantizado que será un movimiento válido, según las suposiciones: un paso simple .
  3. Mueva el disco m − 1 que acabamos de colocar en el repuesto, desde el repuesto hasta la clavija de destino mediante el mismo procedimiento de resolución general , de modo que queden colocados encima del disco m sin violar las reglas.
  4. El caso base es mover 0 discos (en los pasos 1 y 3), es decir, no hacer nada, lo que no viola las reglas.

Luego, la solución completa de la Torre de Hanoi mueve n discos desde la clavija de origen A a la clavija de destino C, utilizando B como clavija de repuesto.

Este enfoque puede probarse matemáticamente de manera rigurosa mediante inducción matemática y a menudo se utiliza como ejemplo de recursión al enseñar programación.

Análisis lógico de la solución recursiva

Como en muchos acertijos matemáticos, encontrar una solución se hace más fácil resolviendo un problema un poco más general: cómo mover una torre de h (altura) discos desde una clavija de inicio f = A (desde) a una clavija de destino t = C (a), siendo B la tercera clavija restante y asumiendo que tf . Primero, observe que el problema es simétrico para permutaciones de los nombres de las clavijas ( grupo simétrico S 3 ). Si se conoce una solución para pasar de la clavija A a la clavija C , entonces, al cambiar el nombre de las clavijas, se puede usar la misma solución para cualquier otra elección de clavija de inicio y destino. Si solo hay un disco (o incluso ninguno), el problema es trivial. Si h = 1, entonces mueva el disco de la clavija A a la clavija C . Si h > 1, entonces en algún lugar a lo largo de la secuencia de movimientos, el disco más grande debe moverse de la clavija A a otra clavija, preferiblemente a la clavija C . La única situación que permite este movimiento es cuando todos los h − 1 discos más pequeños están en la clavija B . Por lo tanto, primero todos los h − 1 discos más pequeños deben ir de A a B . Luego mover el disco más grande y finalmente mover los h − 1 discos más pequeños de la clavija B a la clavija C . La presencia del disco más grande no impide ningún movimiento de los h − 1 discos más pequeños y puede ignorarse temporalmente. Ahora el problema se reduce a mover h − 1 discos de una clavija a otra, primero de A a B y posteriormente de B a C , pero el mismo método se puede utilizar ambas veces renombrando las clavijas. La misma estrategia se puede utilizar para reducir el problema h − 1 a h − 2, h − 3, y así sucesivamente hasta que solo quede un disco. Esto se llama recursión. Este algoritmo se puede esquematizar de la siguiente manera.

Identifique los discos en orden de tamaño creciente mediante los números naturales desde 0 hasta h (sin incluirlo) . Por lo tanto, el disco 0 es el más pequeño y el disco h − 1 el más grande.

El siguiente es un procedimiento para mover una torre de h discos desde una clavija A a una clavija C , siendo B la tercera clavija restante:

  1. Si h > 1, entonces primero use este procedimiento para mover los h − 1 discos más pequeños de la clavija A a la clavija B.
  2. Ahora el disco más grande, es decir el disco h, se puede mover de la clavija A a la clavija C.
  3. Si h > 1, entonces use nuevamente este procedimiento para mover los h − 1 discos más pequeños de la clavija B a la clavija C.

Por inducción matemática , se demuestra fácilmente que el procedimiento anterior requiere el mínimo número de movimientos posibles y que la solución obtenida es la única con este mínimo número de movimientos. Utilizando relaciones de recurrencia , el número exacto de movimientos que requiere esta solución se puede calcular mediante: . Este resultado se obtiene al observar que los pasos 1 y 3 requieren movimientos, y el paso 2 requiere un movimiento, lo que da .

Solución no recursiva

La lista de movimientos de una torre que se traslada de una estaca a otra, tal como se produce mediante el algoritmo recursivo, tiene muchas regularidades. Al contar los movimientos a partir de 1, el ordinal del disco que se moverá durante el movimiento m es el número de veces que m se puede dividir por 2. Por lo tanto, cada movimiento impar involucra al disco más pequeño. También se puede observar que el disco más pequeño atraviesa las estacas f , t , r , f , t , r , etc. para una altura impar de la torre y atraviesa las estacas f , r , t , f , r , t , etc. para una altura par de la torre. Esto proporciona el siguiente algoritmo, que es más fácil, realizado a mano, que el algoritmo recursivo.

En movimientos alternativos:

Para el primer movimiento, el disco más pequeño va a la clavija t si h es impar y a la clavija r si h es par.

Observe también que:

Con este conocimiento, se puede recuperar un conjunto de discos en el medio de una solución óptima sin más información de estado que las posiciones de cada disco:

Solución binaria

Las posiciones de los discos se pueden determinar más directamente a partir de la representación binaria (base 2) del número de movimiento (el estado inicial es el movimiento n.° 0, con todos los dígitos 0, y el estado final es con todos los dígitos 1), utilizando las siguientes reglas:

Por ejemplo, en un Hanoi de 8 discos:

Las clavijas de origen y destino para el movimiento m también se pueden encontrar de manera elegante a partir de la representación binaria de m mediante operaciones bit a bit . Para usar la sintaxis del lenguaje de programación C , el movimiento m es de clavija (m & m - 1) % 3a clavija ((m | m - 1) + 1) % 3, donde los discos comienzan en la clavija 0 y terminan en la clavija 1 o 2 según si el número de discos es par o impar. Otra formulación es de clavija (m - (m & -m)) % 3a clavija (m + (m & -m)) % 3.

Además, el disco que se va a mover se determina por el número de veces que el recuento de movimientos ( m ) se puede dividir por 2 (es decir, el número de bits cero a la derecha), contando el primer movimiento como 1 e identificando los discos por los números 0, 1, 2, etc. en orden de tamaño creciente. Esto permite una implementación informática no recursiva muy rápida para encontrar las posiciones de los discos después de m movimientos sin referencia a ningún movimiento anterior o distribución de discos.

La operación, que cuenta el número de ceros consecutivos al final de un número binario, da una solución simple al problema: los discos se numeran desde cero, y en el movimiento m , el número de disco con ceros finales se mueve la distancia mínima posible hacia la derecha (dando vuelta hacia la izquierda según sea necesario). [14]

Solución de código gris

El sistema de numeración binario de los códigos Gray ofrece una forma alternativa de resolver el problema. En el sistema Gray, los números se expresan en una combinación binaria de 0 y 1, pero en lugar de ser un sistema de numeración posicional estándar , el código Gray funciona sobre la premisa de que cada valor difiere de su predecesor en un solo bit modificado.

Si uno cuenta en código Gray un tamaño de bit igual al número de discos en una Torre de Hanoi particular, comienza en cero y cuenta hacia arriba, entonces el bit cambiado en cada movimiento corresponde al disco a mover, donde el bit menos significativo es el disco más pequeño y el bit más significativo es el más grande.

Contando los movimientos desde 1 e identificando los discos por números comenzando desde 0 en orden de tamaño creciente, el ordinal del disco a mover durante el movimiento m es el número de veces que m se puede dividir por 2.

Esta técnica identifica qué disco mover, pero no a dónde moverlo. Para el disco más pequeño, siempre hay dos posibilidades. Para los demás discos siempre hay una posibilidad, excepto cuando todos los discos están en la misma clavija, pero en ese caso o es el disco más pequeño el que debe moverse o el objetivo ya se ha logrado. Afortunadamente, hay una regla que sí dice a dónde mover el disco más pequeño. Sea f la clavija de inicio, t la clavija de destino y r la tercera clavija restante. Si el número de discos es impar, el disco más pequeño se desplaza a lo largo de las clavijas en el orden ftrftr , etc. Si el número de discos es par, esto debe invertirse: frtfrt , etc. [15]

La posición del cambio de bit en la solución del código Gray da el tamaño del disco movido en cada paso: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, ... (secuencia A001511 en la OEIS ), [16] una secuencia también conocida como función de regla , o uno más que la potencia de 2 dentro del número de movimiento. En el lenguaje Wolfram , IntegerExponent[Range[2^8 - 1], 2] + 1da movimientos para el rompecabezas de 8 discos.

Representación gráfica

El juego se puede representar mediante un gráfico no dirigido , en el que los nodos representan las distribuciones de los discos y los bordes representan los movimientos. Para un disco, el gráfico es un triángulo:

El gráfico de dos discos son tres triángulos conectados para formar las esquinas de un triángulo más grande.

Se añade una segunda letra para representar el disco más grande. Claramente, inicialmente no se puede mover.

El triángulo pequeño superior ahora representa las posibilidades de un movimiento con dos discos:

Los nodos en los vértices del triángulo más externo representan distribuciones con todos los discos en la misma clavija.

Para h + 1 discos, tome el gráfico de h discos y reemplace cada triángulo pequeño con el gráfico de dos discos.

Para tres discos el gráfico es:

El gráfico del juego del nivel 7 muestra la relación con el triángulo de Sierpiński .

Los lados del triángulo más externo representan los caminos más cortos para mover una torre de una clavija a otra. El borde en el medio de los lados del triángulo más grande representa un movimiento del disco más grande. El borde en el medio de los lados de cada triángulo siguiente más pequeño representa un movimiento de cada disco siguiente más pequeño. Los lados de los triángulos más pequeños representan movimientos del disco más pequeño.

En general, para un rompecabezas con n discos, hay 3 n nodos en el grafo; cada nodo tiene tres aristas hacia otros nodos, excepto los tres nodos de las esquinas, que tienen dos: siempre es posible mover el disco más pequeño hacia una de las otras dos clavijas, y es posible mover un disco entre esas dos clavijas excepto en la situación en la que todos los discos están apilados en una clavija. Los nodos de las esquinas representan los tres casos en los que todos los discos están apilados en una clavija. El diagrama para n  + 1 discos se obtiene tomando tres copias del diagrama de n discos (cada una representa todos los estados y movimientos de los discos más pequeños para una posición particular del nuevo disco más grande) y uniéndolos en las esquinas con tres nuevas aristas, que representan las únicas tres oportunidades para mover el disco más grande. La figura resultante tiene, por lo tanto, 3 n + 1 nodos y todavía tiene tres esquinas restantes con solo dos aristas.

A medida que se añaden más discos, la representación gráfica del juego se parecerá a una figura fractal , el triángulo de Sierpiński . Está claro que la gran mayoría de las posiciones del rompecabezas nunca se alcanzarán si se utiliza la solución más corta posible; de ​​hecho, si los sacerdotes de la leyenda utilizan la solución más larga posible (sin volver a visitar ninguna posición), les llevará 3 64  − 1 movimientos, o más de 10 23 años.

La ruta no repetitiva más larga para tres discos se puede visualizar borrando los bordes no utilizados:

Por cierto, este camino no repetitivo más largo se puede obtener prohibiendo todos los movimientos de a a c .

El ciclo hamiltoniano para tres discos es:

Los gráficos muestran claramente que:

Esto da como resultado N h 2, 12, 1872, 6563711232, ... (secuencia A125295 en la OEIS )

Variaciones

Hanoi lineal

Si todos los movimientos deben ser entre clavijas adyacentes (es decir, dadas las clavijas A, B, C, no se puede mover directamente entre las clavijas A y C), entonces mover una pila de n discos desde la clavija A a la clavija C requiere 3 n − 1 movimientos. La solución utiliza las 3 n posiciones válidas, y siempre realiza el único movimiento que no deshace el movimiento anterior. La posición con todos los discos en la clavija B se alcanza a mitad de camino, es decir, después de (3 n − 1) / 2 movimientos. [17] [18]

Hanoi cíclico

En el Hanoi cíclico, se nos dan tres clavijas (A, B, C), que están dispuestas en un círculo con las direcciones en el sentido de las agujas del reloj y en el sentido contrario a las agujas del reloj definidas como A – B – C – A y A – C – B – A, respectivamente. La dirección de movimiento del disco debe ser en el sentido de las agujas del reloj. [19] Es suficiente representar la secuencia de discos que se van a mover. La solución se puede encontrar utilizando dos procedimientos recursivos entre sí:

Para mover n discos en sentido antihorario hasta la clavija objetivo vecina:

  1. Mueva n − 1 discos en sentido antihorario hasta la clavija de destino
  2. Mueva el disco n un paso en el sentido de las agujas del reloj
  3. Mueva n − 1 discos en el sentido de las agujas del reloj hasta la clavija de inicio
  4. Mueva el disco n un paso en el sentido de las agujas del reloj
  5. Mueva n − 1 discos en sentido antihorario hasta la clavija de destino

Para mover n discos en el sentido de las agujas del reloj hasta la clavija objetivo vecina:

  1. Mueva n − 1 discos en sentido antihorario hasta una clavija libre
  2. Mueva el disco n un paso en el sentido de las agujas del reloj
  3. Mueva n − 1 discos en sentido antihorario hasta la clavija de destino

Sea C(n) y A(n) el movimiento de n discos en sentido horario y antihorario, entonces podemos escribir ambas fórmulas:

La solución para el Hanoi cíclico tiene algunas propiedades interesantes:

  1. Los patrones de movimiento de transferencia de una torre de discos de una clavija a otra clavija son simétricos con respecto a los puntos centrales.
  2. El disco más pequeño es el primero y el último en moverse.
  3. Los grupos de movimientos de los discos más pequeños se alternan con movimientos individuales de otros discos.
  4. El número de movimientos de discos especificados por C(n) y A(n) es mínimo.

Con cuatro clavijas y más allá

Aunque la versión de tres clavijas tiene una solución recursiva simple que se conoce desde hace mucho tiempo, la solución óptima para el problema de la Torre de Hanoi con cuatro clavijas (llamado rompecabezas de Reve) no fue verificada hasta 2014, por Bousch. [20]

Sin embargo, en el caso de cuatro o más clavijas, el algoritmo Frame-Stewart se conoce sin prueba de optimalidad desde 1941. [21]

Para la derivación formal del número exacto de movimientos mínimos necesarios para resolver el problema aplicando el algoritmo Frame-Stewart (y otros métodos equivalentes), consulte el siguiente artículo. [22]

Para otras variantes del problema de la Torre de Hanoi de cuatro clavijas, véase el artículo de investigación de Paul Stockmeyer. [23]

Las configuraciones de juego denominadas Torres de Bucarest y Torres de Klagenfurt producen códigos Gray ternarios y pentarios. [24]

Algoritmo Frame-Stewart

El algoritmo Frame-Stewart se describe a continuación:

El algoritmo se puede describir recursivamente:

  1. Para algunos , transfiere los discos superiores a una sola clavija que no sea la clavija de inicio o destino, realizando movimientos.
  2. Sin tocar la clavija que ahora contiene los discos superiores, transfiera los discos restantes a la clavija de destino, usando solo las clavijas restantes y realizando movimientos.
  3. Finalmente, transfiere los discos superiores a la clavija de destino, realizando movimientos.

Todo el proceso requiere movimientos. Por lo tanto, se debe elegir el recuento para el cual esta cantidad sea mínima. En el caso de 4 clavijas, el óptimo es igual a , donde es la función entera más cercana . [25] Por ejemplo, en el curso CIS 194 de UPenn sobre Haskell, la primera página de tareas [26] enumera la solución óptima para el caso de 15 discos y 4 clavijas como 129 pasos, que se obtiene para el valor anterior de k .

Se supone que este algoritmo es óptimo para cualquier número de clavijas; su número de movimientos es 2 Θ ( n 1/( r −2) ) (para r fijo ).

Caminos más cortos generales y el número 466/885

Una curiosa generalización del objetivo original del rompecabezas es empezar con una configuración dada de los discos, en la que no todos ellos están necesariamente en la misma clavija, y llegar en un número mínimo de movimientos a otra configuración dada. En general, puede resultar bastante difícil calcular una secuencia de movimientos más corta para resolver este problema. Andreas Hinz propuso una solución que se basa en la observación de que, en una secuencia de movimientos más corta, el disco más grande que se debe mover (obviamente, se pueden ignorar todos los discos más grandes que ocuparán la misma clavija tanto en la configuración inicial como en la final) se moverá exactamente una vez o exactamente dos veces.

Las matemáticas relacionadas con este problema generalizado se vuelven aún más interesantes cuando se considera el número promedio de movimientos en una secuencia más corta de movimientos entre dos configuraciones iniciales y finales de discos que se eligen al azar. Hinz y Chan Tat-Hung descubrieron de forma independiente [27] [28] (véase también [29] : Capítulo 1, p. 14  ) que el número promedio de movimientos en una torre de n discos está dado por la siguiente fórmula exacta:

Para un valor de n suficientemente grande , solo el primer y el segundo término no convergen a cero, por lo que obtenemos una expresión asintótica : , ya que . Por lo tanto, intuitivamente, podríamos interpretar la fracción de como la proporción del trabajo que uno tiene que realizar al pasar de una configuración elegida aleatoriamente a otra configuración elegida aleatoriamente, en relación con la dificultad de tener que cruzar el camino de longitud "más difícil" que implica mover todos los discos de una clavija a otra. Romik dio una explicación alternativa para la aparición de la constante 466/885, así como un algoritmo nuevo y algo mejorado para calcular el camino más corto. [30]

Hanoi magnético

En Magnetic Tower of Hanoi, cada disco tiene dos lados distintos, el norte y el sur (normalmente de color "rojo" y "azul"). Los discos no deben colocarse con los polos iguales juntos: los imanes de cada disco evitan este movimiento ilegal. Además, cada disco debe girarse a medida que se mueve.

Configuración inicial de las Torres Bicolor de Hanoi (n=4)

Torres Bicolores de Hanoi

Esta variación del famoso rompecabezas de la Torre de Hanoi se ofreció a estudiantes de 3.º a 6.º grado en el 2ème Championnat de France des Jeux Mathématiques et Logiques, celebrado en julio de 1988. [31]

Configuración final de las Torres Bicolor de Hanoi (n=4)

Las reglas del rompecabezas son básicamente las mismas: los discos se transfieren entre las clavijas de uno en uno. En ningún momento se puede colocar un disco más grande sobre uno más pequeño. La diferencia es que ahora para cada tamaño hay dos discos: uno negro y otro blanco. Además, ahora hay dos torres de discos de colores alternos. El objetivo del rompecabezas es hacer que las torres sean monocromáticas (del mismo color). Se supone que los discos más grandes en la parte inferior de las torres intercambian posiciones.

Torre de Hanoy

Una variante del rompecabezas ha sido adaptada como un juego de solitario con nueve cartas bajo el nombre de Torre de Hanoy . [32] [33] No se sabe si la ortografía alterada del nombre original es deliberada o accidental. [34]

Aplicaciones

Imagen topográfica AFM 3D de una nanohoja de paladio multicapa sobre una oblea de silicio, con una estructura similar a la de la Torre de Hanoi. [35]

La Torre de Hanoi se utiliza con frecuencia en la investigación psicológica sobre resolución de problemas . También existe una variante de esta tarea llamada Torre de Londres para el diagnóstico neuropsicológico y el tratamiento de trastornos de la función ejecutiva . [36]

Zhang y Norman [37] utilizaron varias representaciones isomórficas (equivalentes) del juego para estudiar el impacto del efecto representacional en el diseño de tareas. Demostraron un impacto en el rendimiento del usuario al cambiar la forma en que se representan las reglas del juego, utilizando variaciones en el diseño físico de los componentes del juego. Este conocimiento ha influido en el desarrollo del marco TURF [38] para la representación de la interacción humano-computadora .

La Torre de Hanoi también se utiliza como esquema de rotación de copias de seguridad cuando se realizan copias de seguridad de datos informáticos en los que intervienen varias cintas/medios. [ cita requerida ]

Como se mencionó anteriormente, la Torre de Hanoi es popular para enseñar algoritmos recursivos a estudiantes principiantes de programación. Una versión gráfica de este rompecabezas está programada en el editor de emacs , al que se accede escribiendo Mx hanoi. También hay un algoritmo de muestra escrito en Prolog . [ cita requerida ]

La Torre de Hanoi también se utiliza como prueba por los neuropsicólogos que intentan evaluar los déficits del lóbulo frontal . [39]

En 2010, los investigadores publicaron los resultados de un experimento que descubrió que la especie de hormiga Linepithema humile pudo resolver con éxito la versión de tres discos del problema de la Torre de Hanoi a través de dinámicas no lineales y señales de feromonas. [40]

En 2014, los científicos sintetizaron nanohojas de paladio multicapa con una estructura similar a la de la Torre de Hanoi. [35]

En la cultura popular

En la historia de ciencia ficción "Now Inhale", de Eric Frank Russell , un humano es mantenido prisionero en un planeta donde la costumbre local es hacer que el prisionero juegue un juego hasta que lo gane o lo pierda antes de su ejecución. El protagonista sabe que una nave de rescate podría tardar un año o más en llegar, por lo que elige jugar a Towers of Hanoi con 64 discos. Esta historia hace referencia a la leyenda sobre los monjes budistas que jugaron el juego hasta el fin del mundo. [41] [42] [43]

En la historia de Doctor Who de 1966, The Celestial Toymaker , el villano epónimo obliga al Doctor a jugar un juego de la Torre de Hanoi de diez piezas y 1023 movimientos llamado The Trilogic Game, en el que las piezas forman una pirámide cuando se apilan. [42] [44]

En 2007, el concepto del problema de las Torres de Hanoi se utilizó en El profesor Layton y la caja diabólica en los rompecabezas 6, 83 y 84, pero los discos se habían cambiado por panqueques. El rompecabezas se basaba en un dilema en el que el chef de un restaurante tenía que mover una pila de panqueques de un plato a otro con los principios básicos del rompecabezas original (es decir, tres platos sobre los que se podían mover los panqueques, no poder poner un panqueque más grande sobre uno más pequeño, etc.)

En la película de 2011 El origen del planeta de los simios , este rompecabezas, llamado en la película "Torre Lucas", se utiliza como prueba para estudiar la inteligencia de los simios. [42]

El rompecabezas aparece con regularidad en juegos de aventuras y rompecabezas . Dado que es fácil de implementar y reconocer, es muy adecuado para usarlo como rompecabezas en un juego gráfico más grande (por ejemplo, Star Wars: Knights of the Old Republic y Mass Effect ). [45] Algunas implementaciones utilizan discos rectos, pero otras disfrazan el rompecabezas de alguna otra forma. Hay una versión arcade de Sega . [46]

En el juego Sunless Sea aparece una versión de 15 discos del rompecabezas como una cerradura que da acceso a una tumba. El jugador tiene la opción de hacer clic en cada movimiento del rompecabezas para resolverlo, pero el juego advierte que se necesitarán 32.767 movimientos para completarlo. Si un jugador especialmente dedicado hace clic hasta el final del rompecabezas, se revela que completar el rompecabezas no desbloquea la puerta.

Este desafío se utilizó por primera vez en Survivor Tailandia en 2002, pero en lugar de anillos, las piezas se hicieron para parecerse a un templo. Sook Jai lanzó el desafío para deshacerse de Jed a pesar de que Shii-Ann sabía perfectamente cómo completar el rompecabezas. El problema se presenta como parte de un desafío de recompensa en un episodio de 2011 de la versión estadounidense de la serie de televisión Survivor . Ambos jugadores ( Ozzy Lusth y Benjamin "Coach" Wade ) lucharon por comprender cómo resolver el rompecabezas y recibieron la ayuda de sus compañeros de tribu.

En Genshin Impact , este rompecabezas se muestra en la misión de Faruzan, "Mecanismo de aprendizaje temprano", donde menciona que lo ve como un mecanismo y lo usa para hacer un prototipo de juguete para niños. Ella lo llama pilas de pagodas .

Véase también

Notas

  1. ^ "A000225 - OEIS". oeis.org . Consultado el 3 de septiembre de 2021 .
  2. ^ Hofstadter, Douglas R. (1985). Temas metamágicos: en busca de la esencia de la mente y los patrones . Nueva York: Basic Books. ISBN 978-0-465-04540-2.
  3. ^ Cohn, Ernst M. (1963). "Un dispositivo para demostrar algunas propiedades elementales de los números enteros". El profesor de matemáticas . 56 (2). Consejo Nacional de Profesores de Matemáticas: 84. doi :10.5951/MT.56.2.0084. ISSN  0025-5769 . Consultado el 9 de marzo de 2021 .
  4. ^ Weisstein, Eric W. "Torre de Hanoi". mathworld.wolfram.com . Consultado el 20 de octubre de 2023 .
  5. ^ ab Hinz, Andreas M.; Klavžar, Sandi; Milutinović, Uroš; Petr, Ciril (31 de enero de 2013). La Torre de Hanoi – Mitos y Matemáticas . Saltador. ISBN 978-3034802369.
  6. ^ Stockmeyer, Paul K. "La Torre de Hanoi: una bibliografía" (PDF) . Consultado el 21 de febrero de 2024 .
  7. ^ de Parville, Henri (27 de diciembre de 1883). "Revista de Ciencias". Diario de debates . Consultado el 21 de febrero de 2024 .
  8. ^ Lucas, Édouard (1889). Jeux scientifiques pour servir à l'histoire, à l'enseignement et à la pratique du calcul et du dessin (en francés). París: Chambon et Baye . Consultado el 27 de enero de 2024 .
  9. ^ Lucas, Édouard (1892). Récréations mathématiques (en francés). vol. 3. Biblioteca Albert Blanchard, 1979. p. 58.
  10. ^ Stockmeyer, Paul K. «Instrucciones de la Torre de Hanoi en inglés, página 1» . Consultado el 21 de febrero de 2024 .
  11. ^ Moscovich, Ivan (2001). 1000 juegos de ingenio: acertijos, paradojas, ilusiones y juegos . Workman. ISBN 978-0-7611-1826-8.
  12. ^ Petković, Miodrag (2009). Famosos acertijos de grandes matemáticos . Librería AMS. pág. 197. ISBN 978-0-8218-4814-2.
  13. ^ Troshkin, M. "El día del juicio final llega: un análisis no recursivo del problema recursivo de las Torres de Hanoi". Focus (en ruso). 95 (2): 10–14.
  14. ^ Warren, Henry S. (2003). "Sección 5-4: Conteo de ceros finales". Hacker's delight (1.ª ed.). Boston, MA: Addison-Wesley. ISBN 978-0-201-91465-8.
  15. ^ Miller, Charles D. (2000). "Cap. 4: Números binarios y el código Gray estándar". Ideas matemáticas (novena edición). Addison Wesley Longman. ISBN 978-0-321-07607-6. Archivado desde el original el 21 de agosto de 2004.
  16. ^ Gros, L. (1872). Teoría del Baguenodier . Lyon: Aimé Vingtrinier.
  17. ^ "Rincón de preguntas: generalización del problema de las Torres de Hanoi". math.toronto.edu . Consultado el 28 de julio de 2023 .
  18. ^ Hinz, Andreas M.; Klavzar, Sandi; Milutinovic, Uros; Petr, Ciril; Stewart, Ian (2013). La Torre de Hanoi: mitos y matemáticas (1.ª ed.). Basilea: Springer Science+Business Media . pp. 241–259. ISBN 9783034802369.
  19. ^ Gedeon, TD (1996). "Las torres cíclicas de Hanoi: una solución iterativa producida por transformación". The Computer Journal . 39 (4): 353–356. doi :10.1093/comjnl/39.4.353.
  20. ^ Bousch, T. (2014). «La quatrieme tour de Hanoi» (PDF) . Toro. Belga. Matemáticas. Soc. Simón Stevin . 21 (5): 895–912. doi : 10.36045/bbms/1420071861. S2CID  14243013. Archivado desde el original (PDF) el 21 de septiembre de 2017.
  21. ^ Stewart, BM; Frame, JS (marzo de 1941). "Solución al problema avanzado 3819". American Mathematical Monthly . 48 (3): 216–9. doi :10.2307/2304268. JSTOR  2304268.
  22. ^ Klavzar, Sandi; Milutinovi, Uro; Petrb, Ciril (2002). "Variaciones sobre el rompecabezas de la Torre de cuatro postes de Hanoi" (Posdata) . Congressus Numerantium . 102 .
  23. ^ Stockmeyer, Paul (1994). "Variaciones sobre el rompecabezas de la torre de cuatro postes de Hanoi" (Posdata) . Congressus Numerantium . 102 : 3–12.
  24. ^ Herter, Felix; Rote, Günter (2018-11-14) [2018-08-09, 2017-12, 2017-08-09, 2016-04-22]. "Enumeración de código Gray sin bucles y la Torre de Bucarest" (PDF) . Theoretical Computer Science . 748 . Berlín, Alemania: 40–54. arXiv : 1604.06707 . doi :10.1016/j.tcs.2017.11.017. ISSN  0304-3975. S2CID  4014870. Archivado (PDF) desde el original el 2020-12-16 . Consultado el 2020-12-16 .[1] (15/18/19/24 páginas)
  25. ^ "University of Toronto CSC148 Slog". 5 de abril de 2014. Consultado el 22 de julio de 2015 .
  26. ^ "UPenn CIS 194 Introducción a Haskell, tarea 1" (PDF) . Consultado el 31 de enero de 2016 .
  27. ^ Hinz, A. (1989). "La Torre de Hanói". L'Enseignement Mathématique . 35 : 289–321. doi :10.5169/sellos-57378.
  28. ^ Chan, T. (1988). "Un análisis estadístico del problema de las torres de Hanoi". Internat. J. Comput. Math . 28 (1–4): 57–65. doi :10.1080/00207168908803728.
  29. ^ Stewart, Ian (2004). Otra buena matemática en la que me has metido... Courier Dover. ISBN 978-0-7167-2342-4.
  30. ^ Romik, D. (2006). "Caminos más cortos en el grafo de la Torre de Hanoi y en autómatas finitos". Revista SIAM de Matemáticas Discretas . 20 (3): 610–622. arXiv : math/0310109 . doi :10.1137/050628660. S2CID  8342396.
  31. ^ Prasad Vithal Chaugule (2015). "Una solución recursiva al problema de las torres bicolores de Hanoi" (PDF) . Revista de Matemáticas Recreativas (4): 37–48. ISSN  2182-1976.
  32. ^ Arnold, Peter (28 de mayo de 2003). Juegos de cartas para uno. Sterling Publishing Company. ISBN 978-0-600-60727-4.
  33. ^ Hedges, Sid G. (6 de marzo de 2018). El libro de pasatiempos de todos. Read Books Ltd. ISBN 978-1-5287-8344-6.
  34. ^ "Torre de la paciencia de Hanoi (también conocida como Torre de la paciencia de Hanoi)". bbcmicro.co.uk . Consultado el 17 de octubre de 2020 .
  35. ^ ab Yin, Xi; Liu, Xinhong; Pan, Yung-Tin; Walsh, Kathleen A.; Yang, Hong (4 de noviembre de 2014). "Nanoláminas ultrafinas de paladio multicapa similares a torres de Hanoi". Nano Letters . 14 (12): 7188–94. Bibcode :2014NanoL..14.7188Y. doi :10.1021/nl503879a. PMID  25369350.
  36. ^ "Deterioros específicos de la planificación". Philosophical Transactions of the Royal Society of London. B, Biological Sciences . 298 (1089): 199–209. 1982-06-25. doi :10.1098/rstb.1982.0082. ISSN  0080-4622.
  37. ^ Zhang, J (1994). "Representaciones en tareas cognitivas distribuidas" (PDF) . Cognitive Science . 18 : 87–122. doi :10.1016/0364-0213(94)90021-3.
  38. ^ Zhang, Jiajie; Walji, Muhammad F. (2011). "TURF: Hacia un marco unificado de usabilidad de EHR". Revista de Informática Biomédica . 44 (6): 1056–67. doi : 10.1016/j.jbi.2011.08.005 . PMID  21867774.
  39. ^ Beers, SR; Rosenberg, DR; Dick, EL; Williams, T.; O'Hearn, KM; Birmaher, B.; Ryan, CM (1999). "Estudio neuropsicológico de la función del lóbulo frontal en niños con trastorno obsesivo-compulsivo que no habían recibido tratamiento psicotrópico". The American Journal of Psychiatry . 156 (5): 777–9. doi :10.1176/ajp.156.5.777. PMID  10327915. S2CID  21359382.
  40. ^ Reid, CR; Sumpter, DJ; Beekman, M. (enero de 2011). "Optimización en un sistema natural: las hormigas argentinas resuelven las Torres de Hanoi". J. Exp. Biol . 214 (Pt 1): 50–8. CiteSeerX 10.1.1.231.9201 . doi :10.1242/jeb.048173. PMID  21147968. S2CID  18819977. 
  41. ^ Russell, Eric Frank (abril de 1959). "Now Inhale". Novelettes. Astounding Science Fiction . Vol. 63, núm. 2. págs. 31–77.
    • Reimpreso: Russell, Eric Frank (2000). "Ahora inhala". En Katze, Rick (ed.). Ingredientes principales: las historias cortas seleccionadas de Eric Frank Russell . Framingham, Mass.: NESFA Press. págs. 399–417. ISBN 978-1-886778-10-8.
  42. ^ abc Bonanome, Marianna C.; Dean, Margaret H.; Dean, Judith Putnam (2018). "Grupos autosimilares". Una muestra de grupos notables: Thompson, autosimilar, Lamplighter y Baumslag-Solitar . Libros de texto compactos de matemáticas. Cham, Suiza: Springer. p. 96. doi :10.1007/978-3-030-01978-5_3. ISBN 978-3-030-01976-1.
  43. ^ Birtwistle, Graham (enero de 1985). "Las corrutinas de Hanoi". Avisos SIGPLAN de la ACM . 20 (1): 9–10. doi :10.1145/988284.988286. S2CID  7310661.
  44. ^ "La Cuarta Dimensión: El Juguetero Celestial". Doctor Who . BBC One . Consultado el 2 de abril de 2021 .
  45. ^ "Torre de Hanoi (concepto de videojuego)". Giantbomb.com . Consultado el 5 de diciembre de 2010 .
  46. ^ "Torre de Hanoi / Andamiro". Sega Amusements. Archivado desde el original el 2012-03-01 . Consultado el 2012-02-26 .

Enlaces externos