domingo, 6 de abril de 2008

Una ciudad con tres islas

Enunciado

Este problema es un problema típico de recorrido, equivalente a recorrer un dibujo sin levantar el lápiz del papel, unir una serie de puntos, y otros pasatiempos.

Lo más difícil para muchos fue entender que un circuito quería decir que el punto de partida y el de llegada era el mismo, mientras que un recorrido significa partir de un lugar y llegar a otro. Con este plano de islas se puede hacer un recorrido, pero no un circuito.

Hay que observar que si nos fijamos en un trozo de tierra aislada (sea la costa, o una cualquiera de las islas), suponiendo que sólo podamos pasar por los puentes y que sólo podamos usar una vez cada puente, cuando el autobús del circuito entre en la zona, gastará un puente, y cuando salga, gastará otro. Eso quiere decir que cada vez que pase por una de las cuatro zonas, gasta dos de los puentes que tiene esa zona. Si un circuito se puede trazar, está clara que todas las zonas deberían tener una cantidad par de puentes que lleguen a ella.

En nuestro caso, las dos islas menores tienen sólo tres puentes que comuniquen con ellas. Por eso, si pasa por una de esas islas el autobús, usará un puente para entrar y otro para salir, con lo que sólo quedará un puente sin usar. Si vuelve a entrar el autobús, estará atrapado dentro de la isla.

¿Podríamos trazar un recorrido? Sí, si sale de una isla y acaba en la isla contraria, como es fácil comprobar. Pero no un circuito, por lo que antes se ha comentado.

Plano con solución

Plano con solución

¿Podríamos poner un puente más que solucionara el problema? Para hacer par a la vez los puentes de las dos islas, habría que añadir o quitar un puente entre ellas. Como no existe ninguno, sólo tenemos la posibilidad de añadirlo. Una vez añadido, hay que comprobar que efectivamente se puede hacer el circuito (ver en el dibujo).

No hay comentarios: