Un Problema sobre Ciudades y Carreteras: propuesta de solución

Como muchos de vosotros ya sabréis, desde la RSEM y El País, y con motivo del centenario de la primera, se ha abierto un concurso de resolución de problemas de matemáticas. El primero de ellos consiste en Un Problemas de Ciudades y Carreteras, propuesto por el Profesor Adolfo Quirós de la Universidad Autónoma de Madrid

El problema en cuestión era el siguiente (click en la imagen para ir al video):





Pues bien, ya se ha cerrado el plazo y el mismo proponente ha dado la solución al problema: No hay solución posible. A continuación, os dejo el vídeo en el que Adolfo da su solución, para mi gusto, muy simple y elegante, basada en el hecho de que el grafo en cuestión se puede colorear con sólo 2 colores (click en la imagen para ir al video):





Bueno, si leéis la noticia en la que se da la solución, veréis que no he sido el agraciado ganador. En cualqueir caso, os dejo a continuación la solución que envié. Básicamente, lo que hice fue ponerme a tratar de construir tal camino, partiendo de una situación inicial, e ir descartando posibilidades. Al estilo de un sudoku, vamos.

Por Reducción al Absurdo, vamos a suponer que ese ciclo SÍ que existe.

Como se nos pide un ciclo (es decir, un camino cerrado) y que pase por todos los vértices, es indiferente el vértice por el que empecemos a trabajar, ya que a todos y cada uno de los vértices llegarán dos y sólo dos aristas.
Así pues, vamos a comenzar a trabajar por un vértice cualquiera: el número 1. ¿Por qué éste? pues porque, además de estar en el eje horizontal de simetría del grafo, a él sólo llegan 3 aristas (al resto, excepto el número 5, llegan 4).

Como ya hemos dicho, al vértice 1, llegan exactamente tres aristas. Por lo tanto, nuestro ciclo debrerá contener dos de esas tres aristas y, en particular, en nuestro ciclo estará bien la arista 1-8, bien la arista 1-11 (o las dos a la vez). En cualquier caso, por la simetría (respecto del eje que marcan lso vértices 1-2-3-4-5) del grafo, da igual una arista u otra. Así que vamos a suponer que es la 1-8 la que está en nuestro "presunto" ciclo.

Ahora que sabemos que llegamos al vértice 8, tendremos tres opciones diferentes.

OPCIÓN 1: 1-8-6, es decir, de 8 nos vamos a 6.
Como nuestro ciclo ya ha pasado por 8 (ya le han llegado 2 aristas), las aristas 8-7 y 8-5 no puede estar ya en el ciclo (quedan inutilizada).
El vértice 7 se queda con sólo dos aristas útiles, que forzosamente deberán estar en nuestro ciclo: 3-7-4.
El vértice 5 se queda con sólo dos aristas útiles, que forzosamente deberán estar en nuestro ciclo: 4-5-11.
Uniendo estas dos últimas observaciones, nuestro ciclo tendrá que seguir este camino: 3-7-4-5-11.
Ahora bien, en estas condiciones, nuestro ciclo habrá pasado ya por el vértice 4 (le han llegado 2 aristas), lo que inutiliza la arista 4-10.
El vértice 10 se queda con sólo dos aristas útiles, que forzosamente deberán estar en nuestro ciclo: 11-10-3.
Pero entonces nuestro ciclo se cierra, sin pasar por todos los vértices: 3-7-4-5-11-10-3. Por lo tanto llegamos a que la OPCIÓN 1 es imposible.


OPCIÓN 2: 1-8-7, es decir, de 8 nos vamos a 7.
Como nuestro ciclo ha pasdo por 8, eso inutiliza las aristas 8-6 y 8-5.
El vértice 5 se queda con dos aristas útiles, que forzosamente deberán estar en nuestro ciclo: 4-5-11.
El vértice 6 se queda con dos aristas útiles, que forzosamente deberán estar en nuestro ciclo: 2-6-3.
Al vértice 9 llegan tres aristas, luego el ciclo hamiltoniano debe pasar por dos de ellas. Si se utilizaran 2-9 y 9-3, junto con 2-6-3 (que ya sabemos que debe estar en el ciclo), cerraría el ciclo sin pasar por todos los vértices (2-6-3-9-2). Por lo tanto, la tercera arista que pasa por 9 tiene que estar presente en nuestro ciclo: 11-9.
Como ya teníamos 4-5-11 y ahora 11-9, tenemos seguro que el ciclo pasa por 4-5-11-9 y nuestro ciclo ya ha pasado por 11, por lo que la arista 11-10 queda inutilizada.
El vértice 10 se queda con sólo dos aristas útiles, que forzosamente deberán estar en nuestro ciclo: 3-10-4.
Uniendo lo que tenemos hasta ahora, llegamos a que nuestro ciclo debe contener a 1-8-7 por un lado, y a 2-6-3-10-4-5-11-9
Pero entonces, acabamos de dejar al vértice 7 sin salida posible (hemos llegado a él por 8, pero no podremos salir de él (las arista 3-7 queda inutilizada porque el ciclo ya ha pasado por 3 y, análogamente, la arista 4-7 queda inutilizada porque el ciclo ha pasado por 4).
Por lo tanto la OPCIÓN 2 también es imposible.


OPCIÓN 3: 1-8-5, es decir, de 8 nos vamos a 5.
Como nuestro ciclo ha pasado por 8, eso inutiliza las aristas 8-6 y 8-7.
El vértice 6 se queda con dos aristas útiles, que forzosamente deberán estar en nuestro ciclo: 2-6-3.
El vértice 7 se queda con dos aristas útiles, que forzosamente deberán estar en nuestro ciclo: 3-7-4.
Uniendo estas dos partes, tenemos 2-6-3-7-4. Por lo tanto, el ciclo habrá pasado por el vértice 3, lo que inutiliza las aristas 3-9 y 3-10.
El vértice 9 se queda con dos aristas útiles, que forzosamente deberán estar en nuetro ciclo: 2-9-11.
El vértice 10 se queda con dos aristas útiles, que forzosamente deberán estar en nuestro ciclo: 4-10-11.
Uniendo ésto último con lo anterior, trendríamos un ciclo cerrado 2-6-3-7-4-10-11-9-2, que no pasaría por todos los vértices.
Por lo tanto, la OPCIÓN 3 también es imposible.


En conclusión, NO puede exisitr un ciclo hamiltoniano en este grafo.

Creo que no es una solución complicada de entender. tampoco hacen falta grandes conocimientos de matemáticas. Sólo hace falta un poco de organización, lógica y tener las cosas claras.

ACTUALIZACIÓN: Como no parecían verse los vídeos (problemas con el incrustamiento desde El País), he decidido incluir imágenes que la hacer click en ellas, pasas a ver el vídeo directaemnte en su enlace original.

Tito Eliatron Dixit

PD: Esta entrada forma parte de la Edición 2.2 del Carnaval de Matemáticas cuyo anfitrión, en este mes, es Gaussianos.