Epsilones
Historias matemáticas
Siguenos en Blogger

 ◄
► 
Siguiente

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 De Parville 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 de diamante 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 de bronce, 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 la primera 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 en una 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 una idea 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 que necesitamos 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 una traslación = 21 - 1
  • Para dos discos (n = 2), tenemos 2·(21 - 1) + 1 = 22 - 1
  • Para n: 2(2n-1 - 1) + 1= 2n - 1
  • Total, que si n = 64, el número de traslaciones es 264 - 1 = 18.446.744.073.709.551.615.

Si los brahmanes fuesen capaces de realizar una trasferencia cada segundo (que ya es transferir), el tiempo necesario para trasladar la columna sería, aproximadamente, de 585.000.000.000 años, que viene a ser más de cien veces la edad actual de nuestro sol, lo cual es suficientemente tranquilizador, al menos en lo que respecta al problema que nos ocupa: ya encontraremos otro modo de acabar con el mundo.

En un cuento de Arthur C. Clarke titulado Los nueve mil millones de nombres de Dios (The Nine Billion names og God) se cuenta una historia parecida: unos monjes tienen la tarea de escribir mediante combinaciones de ciertos caracteres especiales todos los posibles nombres de Dios, unos nueve mil millones, tarea que según sus propios cálculos les mantendría ocupados durante unos quince mil años. La cosa es que han pensado que utilizando ordenadores podrían acortar ese tiempo a unos mucho más razonables tres meses, por lo que alquilan un equipo de programadores y un ordenador Mark V para que lleve a cabo la tarea. Lo que no saben los operarios del ordenador es que, según las creencias de los monjes, cuando todos los nombres de Dios hayan sido escritos el mundo desaparecerá...


Fuentes

 

 
Comentarios
Epsilones. Página + o - matemática de Alberto. Correo: alberto@epsilones.com. En la red desde el 4-7-2002 (ya hace). Última actualización: ver Novedades.
Siguenos en Blogger
 

 

Con esto se termina la página:

El contenido de esta página requiere una versión más reciente de Adobe Flash Player.

Obtener Adobe Flash Player