El dodecaedro maldito

EL PA?S y Materia proponen a sus lectores, cada semana, un juego de l¨®gica. Los lectores pueden enviar sus soluciones en los comentarios, y plantear nuevos acertijos y juegos. La respuesta correcta ser¨¢ ofrecida en la columna de la semana siguiente.

A partir de las consideraciones de Euler relativas al problema de los puentes de K?nigsberg, es f¨¢cil ver que para dibujar un sobre abierto sin levantar el l¨¢piz del papel y sin pasar dos veces por un mismo trazo, hay que partir de uno de los dos v¨¦rtices inferiores y terminar en el otro, pues en ambos confluyen un n¨²mero impar de aristas (3). Como en los dem¨¢s v¨¦rtices el n¨²mero de aristas es par (2 en el v¨¦rtice superior y 4 en los dem¨¢s), el recorrido es posible, e incluso hay varias soluciones distintas (?cu¨¢ntas?).

En el acertijo de Lewis Carroll, a todos los v¨¦rtices les corresponde un n¨²mero par de aristas, por lo que el recorrido tiene que empezar y terminar en el mismo punto. Tambi¨¦n en este caso hay varias soluciones distintas (aunque no tantas como parece, pues las soluciones sim¨¦tricas son equivalentes).

Por ejemplo, si partimos del punto de intersecci¨®n inferior, un posible recorrido ser¨ªa: 1 abajo, 2 dcha, 3 arriba, 4 izda, 5 abajo, 6 izda, 7 arriba, 8 dcha, 9 arriba, 10 dcha, 11 arriba, 12 izda, 13 abajo, 14 izda, 15 abajo, 16 izda, 17 arriba, 18 dcha, 19 arriba, 20 izda, 21 abajo, 22 dcha, 23 abajo, 24 dcha (en todos los casos, el trazo es lo m¨¢s breve posible, es decir, cambia de direcci¨®n al encontrar el primer nodo).

Estos acertijos nos llevan directamente al fascinante tema de los caminos y los ciclos hamiltonianos. Un camino hamiltoniano es un recorrido que, siguiendo las aristas de un grafo, pasa una sola vez por todos sus v¨¦rtices. Si el recorrido termina en un v¨¦rtice adyacente al de partida, el camino es un ciclo hamiltoniano (pues se podr¨ªa cerrar el circuito recorriendo la arista que une los v¨¦rtices inicial y final).

Los caminos hamiltonianos se llaman as¨ª en honor del gran matem¨¢tico irland¨¦s William Hamilton (el padre de los cuaterniones), que estudi¨® este tipo de recorridos en los s¨®lidos plat¨®nicos.

En 1857, Hamilton permiti¨® que se comercializara un rompecabezas basado en los caminos hamiltonianos, consistente en hallar un recorrido por las aristas de un dodecaedro que pasara una sola vez por todos sus v¨¦rtices. Parece ser que las 25 libras que le pagaron en aquella ocasi¨®n fue todo el dinero que Hamilton percibi¨® en su vida por sus hallazgos matem¨¢ticos.

La figura es un grafo topol¨®gicamente equivalente a un dodecaedro, en el que puedes intentar hallar un camino hamiltoniano. O mejor, un ciclo.

Carlo Frabetti

Escritor y matem¨¢tico, miembro de la Academia de Ciencias de Nueva York, ha publicado m¨¢s de 50 obras de divulgaci¨®n cient¨ªfica para adultos, ni?os y j¨®venes, entre ellos ¡®Maldita f¨ªsica¡¯, ¡®Malditas matem¨¢ticas¡¯ o ¡®El gran juego¡¯. Fue guionista de ¡®La bola de cristal¡¯