La torre de Hanoi (II)

EL JUEGO DE LA CIENCIA // CARLO FRABETTI

*Escritor y matemático

Dada una torre de Hanoi trivial, de un solo disco, es evidente que basta un movimiento para trasladar ese disco a otro eje. Una torre de dos discos también es trivial: trasladamos el menor a uno de los dos ejes libres, el mayor al otro eje libre, y por último ponemos el menor sobre el mayor. Consideremos ahora una torre de tres discos, a los que llamaremos, de menor a mayor, A, B y C. Para el primer movimiento solo hay una opción: trasladar el disco A a uno de los dos ejes libres. Para el segundo movimiento solo hay una opción no repetitiva: pasar el disco B al eje libre. Los siguientes movimientos no son únicos, pero sí bastante obvios: 3) A sobre B, 4) C al eje libre, 5) A al eje libre, 6) B sobre C, 7) A sobre B. La secuencia es, pues, ABACABA.

Hamilton estudió en los sólidos platónicos los recorridos que llevan su nombre, que consisten en pasar una y solo una vez por todos los vértices. En el caso de un cubo, si llamamos A a la dirección vertical, B a la horizontal y C a la anteroposterior, partiendo, por ejemplo, del vértice superior izquierdo del cubo y yendo primero hacia abajo, luego hacia la derecha, luego hacia arriba, luego hacia atrás y así hasta completar el sencillo recorrido hamiltoniano, veremos que la secuencia direccional (y dimensional) es ABACABA, ¡la misma que en una torre de Hanoi de tres discos! Pero esto no es más que el principio. A mediados del siglo pasado, el matemático D. W. Crowe demostró que este sorprendente isomorfismo se mantiene para torres de cualquier altura y cubos de cualesquiera dimensiones: el orden en el que hay que mover n discos de una torre de Hanoi para trasladarlos a otro eje, se corresponde exactamente con la secuencia direccional (y dimensional) de un recorrido hamiltoniano en un cubo de n dimensiones.

Como es bien sabido, el mítico inventor del ajedrez le pidió al rey de la India un grano de trigo por la primera casilla del tablero, dos por la segunda, cuatro por la tercera, ocho por la cuarta, y así sucesivamente hasta la casilla 64, doblando en cada una el número de granos de trigo de la anterior. Pues bien, este número (18.446.744.073.709.551.615) es igual al número de traslados necesarios para pasar de un eje a otro los 64 discos de oro de la torre de Brahma (ver columna anterior), y al número de aristas que hay que recorrer en un hipercubo de 64 dimensiones para efectuar un recorrido hamiltoniano (dejo a mis sagaces lectores la comprobación de la sorprendente equivalencia entre ambas leyendas indias).