La torre de Hanoi

La torre de Hanoi

Antonio Javier Serrano Mora


Primavera de 20061

1  Un poco de historia

En el año 1883, Édouard Lucas d'Amiens (1842-1891) publicó un juego o puzle matemático llamado <<La Torre de Hanoi>> bajo el pseudónimo de Profesor N. Claus de Siam (nombre que tiene las mismas letras que el suyo auténtico), mandarín del colegio Li-Sou-Stian (el propio Lucas impartía clases en el instituto Saint-Louis). En las ilustraciones de la revista La Nature, donde el escritor francés Henri de Parville lo presentó en 1884, en la sección llamada Récréations Mathématiques, se observan, sobre una superficie rectangular de madera, tres postes verticales, uno de ellos (el de la izquierda) rotulado A y otro (el de la derecha) rotulado B. La ilustración I nos muestra que en el poste A hay insertados ocho discos de madera ordenados de mayor a menor diámetro (de abajo arriba); se trata de la posición inicial del juego. En la ilustración III se ve la posición final: los ocho discos insertados en el poste B, manteniendo el orden indicado. La ilustración II muestra una posición intermedia del desarrollo del puzle. Sólo se puede mover un disco cada vez y no se puede colocar sobre otro de diámetro menor. Estas son las únicas reglas del juego.

Figura 1 Ilustración de Poyet que acompaña al artículo de De Parville en La Nature

Ignoramos cuándo y cómo pasó a ser llamado <<Las Torres de Hanoi>>, en plural, aunque intuimos la razón: dado que en el desarrollo del juego la torre inicial es distribuida en dos y hasta en tres torres distintas varias veces, es natural que alguien se refiera al juego con el plural. En cambio, parece clara la idea de Lucas: sólo hay una torre, la formada por los discos colocados uno sobre otro al principio y al final del juego. Como quiera que sea, a lo largo de todo este tiempo, el juego se ha difundido por todo el mundo con el nombre escrito en plural.

¿Por qué de Hanoi? En esa época, finales del XIX, Francia formó, a golpe de guerras de invasión colonial, la llamada Indonesia Francesa, que duró hasta 1954 y que incluía los actuales Camboya, Laos y Vietnam. Es de suponer que la prensa francesa se refiriera a estos lugares constantemente, siguiendo el ritmo de las batallas. Hanoi (nombre que significa en chino dentro del río) es la capital de la región del norte de Vietnam, Tonkin. En la portada de la publicación de Lucas puede leerse <<Juego traído de Tonkin>> y <<Verdadero rompecabezas annamita>>. Annam es la región central de Vietnam, pero es el nombre con el que los chinos, hasta el siglo X dominadores del país, lo llamaban. Los franceses recuperaron este nombre para referirse tanto a la región central como a todo Vietnam, de forma que, en la Francia de finales del XIX, annamita era sinónimo de vietnamita.
Figura 2: Portada original del juego de Lucas, 1883
Viendo la portada del juego, el nombre del supuesto autor y la ilustración (cañas de bambú, personas asiáticas, alguien con frac en primer plano que recuerda a un mono...), se nota un cierto toque de misterio oriental. Ayer, como hoy, todo lo oriental, que esté relacionado con la meditación, tiene su público. Es curioso cómo Lucas va eligiendo y dando los datos, a parte del nombre del autor. Dice que es un juego annamita, traído de Tonkin que se llama Torre de Hanoi. ¿Caben más sitios orientales en menos espacio? Suponemos que una mezcla de interés lúdico e interés comercial conformaron toda la presentación del juego, su nombre y la leyenda que lo acompaña desde su creación.
También este juego ha sido conocido por los nombres de Las torres de Brahma y El problema del fin del mundo. Se deben, sin duda, a la leyenda a la que nos hemos referido. En las instrucciones que acompañaban al juego, Lucas incluyó una referencia a los brahmanes de Benarés (India) y a su templo, no en vano Benarés es considerada la ciudad más antigua del mundo, como afirma Fernando Sánchez Dragó, pero fue un año después, en 1884, cuando De Parville publicó su artículo en la revista La Nature y, en él, desarrolló por completo la leyenda de una forma muy poética. Dice así:
<<En el gran templo de Benarés, debajo de la cúpula que marca el centro del mundo, yace una base de bronce, en donde se encuentran acomodadas tres agujas de diamante, cada una del grueso del cuerpo de una abeja y de una altura de 50 cm aproximadamente. En una de estas agujas, Dios, en el momento de la Creación, colocó sesenta y cuatro discos de oro -el mayor sobre la base de bronce, y el resto de menor tamaño conforme se va ascendiendo-. Día y noche, incesantemente, los sacerdotes del templo se turnan en el trabajo de mover los discos de una aguja a otra de acuerdo con las leyes impuestas e inmutables de Brahma, que requieren que siemre haya algún sacerdote trabajando, que no muevan más de un disco a la vez y que deben colocar cada disco en alguna de las agujas de modo que no cubra a un disco de radio menor. Cuando los sesenta y cuatro discos hayan sido transferidos de la aguja en la que Dios los colocó, en el momento de la Creación, a otra aguja, el templo y los brahmanes se convertirán en polvo y, junto con ellos, el mundo desaparecerá>>.
[La foto de la izquierda es de Édouard Lucas]. Es interesante que, en su artículo, Henri de Parville menciona el parecido de este juego con otro llamado <<baguedaunier>> (por otros nombres <<Trapecio>> y <<Aros chinos>>), estudiado por, precisamente, Édouard Lucas, en un libro llamado Les récréations mathématiques. También el profesor N. Claus (de Siam) nos remite a esta obra de Lucas en las instrucciones del juego.
Seguramente, la Torre de Hanoi es de los juegos más conocidos en el mundo matemático. Muchos profesores lo han usado para ilustrar el método de demostración llamado de inducción completa, el concepto de recursividad, conceptos relacionados con la combinatoria, sistemas de numeración... Incluso, como veremos, podría ser usado para mostrar la creación de un fractal.

