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’