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.