2  Análisis del puzle. Primeros resultados

Las primeras manipulaciones del puzle ponen de manifiesto muchas de las propiedades que vamos a comentar. Para seguir convenientemente la lectura del texto, sería aconsajable que el lector dispusiera de un modelo de la torre de Hanoi con el que realizar los primeros movimientos y comprobar las afirmaciones que haremos. Existen, en los mercadillos, artesanos que los fabrican en madera. El lector podrá fabricarse uno casero apilando cuatro o cinco fichas o monedas, o círculos de cartón, de diámetros crecientes.
Llamaremos THn a un juego de la Torre de Hanoi de n discos. Llamaremos postes a las agujas de diamante o a los clavos en los que se insertan los discos. En el poste A, el de la izquierda, están insertados todos los discos al principio del juego y queremos mover la torre al poste C, el de la derecha. El poste B, el central, nos servirá de ayuda para depositar temporalmente algunos discos a lo largo del procedimiento. Llamaremos Mn al mínimo número de movimientos necesarios para solucionar THn. Consideraremos ordenados los discos de menor a mayor radio, de forma que el disco 1 es el más pequeño, el disco 2 el siguiente y, así, el disco n será el más grande y, por tanto, el que reposa en la base del juego.
Es claro que M1=1, pues basta desplazar el único disco del juego desde el poste A hasta el poste C. Si n=2, entonces hay que trasladar el primer disco hasta B, el segundo hasta C y, finalmente, el tercero hasta C. Por tanto, M2=3. Si n=3, entonces hay que trasladar los dos primeros discos hasta B, lo que requerirá M2=3 movimientos; luego el tercer disco hasta C y, finalmente, los dos discos pequeños desde B hasta C, lo que aporta otros M2=3 movimientos. Por tanto, M3=2M2+1=7. Como también M2=2M1+1, postulamos que, en general, se cumple que Mn=2Mn-1+1, cosa que probaremos a continuación.
Para resolver THn hay que trasladar los n-1 discos menores hasta el poste B, lo que aporta Mn-1 movimientos; luego se traslada el disco grande (disco n) hasta C y, finalmente, se trasladan los n-1 discos menores desde B hasta C, lo que nos suma otros Mn-1. Entonces: Mn=2Mn-1+1 como queríamos demostrar.
La expresión anterior es una recurrencia. Busquemos ahora una fórmula explícita. Dado que M1=1=21-1, M2=3=22-1, M3=7=23-1, podemos postular que, en general, Mn=2n-1, cosa que probaremos por inducción.
Los primeros casos ya han sido mostrados, así que supongamos que Mn=2n-1 es cierto hasta un valor determinado n. Entonces: Mn+1=2Mn+1=2(2n-1)+1=2n+1-1, como queríamos demostrar.
Esta misma relación la establece el propio Lucas en las instrucciones de su juego, donde da una tabla hasta n=8. Además, da el asombroso número (vertiginoso lo llama él) de movimientos necesarios para que los brahmanes de Benarés completen su tarea, M64=264-1=18 446 744 073 709 551 615. Suponiendo que cada movimiento se realice en un segundo, Lucas estima que los sacerdotes tardarán más de cinco mil millones de siglos, varias veces la edad del Universo, en completar TH64. ¿Podría el lector encontrar la cifra exacta? El fin del mundo, por tanto, no está tan cerca como algunos agoreros televisivos quieren hacernos creer.
Si le damos a los postes A, B y C un orden circular, entonces cualquier movimiento de un disco puede considerarse realizado entre postes contiguos. En efecto, si el orden circular es el de ABC, es decir, el poste A está a la izquierda del poste B y a la derecha del poste C, entonces un movimiento desde A hasta B consiste en trasladar el disco un poste a la derecha; un movimiento desde A hasta C consiste en trasladar un disco un poste a la izquierda, etc.
Analicemos el juego TH4 para determinar el sentido del movimiento de cada disco. Un movimiento a la derecha será señalado con la letra d y uno a la izquierda con la letra i.
nº mov disco está en va hacia sentido
1 1 A B d
2 2 A C i
3 1 B C d
4 3 A B d
5 1 C A d
6 2 C B i
7 1 A B d
8 4 A C i
9 1 B C d
10 2 B A i
11 1 C A d
12 3 B C d
13 1 A B d
14 2 A C i
15 1 B C d
La tabla anterior pone de manifiesto las siguientes propiedades del movimiento de los discos:
La siguiente tabla recoge el juego TH4, con los números de movimiento en decimal y binario, indicando qué disco se mueve.
nº mov(m) Bin(m) se mueve
1 1 1
2 10 2
3 11 1
4 100 3
5 101 1
6 110 2
7 111 1
8 1000 4
9 1001 1
10 1010 2
11 1011 1
12 1100 3
13 1101 1
14 1110 2
15 1111 1
Por lo tanto, para saber qué disco se mueve en el movimiento m sólo hay que expresar el número m en binario y si la primera cifra (por la derecha) que es 1 es la cifra k, entonces se mueve el disco k.
Salta a la vista la relación entre el juego THn y el sistema de numeración en base 2. En un próximo apartado entraremos en más detalle.
Sabemos, de momento, cuál es el número mínimo de movimientos para solucionar THn, en qué sentido se mueve un disco determinado k, Sk, cuál es su primer movimiento, Pk, cada cuánto se mueve, Fk. Además, sabemos cómo averiguar qué disco se mueve si sabemos el número de movimiento. Otro resultado importante es el Principio de paridad: <<un disco nunca toca a otro de la misma paridad>>. Es decir, en caso de que un disco esté en contacto con otro, si es par toca a uno o dos impares y si es impar toca a uno o dos pares. Este hecho hace enunciar a Conway, Guy y Berlekamp su Regla de oro (y plata): <<Usa discos que sean alternativamente de oro y plata y nunca pongas juntos dos del mismo metal>>.
Terminaremos este apartado estableciendo cuántas veces se mueve un disco determinado k en todo el proceso de resolución de un juego THn. Analizando otra vez la tabla de TH4 se comprueba que el disco 1 se mueve 8 veces, el disco 2 se mueve 4 veces, el disco 3 se mueve 2 veces y el disco 4 se mueve una vez. De forma que diremos que en un juego THn el disco k se mueve en Qn=2n-k ocasiones. Además se observa que:
Q1+Q2+¼+Qn=2n-1+2n-2+...+2+20=2n-1=Mn
es decir, la suma de la cantidad de veces que se mueve cada disco es el número de movimientos total, como cabía esperar.
Ya se ha dicho que el disco grande, el n, sólo se mueve una vez. Su movimiento es desde el poste A al C. Se acaba de ver que que el disco n-1 se mueve sólo dos veces. Estos movimientos son: del poste A al B y de éste al C. Este resultado será importante más tarde cuando tratemos de determinar la posición de los discos a partir de un código determinado.

