La torre y el hipercubo

En una torre de Hanói trivial de dos discos, A y B, como vimos la semana pasada, la secuencia de movimientos para efectuar el traslado de un eje a otro es ABA. En la de tres discos, A, B y C, la secuencia es ABACABA. Es decir, primero trasladamos los tres discos superiores como en la torre de tres discos, luego cambiamos de eje el cuarto disco, y por último repetimos el traslado de tres discos para situarlos sobre el cuarto. Y con cuatro discos, A, B, C y D, el proceso es análogo: trasladamos...

En una torre de Hanói trivial de dos discos, A y B, como vimos la semana pasada, la secuencia de movimientos para efectuar el traslado de un eje a otro es ABA. En la de tres discos, A, B y C, la secuencia es ABACABA. Es decir, primero trasladamos los tres discos superiores como en la torre de tres discos, luego cambiamos de eje el cuarto disco, y por último repetimos el traslado de tres discos para situarlos sobre el cuarto. Y con cuatro discos, A, B, C y D, el proceso es análogo: trasladamos los tres primeros a otro eje, cambiamos el cuarto al eje libre y volvemos a repetir la secuencia de los tres primeros para situarlos sobre el cuarto: ABACABADABACABA. Por lo tanto, a medida que aumenta el número de discos, el número de movimientos necesarios aumenta según la secuencia 1, 3, 7, 15, 31, 63… Para n discos, el número de movimientos necesarios es 2ⁿ– 1, lo que explica la coincidencia numérica entre las dos supuestas leyendas indias: la del inventor del ajedrez y la de la torre de 64 discos de oro del templo de Benarés.

Como también vimos, la secuencia de movimientos necesaria para trasladar una torre de tres discos se corresponde con el recorrido hamiltoniano por los vértices de un cubo. Pero la cosa no acaba ahí (no ha hecho más que empezar): la secuencia de movimientos para una torre de cuatro discos se corresponde con el recorrido hamiltoniano por los vértices de un teseracto (hipercubo 4-dimensional). Y así sucesiva e indefinidamente: como demostró el matemático D. W. Crowe a mediados del siglo XX, esta correspondencia se mantiene para torres de cualquier altura y cubos de cualesquiera dimensiones: el número de movimientos y el orden en el que hay que mover n discos de una torre de Hanói para trasladarlos a otro eje, se corresponden exactamente con la secuencia direccional (y dimensional) de un recorrido hamiltoniano en un hipercubo de n dimensiones.

Dos rompecabezas de madera ideados hacia la misma época por sendos grandes matemáticos, el dodecaedro de Hamilton y la torre de Hanói de Lucas, coinciden en un estante de una juguetería. A primera vista parece que no tienen nada que ver el uno con el otro; pero, como en los folletines decimonónicos, acaban descubriendo que son (topológicamente) hermanos.

Grafos caligráficos

Por primera vez en nueve años, la semana pasada, a causa de un problema técnico, la sección de comentarios no estuvo operativa, así que me remontaré a los de hace dos semanas. Bretos Bursó envió, en esquema, su solución al recorrido hamiltoniano por los vértices de un dodecaedro:

Y Salva Fuster hizo una interesante observación sobre la relación entre grafos y letras: “Pensando en los caminos eulerianos y hamiltonianos me he dado cuenta de que ni la E ni la H admiten caminos de un tipo ni del otro. Supongo que el grafo más sencillo que no los admite coincide con la letra Y. Por cierto, las letras del alfabeto podrían ser clasificadas en diferentes tipos de grafos. ¿Cuántos tipos hay?”.

Animo a mis sagaces lectoras/es a examinar las letras (mayúsculas) del alfabeto consideradas como grafos. Se prescinde de la Ñ por razones obvias (no puede considerarse un grafo debido a la virgulilla) y se recomienda centrarse en un tipo de letra de trazo simple (palo seco o sin gracias, como dicen los tipógrafos), como este:

Puedes seguir a MATERIA en Facebook, X e Instagram, o apuntarte aquí para recibir nuestra newsletter semanal.