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?¨C 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.