Page 9 - Boletín CIMAT Agosto 2019

Como ves, pasamos los 3 discos del poste A al
poste B con solo 7 movimientos. ¿Cuántos movimientos harán falta para trasladar
una torre de 4 discos? Pensemos un poquito: para pasar una torre de 4 discos de un poste a otro, primero tenemos que mover los primeros 3 discos, para lo cual necesitamos... ¡exacto, 7 movimientos!, tal y como lo acabamos de hacer con la torres de 3 discos. Luego, nos quedaría un poste libre, a donde movemos el cuarto disco, que es el más grande. Ya llevamos 8 movimientos. Para completar el problema, trasladaremos la torre de 3 discos encima del disco más grande, lo que, una vez más, nos llevará otros
7 movimientos siguiendo los pasos que explicamos antes. En total, hemos resuelto la torre de 4 discos con
¡15 movimientos!
Ahora intententémoslo con una torre de 5 discos. Seguiremos el mismo procedimiento: primero, movemos los 4 primeros discos, para lo que necesitamos 15 movimientos; luego, movemos el disco que nos queda, el más grande, a la torre que quedó libre, y con esto sumamos 16 movimientos; por último, realizamos los 15 movimientos necesarios para poner los primeros 4 discos sobre el disco grande, para así completar nuestra misión con ¡31 movimientos!
Como seguramente has adivinado, en el caso de 6 discos también debemos hacer dos veces el traslado de los primeros 5 discos, es decir, 2x31 (62 movimientos), más un movimiento por el cambio del disco grande a otro poste, es decir, 2x31+1=63 movimientos.
Sucesivamente, podríamos continuar añadiendo
un disco cada vez y seguir la secuencia hasta llegar
a los 64 discos para saber cuántos movimientos
se necesitan, pero quizás haya otra forma de averiguarlo. Fijémonos en el número de movimientos que hemos obtenido con las torres de 1 a 6 discos:
1, 3, 7, 15, 31 y 63. Quizás esta sucesión no te diga mucho, pero, ¿qué tal si le sumamos 1 a cada número? Resulta 2, 4, 8, 16, 32 y 64.
¿Has visto esa sucesión antes?
Así es, ¡son potencias de 2!, es decir, aquellos números que se obtienen al multiplicar 2 por sí mismo cierto número de veces.
Podemos conjeturar que para n discos, el total de movimientos será 2n-1.
Ahora que sabemos esto, podemos concluir que el número de movimientos para resolver una la torre de Hanói de 64 discos es igual a 264-1, es decir...
18 446 744 073 709 551 615
(¡dieciocho trillones, cuatrocientos cuarenta y seis mil setecientos cuarenta y cuatro billones, setenta y tres mil setecientos nueve millones, quinientos cincuenta y un mil seiscientos quince movimientos!)
¿Y eso cuánto
es en unidades de tiempo? Bueno, supongamos que cada movimiento toma solo un segundo.
¿A cuántos días,
meses o años corresponde esa cantidad de segundos?
Resulta que todos esos segundos equivalen a aproximadamente
¡585 mil millones de años!,
más o menos 3 veces la edad del universo. Así que ni tú, ni tus hijos, ni los hijos de tus hijos, ni los hijos de los hijos de los hijos de tus hijos tienen de qué preocuparse por los monjes de Benarés ni por sus torres de Hanói.
Matemorfismos Boletín Mensual 9 de Información