Akaso

La Torre de Hanoi
En 1883, el matemático francés Édouard Lucas d’Amiens publicó un problema bajo
el pseudónimo de N. Claus de Siam que, sin embargo, perduraría en la legendaria
forma que le dio DeParville al año siguiente:
"Él refirió que en el gran templo de Benarés, debajo de la cúpula que marca el
centro del mundo, yace una base de bronce en la que se encuentran fijadas tres
agujas dediamante de una codo de altura y del grueso del cuerpo de una abeja. En
una de estas agujas, Dios, en el comienzo de los siglos, colocó sesenta y cuatro
discos de oro puro, el mayor sobre el plato debronce, y los otros, en orden
decreciente de anchura, superpuestos hasta la cima. Esta es la Torre de Brahma.
Día y noche, los sacerdotes se turnan en la ocupación de transportar la torre de laprimera aguja de diamante a la tercera, sin desviarse de las reglas fijas e
inmutables impuestas por Brahma. El sacerdote no debe mover más de un disco a
la vez; y no debe colocar un disco más que enuna aguja libre o sobre un disco
mayor. Cuando siguiendo estrictamente estas recomendaciones los sesenta y
cuatro discos hayan sido transferidos de la aguja en la que Dios los colocó a la
tercera,la torre y los brahmanes se convertirán en polvo y será el fin del mundo."
(*).
Dicho esto, es evidente que a todos nos interesará saber cuándo finalizarán los
sacerdotes su tarea para hacernos unaidea del tiempo que nos queda.
Afortunadamene, el número de pasos se puede calcular fácilmente por inducción:
Si tenemos un disco, necesitaremos una única traslación.
Si tenemos dos discos,necesitaremos tres traslaciones: el pequeño a un poste; el
grande al otro; y el pequeño encima del grande.
Si tenemos n+1 discos, primero llevamos n discos a otro de los postes.
Supongamos quenecesitamos x traslaciones. Luego llevamos el disco restante (el
mayor) al tercer poste, y luego trasladamos los n discos menores encima del
mayor. Total: 2.x+1 traslaciones.
Para un disco (n = 1), tenemos...