Y la solución es... no se puede

La solución al problema planteado el pasado viernes (ver vídeo a la izquierda de esta página) por el profesor Adolfo Quirós, de la Real Sociedad Matemática Española y de la Universidad Autónoma de Madrid es... que no hay solución. Muchos lectores han enviado erróneamente una secuencia de números con un posible camino, pero la mayoría de ellos no tenía en cuenta que había que regresar al punto de partida. Otros, tal vez tras múltiples intentos, han llegado a la conclusión correcta de que no hay una ruta que cumpla las condiciones. Pero eso no bastaba: tal y como pedía el profesor había que demostrarlo.

Algunos lectores con amplios conocimientos matemáticos han dado una respuesta académica impecable al problema: no tiene solución porque es un gráfico bipartito con un número impar de vértices y por tanto no admite un circuito hamiltoniano (el que recorre todos los puntos sin pasar dos veces por el mismo y vuelve al punto de partida).

Sin embargo, en el espíritu de estos desafíos está que en ellos puedan participar personas con conocimientos básicos de matemáticas. Y, sí también se puede demostrar la solución sin haber oído nunca hablar de la teoría de grafos ni los circuitos hamiltonianos. Una posible demostración, la que nos propone el profesor Quirós (ver vídeo de la derecha) se basa en la técnica llamada coloración de grafos. Y pese a este nombre solemne, la puede entender hasta un niño.

Primero, nos damos cuenta de que las ciudades pueden pintarse con dos colores, por ejemplo, rojo y azul, de forma que los vértices rojos sólo se comuniquen directamente con los azules y los azules con los rojos (que no haya ningún camino entre puntos del mismo color, vamos). Nos quedarán así seis ciudades azules y cinco rojas. Pues bien, si empezamos por una ciudad azul nuestro última etapa será también de ese color... pero entonces no habrá comunicación con el punto de partida (no están enlazados los puntos del mismo color). Pero si empezamos con una ciudad roja (sólo hay cinco) será peor: quedaremos atascados mucho antes de completar el circuito.

Se han recibido bastantes respuestas con este mismo razonamiento y distintas maneras de presentarlo (colores, letras...), que se apoyan como el profesor en la idea de dividir las ciudades en dos grupos.

Pero hay más demostraciones posibles. Entre las respuestas correctas que utilizan otro tipo de argumentos, queremos destacar las que razonan esencialmente así: a cada ciudad llegamos por una carretera y salimos por otra, por tanto hay que usar dos y sólo dos carreteras por ciudad; podemos por tanto borrar dos carreteras (sin especificar cuáles) de las que llegan a cada una de las ciudades 3, 8 y 11 (donde confluyen cuatro), y una de las que llegan a 2 y 4 (ahí llegan tres). Borramos así ocho carreteras en total (como estas ciudades no tienen carreteras en común no hay riego de haber contado una dos veces). Pero esto nos dejaría con sólo diez carreteras, y eso hace imposible completar el circuito de 11 carreteras necesarias para unir los 11 puntos. Ésta, igual que la del profesor Quirós, es una solución sencilla y elegante, es decir, matemática.

En cuanto a las soluciones erróneas, además de las que proponían una secuencia númerica (como hemos dicho, no había camino posible), algunos lectores han confundido el problema planteado, que busca "circuitos hamiltonianos", con el más famoso de los Puentes de Königsberg. Pero hay una diferencia: en este último se buscaba un camino que pasara por todos los puntos recorriendo todas y cada una de las carreteras sólo una vez; en el del profesor Quirós no hacía falta recorrerlas todas.

En el caso de los Puentes de Königsberg Leonhard Euler dio, en 1735, un criterio sencillo que caracteriza exactamente qué grafos admiten un "camino euleriano": sólo pueden resolverse si coinciden en dos o menos vértices un número impar de líneas. Por el contrario, no se conoce un criterio general que permita decidir fácilmente si un grafo cualquiera tiene o no un circuito hamiltoniano como el que pedimos en el problema, aunque sí se conocen condiciones que nos dicen que cierta clases de grafos admiten, o no, un circuito hamiltoniano.

Hasta las 0.00 de hoy (plazo límite marcado para recibir respuestas) habían llegado a nuestro buzón de correo más de 3.700 soluciones. Realizado un sorteo entre las correctas (al menos una cuarta parte del total), la ganadora ha resultado ser Ángela Barbero de Valladolid, que recibirá una biblioteca matemática completa como la que cada domingo sale a la venta con EL PAÍS. Hoy plantearemos un nuevo desafío.

Primer desafío matemático de el PAÍS: la solución es... no hay solución

Un problema de ciudades y carreteras