3  Análisis del puzle en base 2

Llamaremos código a un conjunto finito y ordenado de dígitos. Llamaremos sistema de codificación a la forma de asignar a cada posición del juego un código. Un buen sistema de codificación de cualquier juego THn debería satisfacer al menos las siguientes propiedades:
Propiedad 1 Los códigos usados y las posiciones del juego deben estar en biyección. Es decir, dada una posición podremos establecer su código y dado un código podremos establecer la posición del juego.
Propiedad 2 Los códigos usados y el número de movimiento deben estar en biyección.
Propiedad 3 Dado un código debemos ser capaces de escribir el código correspondiente a la siguiente posición del juego.
Empezaremos codificando un juego THn en base 2. Para ello estableceremos códigos de n dígitos. El primer dígito de la derecha hará referencia al disco 1 (el pequeño), el segundo dígito al segundo disco y, así, hasta el dígito n que se referirá al disco n, el más grande. Como sabemos que son necesarios un mínimo de Mn=2n-1 movimientos para completar el juego, se escribirá la secuencia de números naturales 0,1,2,3¼,2n-1 en base 2, completando a la izquierda con ceros, si es necesario, para que todos los códigos tengan n dígitos. Sirva como ejemplo la siguiente tabla relativa al juego TH5.
nº jugada base 2 nº jugada base 2
0 00000 16 10000
1 00001 17 10001
2 00010 18 10010
3 00011 19 10011
4 00100 20 10100
5 00101 21 10101
6 00110 22 10110
7 00111 23 10111
8 01000 24 11000
9 01001 25 11001
10 01010 26 11010
11 01011 27 11011
12 01100 28 11100
13 01101 29 11101
14 01110 30 11110
15 01111 31 11111
El código binario correspondiente al número natural m, Bin(m), está relacionado con el movimiento número m. Así que vemos que este sistema de codificación cumple la Propiedad 2 de un buen sistema de codificación. En efecto, si sabemos el número de movimiento m se calcula su código averiguando Bin(m). Si sabemos el código Bin(m) correspondiente a una posición dada del juego, entonces podemos averiguar el número de movimiento pasando Bin(m) a base 10. Veamos dos ejemplos:
Problema 1 En un juego TH5 se sabe que acaba de realizarse el movimiento número 23. ¿Cuál es el código de esta posición?
Simplemente hay que calcular Bin(23) y, si es necesario, añadirle ceros a la izquierda para que tenga cinco dígitos. Bin(23)=10111.
Problema 2 En un juego TH5 se sabe que el código correspondiente a una posición dada es 01011. ¿Qué movimiento se acaba de realizar?
Para saberlo, calculamos 01011 en base 10: m=8+2+1=11. Se trata del movimiento número 11.
También es sencillo ver que se cumple la Propiedad 3 del buen sistema de codificación. Dado un código Bin(m) correspondiente a una posición dada del juego, podemos averiguar el código correspondiente a la siguiente posición del juego, Bin(m+1), sin más que calcular Bin(m)+1, es decir, Bin(m+1)=Bin(m)+1. Leyendo Bin(m+1) sabremos qué disco hay que mover para pasar de la posición Bin(m) a la posición Bin(m+1). Empezando por la derecha de Bin(m+1), si el primer 1 que aparece es el dígito número k, entonces hay que mover el disco número k, como ya se dijo más arriba. Considerando que un disco sólo se mueve a un poste contiguo y calculando el sentido del movimiento del disco k, Sk, el movimiento que hay que realizar no tiene ninguna ambigüedad.
Por ejemplo, supongamos que tenemos el código Bin(m)=01010, correspondiente a un juego TH5. Entonces: Bin(m+1)=Bin(m)+1=01010+1=10111. Como el primer dígito de Bin(m+1) es un 1, entonces hay que mover el disco 1 para pasar de una posición a la otra. Como n=5 y k=1, entonces Sk=(-1)5-1+1=-1. El disco 1 se mueve hacia la izquierda. Además, pasando Bin(m) a base 10, tenemos que m=10. De forma que se trata de los movimientos décimo y décimoprimero.
Veamos ahora que también se cumple la Propiedad 1 del buen sistema de codificación. Timothy R. S. Walsh encontró la clave para relacionar este código en base 2 con la posición de los discos en cada poste. Para comprenderla mejor, llamemos al poste A poste 0, al poste B poste 1 y al poste C poste 3. El resultado de Walsh dice: <<el disco k se encuentra sobre el disco k+1 (mod 3) si y sólo si son iguales los dígitos k y k+1 del código en base 2 que representa la posición del juego>>. Este resultado, junto al Principio de paridad (o la Regla de oro de Conway) y el hecho de que el disco grande sólo se mueve una vez, nos permitirán establecer la relación posición-código satisfactoriamente. Además, para que todo vaya sin problemas, hemos de suponer un disco más, el n+1, imaginario, que reposa siempre sobre la base del poste 0 y que no se mueve nunca.
Por ejemplo, en TH5, tenemos que tras realizar el décimo noveno movimiento, el código que expresa su posición es Bin(19)=10011. Entonces, como a5=1, el disco grande ya se ha movido y está, por tanto, en el poste 2. Como a4 ¹ a5, el 4º disco no se encuentra sobre el 5º en el poste 2; tampoco podría estar en el poste 0 sobre el <<disco 6>> por el Principio de paridad, así que se encuentra en el poste 1. Como a3=a4 entonces el tercer disco se encuentra sobre el disco 4º en el poste 1. Como a2 ¹ a3, el 2º disco no se encuentra sobre el 3º en el poste 1; tampoco podría estar en el poste 0 sobre el <<disco 6>> por paridad, así que se encuentra en el poste 2. Como a1=a2 entonces el primer disco se encuentra sobre el 2º disco en el poste 2. El código corresponde a la figura siguiente.
Figura 3: Posición nº 19 de un juego TH5
Observemos que el resultado de Walsh implica que los dígitos k y k+1 de un código dado son distintos si y sólo si los discos k y k+1 no están en el mismo poste. Podemos usar esta versión de su resultado para hacer la tarea contraria: dado una posición del juego, escribir su código correspondiente. Sirva como ejemplo la posición presentada en la figura 4. Observamos que el disco grande aún no se ha movido, así que a5=0. Como el disco 4 no está sobre el 5, se debe cumplir que a4 ¹ a5 y, por tanto, a4=1. Como el disco 3 no está sobre el disco 4, entonces a3=0. Como el disco 2 no está sobre el tercer disco, a2=1. Y como el disco 1 no está sobre el 2, a1=0. De forma que el código correspondiente a esta posición es Bin(m)=01010 de donde m=10. Es la posición tras el movimiento 10.
Figura 4: Escribir el código de esta posición
Podríamos ahora resolver el problema que Javier Cilleruelo propone en la Gaceta de la RSME y cuyo enunciado es:
Problema 3 Partiendo de una pila de 10 discos en una de las clavijas, numerados de manera creciente según su tamaño, me propuse trasladar determinados discos a otra clavija respetando las reglas de las torres2 de Hanoi. Necesité 545 movimientos. ¿Qué discos trasladé sabiendo que no lo pude hacer en menos movimientos? ¿Qué discos quedaron en cada una de las clavijas?
Dado que Bin(545)=1000100001 tenemos que el disco grande ya ha sido movido pues a10 no es cero. De forma que el disco 10 se encuentra en el poste 2. Como a9 ¹ a10, el disco 9 no se encuentra sobre el 10 en el poste 2; como tampoco podría estar en el poste 0 sobre el disco imaginario 11 (por paridad), entonces deducimos que el disco 9 se encuentra en el poste 1. Como a9=a8=a7 entonces los discos 8 y 7 se encuentran también en el poste 1. Como a6 ¹ a7, el disco 6 no está sobre el 7 en el poste 1; como tampoco puede estar en el poste 2 sobre el disco 10 (por paridad), concluimos que está en el poste 0. Como a5 ¹ a6 el disco 5 no está en el poste 0 sobre el disco 6; tampoco puede estar en el poste 1 sobre el disco 7 (por paridad), concluimos que está en el poste 2 sobre el disco 10. Como a2=a3=a4=a5 concluimos que los discos 2, 3 y 4 están sobre el 5 en el poste 2. Finalmente, como a1 ¹ a2, el disco 1 no se encuentra sobre el disco 2 en el poste 2; tampoco puede estar en el poste 1 sobre el disco 7 (por paridad), de manera que tiene que estar en el poste 0 sobre el disco 6. Así que se han movido todos los discos y en el primer poste tenemos los discos 6 y 1, en el segundo los discos 9, 8 y 7 y en el último poste están los discos 10, 5, 4, 3 y 2.

