viernes, 24 de diciembre de 2010

SOLUCIÓN AL ACERTIJO 39

Como bien insinué en la anterior entrada, el grafo anterior no tiene solución. Para estar convencidos de ello, tenemos tres opciones:
a) Usar complejas fórmulas de teoría de grafos, algo que ni sé ni voy a hacer en este blog.
b) Usar la fuerza bruta, o sea, probar una por una todas las combinaciones de caminos. Lo difícil es no perderse y, sobre todo, estar convencido de que no nos hemos dejado un camino que pueda ser el bueno.
c) Usar un poco la lógica, que es lo que vamos a hacer.

Fijémonos en el gráfico:
Está formado por 4 puntos (si no contamos el centro). Necesariamente tenemos que empezar por un punto y acabar por otro (que podría ser el punto de inicio). O sea, que COMO MUCHO tenemos dos puntos diferentes de inicio y de final. 
Llamaré PUNTO DE TRANSICIÓN a aquel punto que no se usa ni para empezar ni para terminar. Un punto de transición debe verificar una propiedad clara, y es que el número de caminos que inciden en él ha de ser a la fuerza par. Vamos, que todo lo que en él entra, de él sale (si no saliera, sería un punto de inicio o de final, nunca de transición). Está claro, pues, que los puntos de transición van a asociados a número par de caminos.
Nuestro gráfico tiene 4 puntos. Como dije antes, como mucho dos son de inicio y final, luego debe haber entre dos (como mínimo) y tres puntos de transición. 
Si observamos el grafo, al punto número 1 le llegan 5 caminos (número impar y con rima), luego no puede ser de transición. Lo mismo le ocurre a los puntos 2, 3 y 4. Siempre habrá un camino que nos falte, que será precisamente el que una a los dos puntos que les haya correspondido ser de transición.
Queda así demostrado que el grafo no puede ser completado.
De hecho, si observamos la casita... 
...nos damos cuenta de que las tres esquinas superiores pueden funcionar como puntos de transición (les llegan 2 y 4 caminos), mientras que los dos de abajo son óptimos para ser inicio y final, pues sólo tienen 3 caminos que inciden en ellos. Si alguien prueba a hacer esta casa empezando por algún punto de arriba, se dará cuenta de que es imposible, pues ello obliga a que uno de los puntos de abajo sea de transición, y por supuesto que no pueden serlo por tener un número impar de caminos.

Espero que la explicación haya resultado convincente.
Si alguien se ha enterado del rollo que he soltado, le haré la siguiente pregunta...

¿Es posible hacer el sobre?

Un saludo a todos, y feliz Navidad.

7 comentarios:

María A. dijo...

Si comparamos la primera figura y la última (el sobre) vemos claramente que el "huevo" es un despista-lía bobos...en este caso el número de caminos sigue siendo impar, pero la cifra es 3.

María A. dijo...

No lo he dicho pero es obvio....no se puede hacer.

Asdi dijo...

Valeeee, fallo mío, pasé dos veces por el mismo punto T_T
Yo tenía acertijos de grafos en un libro (Venía uno de unos ladrillos chungo que no veas) y te venía la explicación. Pero no me acordaba.
Como dice la señorita María, no se puede hacer xD
Feliiiiznavidá y esas cosas que se dicen en estas fiestas :) Y que el gordo cocacolero le traiga cosas bonicas ^^

Manuel Amaro dijo...

María... efectivamente, el "huevo" despista. ¡Muy bien tu respuesta! Ya eres una experta en resolver grafos.

Asdi... sí, me imaginé que habías hecho trampa. Felices fiestas!!!

Mery dijo...

Como es el día de los Santos Inocentes, no me meto en berenjenales ¡ea!

FELIZ NAVIDAD

alberto dijo...

Feliz 2011!!!!

Te deseo un año lleno de páginas escritas

Un fuerte abrazo

Mar Cantón dijo...

Mar Cantón dijo...

Manuel, ya van años de amistá bloggera, aunque no siempre esté o escriba eres uno de mis referentes, uno de esos referentes que "siempre están ahí", y en este año en el que emprendí esta nueva aventurita con el blog coincidiendo con la marcha inequívoca de uno de ellos, siento estas cosas más que nunca... Relaciones extrañas y especiales, con su bueno y con su malo, con esa sensación que da lo virtual de no estar solo nunca y ese vacío que provoca cuando alguien te deja solo y no tienes dónde buscarlo... No a través de lo virtual.

"Raro", verdad??? ;))

Feliz año y mil besos, que eso que espero en mi buzón (y todo), te dé mucha felicidad.