miércoles, 23 de marzo de 2011

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.

8 comentarios:

  1. creo que haciéndolo un poco más general queda casi más fácil. Yo lo hubiera hecho así:
    Lema.- todo grafo hamiltoniano 2-coloreable tiene un número par de vértices.

    En ese grafo todas las caras tienen longitud par, luego es sabido que es 2-coloreable.

    Ergo...

    ResponderEliminar
  2. Quizás es algo más técnico. En cualqueir caso, muchas gracias por tu experta aportación, Alberto.

    ResponderEliminar
  3. ¿Lo de las cuatro aristas del principio es correcto? (lo de "excepto el número 5..."). Aunque lo cierto que tampoco influye en la solución.

    Yo les mandé la otra solución que publican (la de contar ramas del grafo que no están en el ciclo) y tampoco me ha tocado. Estoy muy triste.

    ResponderEliminar
  4. Cierto, krospell. Y como bien dices, no afecta para nada. El caso es elegir un inicio... y ese me pareció buena idea. en cualquier caso, ya lo he corregido.
    (Espero que no hayan eliminado mi solución por esa chorradita)

    ResponderEliminar
  5. Vaya Tito, envié una solución prácticamente igual que la tuya. De hecho hice el mismo razonamiento que tú para poder suponer que partimos del 1-8 y lo dividí después en los mismos 3 casos posibles. Me quedaron estos casos algo más cortos, pero vamos, la idea general es la misma.

    La verdad es que mi primer planteamiento fue de otro tipo, pero no me salió. Ahora veo que una de las soluciones que ponen (justo la siguiente a la del vídeo) era como pensé, pero no me salió.

    ResponderEliminar
  6. Tito, no es por hacerte la pelota, pero tu solución me parece mas elegante que la que dan en el propio periódico. Quizás se echa de menos una explicación de por que coges ese tramo de inicio: al ser simétrico da igual y como sólo tiene 3 tienes que coger al menos 1 simétrico. Además, no creo que tu solución la hayan quitado por esa chorradita: seguro que primero escogen al posible ganador y después ven si es correcta la solución. Así corrigen mucho menos. Por cierto, que mi hijo estuvo e lsábado pasado en la olimpidad de 2º de ESO. Un abrazo.

    ResponderEliminar
  7. @antoniopala:
    Primero elijo un vértice por el que solo pasen 3 aristas y que esté en el eje de simetría.

    Así si el camino pasa por 1, habrá 2 aristas que lleguen a él. así que al menos 1 de ellas será la 1-8 o la 1-5. Como el grafo es simétrico (respecto de la horizontal), para seguir argumentando, da igual elegir una opción u otra, pues saldrá igual.

    Si quiers, piensa en que si cojo la 1-5 y pongo un espejo en el eje de simetría horizontal, lo que haga por la 1-8 se "refleja" en lo que haga en la 1-5.

    Tras mandar esta solución, encontré una algo más corta, pero no demasiado.

    ¿Estuviste en Sevilla con tu hijo en la Olimpiada? Yo estuve con los de primaria, fijo que hasta nos cruzamnos.

    ResponderEliminar

Si no comentas, Gauss se comerá una integral.
Y, por favor, respeta a todos con tus opiniones.