4  Análisis del puzle en base 3

Acabamos de ver que, aunque es inmediato saber cuál es el número de movimiento a partir de un código en base 2, no lo es tanto lograr colocar los discos en su sitio. Para facilitar esta tarea usaremos ahora un código en base 3.
Supongamos que el juego tiene n discos. Como antes, cada posición del juego estará representada por un código de n dígitos, xh=anan-1¼a2a1 (h es el número de movimiento y x0 se refiere a la posición inicial) de forma que cada dígito ak se corresponda con el k-esimo disco, ordenados éstos de menor a mayor diámetro. Es decir, el dígito a1 representará al disco pequeño, el a2 al siguiente y, así, hasta el an que representará al mayor. Como el código es un número en base 3, los valores de cada dígito podrán ser 0, 1 ó 2, correspondiendo estos valores, respectivamente, al poste de la izquierda, al central y al de la derecha. Es decir, si, por ejemplo, ak=2, entonces el k-esimo disco está colocado en el poste número 2, el de la derecha. Así las cosas, la posición inicial se representa por el código x0=000¼00 (con n ceros) y la posición final se representa mediante el código xM=222¼22 (con n doses), siendo M el mínimo número de movimientos necesarios para resolver el puzle, que, como sabemos es M=2n-1.
Dado que, en cada movimiento, se desplaza un único disco, se puede establecer el siguiente
Teorema 1 (Diferencia entre códigos consecutivos) Si el código xh=anan-1¼a2a1 representa la posición del puzle tras el movimiento h-esimo, entonces xh+1=bnbn-1¼b2b1 se diferencia de xh en un único dígito.
Este tipo de códigos se conocen con el nombre de códigos Gray. También ahora supondremos que el orden de los postes es circular y que, por tanto, el poste 1 queda a la derecha del 0, el 2 a la derecha del 1 y el 0 a la derecha del 2. Así, cuando se mueve un disco, siempre se hace a un poste contiguo (a la derecha o a la izquierda), sumando o restando 1 al número del poste anterior. Podemos dar, entonces, los siguientes teoremas:
Teorema 2 (Diferencia entre dígitos de movimientos consecutivos) Si el número xh=anan-1¼a2a1 representa la posición del puzle tras el movimiento h-esimo y el número xh+1=anan-1¼a¢k¼a2a1 representa la siguiente posición, donde se ha movido el disco k-esimo, entonces se cumple que a¢k º ak ± 1 (mod 3).
Teorema 3 (Movimiento del disco pequeño) El movimiento del disco pequeño viene regido por la expresión a¢1 º a1 + (-1)n (mod 3).
Este teorema encaja a la perfección con todo lo que ya sabemos sobre el movimiento de los discos. Primero: el primer disco siempre se mueve en el mismo sentido (izquierda o derecha), cosa que ocurre, además, con todos los discos. Segundo: si n es par, se mueve hacia la derecha; si n es impar, hacia la izquierda. Tercero: si n es impar, el primer movimiento del disco pequeño hay que hacerlo hacia el poste final y si n es par hacia el otro.
Teorema 4 (Posibilidad de movimiento de un disco) El disco k-esimo (k ¹ 1) estaría en condiciones de ser movido (es movible) si se cumplen las siguientes condiciones: (i) ak ¹ ai "i < k (si no tiene discos encima) (ii) ai = aj  "i,j < k (si todos los discos más pequeños están en el mismo poste).
Las condiciones expresadas en el Teorema 4 son necesarias, pero no suficientes si queremos resolver el puzle en el número mínimo de movimientos. Estos cuatro teoremas, y el siguiente, pueden ser <<deducidos>> de una tabla de movimientos real para un juego concreto. Damos a continuación la tabla para TH5, donde hemos puesto en negrita el dígito correspondiente al disco que va a ser movido:
nº jugada base 3 nº jugada base 3
0 00000 16 21111
1 00002 17 21110
2 00012 18 21120
3 00011 19 21122
4 00211 20 21022
5 00210 21 21021
6 00220 22 21001
7 00222 23 21000
8 01222 24 22000
9 01221 25 22002
10 01201 26 22012
11 01200 27 22011
12 01100 28 22211
13 01102 29 22210
14 01112 30 22220
15 01111 31 22222
Teorema 5 (Movimiento general de los discos) Consideremos el juego THn. Supongamos que el k-esimo disco es movible según el Teorema 4. Sea el código xh=anan-1¼a2a1 el que representa la posición actual del puzle y sea el código xh+1=a¢na¢n-1¼a¢k¼a¢2a¢1 el que representa la siguiente posición. Sea bk º ak + Sk (mod 3), donde Sk es el sentido de movimiento del disco k. Entonces, si bk ¹ ai  "i < k se tiene que a¢k=bk y que a¢i=ai  "i ¹ k. En caso contrario, si bk=ai para algún i < k, se tiene que a¢1=b1 y a¢i=ai "i ¹ 1.
El Teorema 5 nos dice dos cosas:
(i) Si hay que elegir entre mover el disco pequeño y otro (el pequeño siempre es movible) se comprueba cuál es el poste destino del otro. Si no está ocupado por un disco menor, es decir, si el movimiento es realmente realizable, entonces se mueve el grande. En caso contrario, se mueve el pequeño.
(ii) El teorema nos brinda la fórmula para averiguar cuál es el poste destino de cada disco en cada ocasión. Si se analiza esta fórmula se verá que confirma todo lo dicho sobre movimientos de discos y, además, dice que si n es impar, los discos pares van a la derecha (sumando uno al dígito que cambia) y los impares a la izquierda (restando 1) pero si n es par, entonces los sentidos de los discos pares e impares cambian.
Analicemos ahora la bondad de este sistema de codificación. En primer lugar, que cumple la Propiedad 1 es evidente. Dado un código se pueden colocar los discos de inmediato, pues sus dígitos representan los postes en los que están insertados. Y también al revés, dado una posición se puede escribir el código sin más que fijarse en el poste en el que cada disco está colocado.
La Propiedad 3, es decir, dado un código escribir el código de la siguiente posición, se manifiesta en el Teorema 5. Para ilustrarlo, véanse los siguientes problemas:
Problema 1 Si en un juego de n=5 discos, la posición actual es xh=22002, ¿cuál es la posición siguiente?
Sólo a2=0 cumple las condiciones para ser movible expresadas en el teorema 4. Calculamos b2 º a2+(-1)5+2+1 º 0+1 º 1 (mod 3). Como 1=b2 ¹ ai "i < 2 (en realidad, i=1) entonces a¢2=b2=1 y la nueva posición es xh+1=22012.
Problema 2 Si en un juego de n=5 discos, la posición actual es xh=22012, ¿cuál es la posición siguiente?
Sólo a2=1 cumple las condiciones para ser movible expresadas en el teorema 4. Calculamos b2 º a2+(-1)5+2+1 º 1+1 º 2 (mod 3). Como b2=a1=2, este disco no se puede mover. Se mueve el pequeño: a¢1 º a1+(-1)5+1+1 º 2+(-1)7 º 1 (mod 3) y entonces la nueva posición es xh+1=22011.
Veamos ahora cómo se relaciona cada código en base 3 con el número de movimiento correspondiente, es decir, vamos a analizar la Propiedad 2.
  1. Dado el número de movimiento m encontramos el código.
    Para esta tarea vamos a construir una secuencia de números. A cada potencia 2k, con k=0,1,2,3,¼ le asignamos un número, que llamaremos <<número de Conway>> y que escribiremos Cn(2k), donde n es el número total de discos. Los números de Conway dependen de la paridad de n y se construyen de la siguiente forma:
    • Cn(2k) tiene k+1 dígitos y todos valen 1 ó 2.
    • Si n y k son de la misma paridad entonces el primer dígito de la izquierda es 1 y los demás 2.
    • Si n y k son de distinta paridad entonces el primer dígito de la izquierda es 2 y los demás 1.
    Por ejemplo: C4(20)=1; C6(21)=21; C8(22)=122; C10(23)=2111, C3(20)=2; C5(21)=12; C8(24)=12222; etc.
    Entonces, obtenido Bin(m)=anan-1¼a2a1, denotemos por a,b,c,d,¼ a los subíndices de todos los dígitos de Bin(m) que valen 1, expresados en orden creciente.
    Sea xm el código en base 3 que corresponde a la posición del juego tras el m-ésimo movimiento. Entonces xm=Cn(2a-1)ÅCn(2b-1)ÅCn(2c-1)ż, donde Å es una operación que consiste en sumar digito a dígito en módulo 3 y sin arrastre. Si es necesario, completaremos xm con ceros a la izquierda hasta que tenga n dígitos.
    Veamos un ejemplo. En un juego de n=5 discos, tras el decimotercer movimiento tenemos B(13)=01101. Entonces, tenemos que:
    x13=C5(20)ÅC5(22)ÅC5(23)=2Å211Å1222=01102
    Resolvamos ahora otra vez el problema 3 de Javier Cilleruelo enunciado más arriba, usando ahora el sistema de codificación en base 3. Podemos por tanto comparar los métodos en este caso. Se trataba de averiguar la posición de los discos tras el movimiento número 545. Calculamos Bin(545)=1000100001. Ahora hay que calcular tres números de Conway: C10(20)=1, C10(25)=211111 y C10(29)=2111111111. Ahora hacemos la suma de estos tres números dígito a dígito, sin arrastre y en módulo 3: x545 = C10(20)ÅC10(25)ÅC10(29)=2111022220 de donde deducimos, como antes, que en el primer poste (el número 0) están los discos 1 y 6, en el segundo los discos 7, 8 y 9 y en el tercer poste los discos 2, 3, 4, 5 y 10.
  2. Dado un código en base 3 encontramos el número de movimiento.
    Sea xm=anan-1¼a2a1 el código en base 3 de una posición dada tras realizar el m-ésimo movimiento. Queremos calcular m. Sea Bin(m)=bnbn-1¼b2b1 el código binario correspondiente a la misma posición. Si somos capaces de calcular Bin(m), el problema estará acabado, pues pasando Bin(m) a base 10 se obtiene m.
    El código en base 2, Bin(m), lo calculamos empezando por el disco grande, el disco n. Si an=0 el disco mayor no se ha movido aún y entonces bn=0. Si an=2, entonces el disco mayor ya se ha movido y bn=1. Como an no puede ser 1, ya no hay más casos. Es decir, si an=0 entonces bn=0 y en otro caso bn=1.
    Para el resto de dígitos de Bin(m) aplicamos el siguiente resultado: si ak ¹ ak+1 entonces bk ¹ bk+1 y si ak=ak+1 entonces bk=bk+1. De manera que un cambio de dígito en xm corresponde a un cambio de dígito en Bin(m), pero como en éste sólo hay unos o ceros queda bien definido el algoritmo de cambio de base.
    Ejemplo: En el juego TH5, supongamos xm=21001. Entonces, como a5 ¹ 0 tenemos que b5=1. Como a4 ¹ a5 entonces b5 ¹ b4=0. Así, a3 ¹ a4, entonces b4 ¹ b3=1. Como a2=a3 se cumple que b3=b2=1. Como a1 ¹ a2 se cumple que b2 ¹ b1=0. De forma que tenemos: Bin(m)=10110, de donde m=22.
