la_torre_de_hanoi

Juegos Matemáticos
La Torre de Hanói y los Qn Grafos
Mª Milagros Latasa Asso
Revista de Investigación

ISSN 2174-0410

1 de octubre de 2011
Resumen
La Torre de Hanói es uno de los hallazgos matemáticos más
ingeniosos de la matemática recreativa. Gracias a una leyenda con tinte
oriental hoy se conoce de modo universal. Se describen en este artículo
las relaciones entre las soluciones delrompecabezas y los ciclos
hamiltonianos en los grafos Qn.
Palabras Clave: Grafo, Juegos, Hanói

1. La leyenda
El matemático francés Édouard Lucas d’Amiens con el pseudónimo de
profesor N. Claus de Siam (anagrama de Lucas d'Amiens), mandarín del
Colegio de Li–Sou-Stian (una nueva permutación de letras, esta vez de las de
las de las palabras Saint Louis), ideó y dio a conocer este problema en 1883. Secomercializó como un juego con el nombre de “La Torre de Hanói”.
El material del rompecabezas lo forman tres pivotes sujetos en una base
horizontal y un cierto número de discos de distintos diámetros que se colocan
en uno de los pivotes extremos. En la parte baja se coloca el de mayor
diámetro y encima los de diámetros menores en orden decreciente.
El objetivo del juego consiste en pasar los discos deun extremo al otro
siguiendo unas precisas normas que son:
•
•
•

En cada movimiento solo puede moverse un disco.
El número de movimientos debe ser el menor posible
No se puede colocar nunca un disco sobre otro de menor diámetro.

1

Juegos Matemáticos - La Torre de Hanói y los Qn grafos

Mª Milagros Latasa Asso

La Torre de Hanói tuvo desde su comienzo un gran éxito y se dio a
conocer con unaleyenda que perfeccionó el escritor Henri de Parville al año
siguiente:
“En el gran templo de Benarés, debajo de la cúpula que marca el
centro del mundo, yace una base de bronce, en donde se encuentran
acomodadas 3 agujas de diamante, cada una del grueso del cuerpo de
una abeja y de una altura de 50 cm aproximadamente. En una de
estas agujas, Dios, en el momento de la creación, colocó 64 discos deoro, el mayor sobre el plato de bronce y el resto, de menor tamaño,
conforme se llega a la cima. Día y noche, incesantemente, los
sacerdotes del templo mueven los discos de una aguja a otra de
acuerdo con las leyes impuestas e inmutables de Brahma, que
requieren que los sacerdotes se encuentren todo el tiempo laborando,
no muevan más de un disco a la vez y que deben colocar el disco en
alguna de lasagujas de modo que no cubra a un disco de radio
menor. Cuando los 64 discos hayan sido transferidos de la aguja en
la que Dios colocó los discos, en el momento de la creación, a la otra
aguja, el templo y los brahmanes se convertirán en polvo y junto con
ellos el mundo desaparecerá.”
Texto original de Henri de Parville (de 1884)
Este final nos invita a averiguar el número de movimientos que hande
realizar los monjes de Benarés para cumplir con el mandato de Brahma. Tal
vez el fin del mundo esté próximo.

Figura 1: Portada original
Fuente: www.cs.wm.edu/~pkstoc/toh.html

Revista “Pensamiento Matemático” - Número 1 - Oct'11
ISSN 2174-0410

2

Juegos Matemáticos - La Torre de Hanói y los Qn grafos

Mª Milagros Latasa Asso

2. Pasarán millones de años
Para resolver el problema de la torrede Hanói con n+1 discos, primero se
trasladan los n discos de menor diámetro al poste central. Se necesitarán
para ello x movimientos. A continuación se mueve el disco de mayor
diámetro al tercer poste, y finalmente los n discos menores encima del mayor.
En total serán precisos 2x+1 movimientos.
Para un disco se necesitarán 21-1 movimientos.
Para dos discos 2·(21 - 1) + 1 = 22 - 1 movimientos.
...Para n discos el número de movimientos será: 2 (2n-1 - 1) + 1= 2n - 1
Luego, para n = 64, el número de movimientos necesario para resolver el
puzzle es
264 - 1 = 18.446.744.073.709.551.615
Si los sacerdotes del templo de Benarés fuesen capaces de mover un disco
cada segundo, sería necesario algo más de medio billón de años para
trasladar la torre de Hanói de un extremo a otro.

3. Los Qn grafos...