1690. Las torres de Hanói

     Llevé a clase un juego antiguo que se llama "Las Torres de Hanói". Consiste en diez discos del mismo grosor y distintos radios (no hay dos radios iguales), que están perforados por sus centros para que se puedan ensartar en tres postes verticales fijos. Inicialmente los diez discos están apilados en un mismo poste formando una especie de cono escalonado (torre de Hanói) ordenados según sus radios (el mayor abajo y el menor arriba).

    El objetivo del juego consistía en trasladar la torre del primer poste al tercer poste mediante la menor cantidad de movimientos legales. Un movimiento legal consiste en sacar de un poste el disco superior (menor) de una torre e insertarlo en otro poste de modo que no caiga encima de otro disco aún menor. Cuando la clase hubo examinado el juego pregunté cuál era ese mínimo número de movimientos legales para conseguir el traslado. Pepé Chapuza no dejó que los demás lo pensaran...

    ¡Mil veintitrés!

    Los compañeros y yo mismo le pedimos explicaciones y Pepe se limitó a decir...

    Profe, mire. Si hubiera N discos, serían 2^N − 1, así que para N = 10, son 2¹⁰ − 1 = 1023.

    Pepe dio un respuesta más general aún. Habrá que dar más explicaciones...

SOLUCIÓN

    Nina Guindilla demostró la fórmula por inducción:

    Mire, profe. La fórmula vale para trasladar una torre entre dos postes cualesquiera... 
    Si solo hay un disco basta con un movimiento legal, y la fórmula se cumple: 2¹ − 1 = 1

    Si suponemos la fórmula cierta para N discos, para N+1 podemos primero trasladar los N discos menores a un poste (el segundo) en 2^N − 1 movimientos, después el disco mayor al otro poste (el tercero) en 1 movimiento, y finalmente los N discos menores a este poste (el tercero) sobre el disco mayor en 2^N − 1 movimientos para formar la torre entera de N+1 discos. Sumando...

2^N − 1 + 1 + 2^N − 1 = 2·2^N − 1 = 2^N+1 − 1

    Nina comentó que 1023 era también el número hasta el que se podía contar con nuestros diez dedos utilizando el sistema binario... Y que a cada dedo le correspondía un disco... Y entonces propuso dos problemas diabólicos...

    A cada dedo le corresponde una potencia de dos: 1, 2, 4, 8, 16, 32, 64, 128, 256 y 512. A cada combinación de dedos levantados le corresponde la suma de los valores correspondientes. ¿Qué combinación de dedos corresponde al número 666?

    ¿Cuál es la disposición de las torres de Hanói después de 666 de los 1023 movimientos legales?

RESOLUCIÓN

    Yoyó Gaviota levantó estos dedos no sin dificultad...

    512 + 128 + 16 + 8 + 2 = 666

    Profe, mire. Estos dedos se corresponden con los unos de 666 en binario: 1010011010.

    Para las torres de Hanói tenemos que el polinomio P(x) = x⁹ + x⁷ + x⁴ + x³ + x (que Ruffini escribe 1 0 1 0 0 1 1 0 1 0) cumple que P(2) = 666 y, aplicando el teorema del resto, tendremos que 666 = P(x) − C(x)·(x−2) donde C(x) es el cociente de la división de P(x) entre (x−2). Ahora bien, para x = 1 tenemos que 666 = P(1) + C(1), que es la suma de los coeficientes del polinomio P(x) + C(x). Estos diez coeficientes son los movimientos de los diez discos...

    Mire, profe. Si asignamos los números 0, 1 y 2 a los postes de izquierda a derecha, el movimiento de un disco azul ha de ser +1 (mod 3) y el de un disco rojo ha de ser +2 (mod 3), así que solo tenemos que calcular en módulo 3 los movimientos de cada disco...

    Yoyó hizo los cálculos y a continuación colocó los discos en sus postes (sin hacer los 666 movimientos)...

    Dejaremos que el lector justifique los cálculos de Yoyó.