La base 3 es, por tanto, un buen sistema de codificación. Además, dado que, de un código al siguiente, sólo hay cambio en un dígito, este es código Gray. Este tipo de código, pero en base 2, se suele usar para codificar el puzle llamado Aros Chinos o Trapecio, lo que, como ya dijeron De Parville y el propio Lucas, emparenta ambos juegos.

5  El grafo de Hanoi

Un juego TH5, como ya sabemos, requiere de M5=25-1=31 movimientos para ser resuelto de manera óptima, es decir, con el menor número de movimientos. Cada movimiento, como también se ha dicho ya, puede ser representado mediante un código en base 3 con cinco dígitos. En cambio, con cinco dígitos existen 35=243 códigos diferentes. ¿Representan algo los códigos no usados en el camino óptimo?
Cada uno de los códigos no usados representa una situación del juego por la que no se pasa en el camino óptimo, pero que eventualmente podría darse si elegimos un camino más largo. En realidad, como vamos a ver, se puede elegir un camino que recorra todas las situaciones posibles del juego y, por tanto, todos los códigos posibles. Este camino, que llamaremos pésimo, como hace Rodolfo Valeiras, tendrá 3n-1 movimientos. La existencia de este camino nos proporciona el resultado siguiente: sea cual sea la posición del juego (siempre que cumpla sus normas) podremos llegar, mediante movimientos legales, a la solución. Para su análisis nos ayudaremos del llamado Grafo de Hanoi, invención de Ian Stewart.
Empezaremos considerando un juego TH1, es decir, un juego donde sólo hay un disco. Tenemos que x0=0 (en notación de base 3). Del poste 0 podemos pasar al 1 ò al 2, aunque ya sabemos que lo más eficiente es pasar al 2. Si optamos por pasar al poste 1, desde éste se puede pasar al poste 2, completando el camino pésimo en dos movimientos. Estas opciones se pueden representar en forma de triángulo, como muestra la figura 5. El lado derecho de este triángulo (que une 0 con 2) es el camino óptimo. El camino pésimo consiste en recorrer los vértices 0-1-2.
Figura 5: Grafo de Hanoi para el juego TH1
Supongamos ahora que el juego tiene 2 discos. Entonces, de la posición 00 se puede pasar a 01 ó a 02 (sólo se puede mover el pequeño). De 01 podemos a 02, cerrando así un triángulo. Pero también de 01 se puede pasar a 21 y de 02 se puede pasar a 12. Ahora se analizan los movimientos legales desde 21 y desde 12 y el resultado puede presentarse en un grafo como el de la figura 6.
Figura 6: Grafo de Hanoi para el juego TH2
Como se puede observar en esta figura, todas las posibles posiciones del juego están conectadas. El lado derecho del triángulo nos sigue presentando la solución óptima (en tres movimientos, por supuesto). Para encontrar el camino pésimo debemos recorrer todo el grafo sin pasar dos veces por el mismo vértice. Esto es siempre posible. Para ello, saliendo desde 00, recorremos el primer triángulo en sentido horario, terminando en 02. Luego bajamos al vértice 12 y recorremos ese triángulo en sentido antihorario, terminando en 10. Llegamos luego al vértice 20 y recorremos ese triángulo en sentido horario. Este recorrido, dicho sea para que Euler repose tranquilo, como se ve, pasa por todos los puntos, pero no por todas las aristas, es decir, el juego pasa por todas las posiciones posibles pero no se realizan todos los movimientos posibles. Si quisiéramos, además, realizar todos los movimientos posibles una sola vez, habría que recorrer el grafo pasando por todas las aristas una sola vez, cosa que es imposible pues existen más de dos vértices de índice impar lo que imposibilita, como Euler nos enseñó, tal recorrido. Agotar todos los movimientos exigiría repetir alguno de ellos. Tal camino merecería ser llamado el peor camino.
El grafo para el juego TH2 puede ser entendido como un gran triángulo equilátero que tiene en cada vértice sendos triángulos equiláteros colocados en su interior. Los lados de los triángulos pequeños representan los movimientos del disco pequeño y los tramos no usados de los lados del grande representan los movimientos del disco grande. Es decir, el grafo de TH2 consiste en un triángulo que tiene en cada vértice un grafo de TH1. Esta forma recursiva de mirar el grafo nos permitirá construir los siguientes. En efecto, el grafo de TH3 (figura 7) es un triángulo que tiene en cada vértice un grafo de TH2.
Figura 7: Grafo de Hanoi para el juego TH3
La forma de encontrar el camino pésimo en este grafo es también recurrente y se puede encontrar de manera sencilla si recorremos las siguientes etapas:
i) Si n es par recorremos el primer triángulo pequeño en sentido horario. Si n es impar lo recorremos en sentido antihorario.
ii) Pasamos al único triángulo pequeño accesible desde el fin del recorrido anterior y lo recorremos en el sentido contrario al anterior.
iii) Repetimos el paso ii tantas veces como sea necesario hasta llegar a la última posición.
Cada lado de un triángulo pequeño representa un movimiento del disco pequeño, cada lado de un triángulo mediano que no pertenezca a un triángulo pequeño representa un movimiento del disco segundo y cada lado del triángulo grande que no pertenezca a un triángulo menor representa los movimientos del disco grande.
¿Se atreverá el lector a diseñar un grafo de Hanoi para TH4? Nosotros damos en la figura 8 el grafo de TH5 sin indicar los códigos. Un buen ejercicio sería, precisamente, ponérselos.
Figura 8: Grafo de Hanoi para el juego TH5
Por supuesto que el grafo de Hanoi para el juego THn, cuando n vaya creciendo sin límite, se convierte en un fractal. Cada una de sus partes reproduce el modelo del grafo completo.
Vamos a mencionar una curiosa relación. Si construimos un triángulo de Pascal ilimitado y sustituimos cada número par por un punto blanco y cada número impar por un punto negro, el resultado es un fractal bastante parecido al famoso estuche de Sierpinski. Para crear un estuche de Sierpinski dibuje un triángulo negro. Divídalo en cuatro triángulos iguales y pinte de blanco el central. Haga lo mismo con los tres triángulos negros pequeños y repita este proceso hasta el infinito. El resultado es bastante parecido a colorear de la forma indicada el triángulo de Pascal. El hecho es que Édouard Lucas, el creador de la Torre de Hanoi, estudió la forma de averiguar cuándo es par o impar un número del triángulo de Pascal, de forma que también contribuyó, sin saberlo, a la creación de estos fractales. Nos interesa ahora, a modo de despedida, que el lector reflexione sobre la siguiente pregunta: ¿No se parece el estuche de Sierpinski (figura ) al grafo de Hanoi?
Figura 9: Estuche de Sierpinski

Bibliografía


Footnotes:

1Primera hoja de instrucciones original de Lucas, 1883
2Obsérvese el plural


File translated from TEX by TTH, version 3.76.
On 16 Sep 2006, 20:56. más algunos ajustes del autor del artículo.