sábado, 3 de mayo de 2008

Verdadera historia de las torres de Hanoi y método para contar todos los movimientos

Veamos cómo obtener la solución al artículo publicado el 04/03/08 >(Ir al artículo inicial)
Las Torres de Hanoi es un rompecabezas inventado por el matemático francés Édouard Lucas , en 1883.
Según se indica en la caja donde venía el juego, éste fue traído de Tonkin por el profesor N. Claus de Siam, mandarín de la Escuela de Li-Sou-Stian, (anagrama de Lucas d´Amiens de la escuela de Saint-Louis, de donde el matemático era profesor) y para añadir encanto e interés por el juego, Édouard Lucas, inventó la leyenda del templo de Benarés .

Veamos como se calcula el número de movimientos:

1.- Suponemos dos discos:
Si tenemos dos discos el a (pequeño) y el b (mayor) en las varilla 1 y debemos pasarlos a la varilla 3 los movimientos serían: a2-b3-a3 .

TOTAL: 3 movimientos ( dos al cuadrado menos 1)

2.- Suponemos tres discos:
Si tenemos tres discos a, b y c en la varilla 1 los movimientos serían a3-b2-a2-c3-a1-b3-a3 .

TOTAL: 7 movimientos (dos al cubo menos uno)


(Aprovechando el caso anterior: tres movimientos para pasar dos discos a la varilla 2 , un movimiento pasar el grande a la varilla 3 y tres movimientos para pasar los dos de la varilla dos a la varilla tres). ( 3 + 1 + 3 =7 movimientos )

3.- Suponemos 4 discos

Si tenemos 4 discos a, b, c y d en la varilla 1 los movimientos serían : a2-b3-a3-c2-a1-b2-a2-d3-a3-b1-a1-c3-a2-b3-a3. TOTAL 15 movimientos. ( dos a la cuarta menos uno)

( Aprovechando el caso 3, pasamos los tres discos de arriba de la varilla 1 a la varilla 2 ( 7 movimientos), luego el disco grande a la varilla 3 ( 1 movimiento) y por último los tres discos de la varilla 2 a la 3 (7 movimientos). (7 + 1 + 7 = 15 movimientos)

4.- Suponemos 5 discos:

Con 5 discos , utilizando el de 4 sería análogo 15+1+15 = 31 movimientos

TOTAL: 31 movimientos. ( dos a la quinta menos uno)


Y así......cuando tengamos 64 discos el número de movimientos necesario sería de dos elevado a la 64 menos uno que es 18.446.744.073.709.551.615 movimientos

¿ Cuántos años tardaría en llegar el fin del mundo?

Calculemos ahora cuántos años tardarían en realizarse todos esos movimientos suponiendo que si se hiciese cada movimiento en un segundo.
a) Aproximamos el número de movimientos por 18.446.744 x 10 elevado a la 12
b) Cada día tiene 86.400 segundos, cada año 365,24 días luego un año tiene 31.556.736 segundos.
c) Si dividimos el número de segundos total entre los que tiene un año obtendremos 0.58455815 años
d) ahora se multiplica por 10 a la 12 y que nos da 584.558.150.000 años es decir, casi 6 mil millones de siglos tardarían en resolver este rompecabezas.
Luego, debemos estar tranquilos por ahora.