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:
- Un determinado disco k se mueve siempre en el mismo
sentido. Además, todos los discos pares se mueven en el mismo
sentido y todos los discos impares en el sentido contrario.
Considerando el juego THn, podemos deducir el sentido de
movimiento de cualquier disco k si consideramos que el disco n
sólo se mueve una vez, desde el poste A hasta el poste C, es
decir, hacia la izquierda. De forma que el disco k se mueve
hacia la izquierda si y sólo si k tiene la misma la misma
paridad que n. Si asumimos que ir hacia la izquierda tiene un
valor -1 e ir hacia la derecha tiene un valor +1 y que
representamos el sentido del movimiento del disco k con Sk,
entonces Sk=(-1)n-k+1. En efecto, si n y k tienen la
misma paridad entonces n-k+1 es un número impar y Sk=-1; si
n y k tienen distinta paridad, entonces n-k+1 es un número
par y Sk=+1.
- En el juego TH4, el primer movimiento del disco 1 se
realiza en el movimiento 1, el primero del disco 2 se realiza en
el 2, el primero del 3 en el movimiento 4, el primero (y único)
del disco 4 en el movimiento 8. Entonces, el primer movimiento del
disco k, Pk, en un juego THn se realiza en el movimiento
2k-1, es decir, Pk=2k-1. En efecto, para mover por
primera vez el disco k hay que trasladar previamente los k-1
discos menores a otro poste y, además, todos tienen que estar en
el mismo pues, de otra manera, el disco k no se podría mover.
Por tanto, hay que realizar Mk-1 movimientos antes de mover
el disco k y, por tanto, Pk=Mk-1+1=2k-1-1+1=2k-1,
como
queríamos demostrar.
- En la tabla anterior también se observa que el disco 1 se
mueve cada 2 movimientos, el disco 2 cada 4, el disco 3 cada 8...
En efecto, en un juego THn el disco k se mueve cada Fk=2k
movimientos. Llamamos al número Fk frecuencia de movimientos
del disco k. Para mostrar este resultado con mayor claridad, sea
An la sucesión formada por los números de los discos que se
mueven, en el mismo orden en el que son movidos, a lo largo de
todo el juego THn. Entonces, A1=1;
A2=1,2,1=A1,2,A1; A3=1,2,1,3,1,2,1=A2,3,A2¼;
An=An-1,n,An-1. En el desarrollo de An se observará
que, efectivamente, Fk=2k.
- Como P1=1 y F1=2, entonces el disco 1 se mueve en
todos los movimientos cuyo número es de la forma m1=1+2p, con
p=0, 1, 2¼ Es decir, en todos los movimientos impares. Como
P2=2 y F2=4, entonces el disco 2 se mueve en todos los
movimientos del tipo m2=2+4p=2+22p con p=0,1,2¼ Como
P3=4 y F3=8, entonces m3=4+8p=22+23p con
p=0,1,2¼ En general, como Pk=2k-1 y Fk=2k,
entonces mk=2k-1+2kp con p=0,1,2¼ Si pensamos el
número mk en binario, veremos que se trata de un número cuyas
primeras k-1 cifras son 0, pero la cifra k-esima es 1. En
efecto, en la descomposición polinómica en base 2 de mk aparece
la potencia 2k-1 y ninguna anterior. De forma que un disco
k se mueve en todos los movimientos tales que, expresados en
binario, terminen en k-1 ceros. Es decir, sea m el número de
un movimiento concreto y sea Bin(m) su expresión en el sistema
de numeración de base 2. Entonces, en el movimiento número m se
mueve el disco k si y sólo si Bin(m) termina en k-1 ceros.
Dicho de otra manera, en el movimiento m se mueve el disco k
si y sólo si el primer dígito de Bin(m) que no es 0 es el dígito
número k (empezando a contar los dígitos desde la derecha).
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.
- 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.
- 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
- Berlekamp, Conway, Guy (1982): Winnings ways for your Mathematical Plays, Academic Press.
- Cilleruelo Mateo, Javier: El sistema binario, Sección "El Diablo de los Números" de La Gaceta de la RSME, Vol. 2, nº 1, enero-abril, 1999, Madrid.
- Gardner, Martin (1975): Carnaval matemático, Alinza Editorial, Madrid, 1992.
- Stewart, Ian: Ingeniosos encuentros entre juegos y matemática, Editorial Gedisa, Barcelona, 2000
- Ruiz, Javier y Peña, Jordi (México DF, 2001), artículo disponible en la dirección: www.geocites.com/jvr_rz/hanoibin.htm
- Valeiras, Rodolfo: artículo sobre la torre de Hanoi disponible en www.rodoval.com/heureka/hanoi/index.html
- Weisstein, Eric W: "Tower of Hanoi". From MathWorld. A Wolfram Web Resource. mathworld.wolfram.com/TowerofHanoi.html
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.