El puente encantado

Enunciado

Este problema también es un problema de recorrido, como el del Una ciudad con tres islas. En este caso hay cinco zonas conectadas por puentes, y si aplicamos el razonamiento basado en la paridad de los recorridos, si hubiese que pasar por todos los puentes, cada zona debería tener un número par de entradas y salidas si es zona de paso, y el principio y el fin, un número impar./p>

En este caso la cosa se complica, ya que pasamos por todos los puentes menos por uno, y además luego hay que investigar de cuántas formas se puede hacer.

Afortunadamente, sabemos desde dónde empezamos (el lado derecho del río) y dónde acabamos (la isla superior). En la isla hay una cantidad impar de puentes (3), así que ninguno de ellos será el encantado. Sin embargo, en el lado derecho del río hay un número par de puentes (4). Uno de ellos es el puente encantado. Si miramos con atención las demás zonas, las otras dos islas tienen un número adecuado de puentes (2 y 4), pero la orilla izquierda del río tiene tres puentes. Eso quiere decir (por ser zona de paso) que también hay que quitar uno. ¿Cuál? Claramente, el que cruza de una orilla a otra. Ése es el puente encantado. Al quitarlo, puede que podamos hacer los recorridos.

numerando puentes

¿Cuántos recorridos? Vayamos por partes. Vamos a poner nombres a las zonas y a los puentes. D, I serán las orillas, y B C y A, las islas de bajo, central y superior. los puentes podemos numerarlos, por ejemplo, como marca el dibujo.

En primer lugar nos encontramos con tres opciones.

Supongamos que usamos el puente hacia la isla inferior en primer lugar (D1B), luego hay que cruzar a la isla central (D1B2C), y podemos hacer tres cosas: pasar a la otra orilla (D1B2C3I), volver a la primera (D1B2C4D), o pasar a la otra isla (D1B2C5A).

Siguiendo la primera de las posibilidades (D1B2C3I) no queda más remedio que pasar a la isla superior (D1B2C3I7A), y de aquí sólo tenemos dos rutas: pasar primero a la isla inferior, en cuyo caso sólo nos queda volver a la otra orilla y retornar a la isla (D1B2C3I7A5C4D6A), ruta 1, o bien cruzar a la isla, en cuyo caso tendremos que volver a la isla central y volver a la superior (D1B2C3I7A6D4C5A), ruta 2.

Siguiendo la segunda posibilidad (D1B2C4D), nos obligamos a pasar a la isla superior (D1B2C4D6A), y de nuevo se plantean dos cosas: pasar a la otra orilla, con lo que tendremos que pasar a la isla central y de ahí a la superior (D1B2C4D6A7I3C5A), ruta 3, o bien pasar a la isla central, de donde iremos a la orilla izquierda y a la isla superior (D1B2C4D6A5C3I7A), ruta 4.

Con la tercera posibilidad (D1B2C5A), pasamos directamente a tener dos opciones: pasamos a la orilla derecha, de donde vamos a la isla central, a la otra orilla y de nuevo a la isla superior (D1B2C5A6D4C3I7A), ruta 5, o bien pasamos a la orilla izquierda, de donde pasamos a la isla central, a la orilla derecha y a la isla superior (D1B2C5A7I3C4D6A), ruta 6.

Ya hemos agotado las posibilidades del primer puente, si pasamos por el puente 4 a la isla central (D4C), podemos hacer tres cosas (a partir de ahora, sólo resumiré las rutas): D4C2B1D6A, de donde obtenemos D4C2B1D6A5C3I7A, ruta 7, y D4C2B1D6A7I3C5A, ruta 8, D4C3I7A, de donde obtenemos D4C3I7A5C2B6A, ruta 9, y D4C3I7A6D1B2C5A, ruta 10, D4C5A, de donde tenemos D4C5A6D1B2C3I7A, ruta 11, y D4C5A7I3C2B1D6A, ruta 12.

Por último, nos queda el último puente válido, el 6, hasta la isla de arriba (D6A), que nos ofrece dos posibilidades: D6A5C, de donde sale D6A5C2B1D4C3I7A, ruta 13, la opción de cruzar a la orilla derecha no es posible, por no pasar por todos los puentes, y D6A5C4D1B3I7A, ruta 14, y D6A7I3C, de donde sale D6A7I3C2B1D4C5A, ruta 15, D6A7I3C4D1B2C5A, ruta 16, y una opción que tampoco vale, porque no pasa por todos los puentes, ya que vuelve a la isla superior por el puente 5.

esquema

En total, 16 rutas diferentes posibles, que son todas las indicadas arriba.

Es posible abordar este problema de una forma más cómoda si vamos construyendo todas esas rutas como un árbol, fijándonos en cada rama en los puentes que hemos cruzado, y en pasar al sitio correcto a través de cada puente.