domingo, 26 de abril de 2009

El tesoro del templo (I)

Enunciado

En todos los problemas en los que se trata de recorrer un laberinto sin pasar dos veces por el mismo sitio, hay un principio que resulta a la vez muy útil y muy sencillo de entender. Todos los cruces que recorramos deben tener un número par de caminos que lleguen a él, excepto (a lo sumo) el lugar por el que entramos y el lugar por el que salimos. El motivo es que cada vez que llegamos a un cruce y volvemos a irnos de él usamos dos caminos, así que, al final, el número total será par, excepto que no hayamos llegado desde ningún sitio (entrada) o bien, nos quedemos allí (salida).

En el laberinto que nos ocupa, el lugar de entrada y el de salida están claros (tienen un único camino), pero hay varios puntos más a los que llega un número impar de caminos, que evidentemente serán los que deberemos dejar sin recorrer, ya que no podremos pasar por alguno de ellos.

Uno de los concursantes me preguntó si era necesario salir del laberinto, ya que había descubierto un camino que mejoraba la cantidad de tesoros, a costa de quedarse dentro del templo. Evidentemente, ningún arqueólogo de película de aventuras elegiría esa opción ¿no?

Vamos al grano. El cruce entre C, D y E, el cruce entre E, G e I, el que hay entre F, G y H y el que hay entre J, H y la Salida tienen 3 caminos, así que tendremos que reducir el número de caminos que llegan a ellos. El sistema evidente es eliminar el camino E y el camino H, pero tiene nada menos que un valor 4 + 3, así que debemos probar si hay un sistema que solucione la paridad con menos coste. También podemos recurrir a quitar D, F, I y J, que proporcionan un total de 1 + 2 + 2 + 2 = 7. Por tanto, ambas soluciones son exactamente igual de costosas. Como el valor total de los tesoros es de 42, los caminos ganadores obtendrán 35.

Si quitamos esos caminos, hay varias opciones para recorrer el laberinto restante. El primer laberinto puede recorrerse con una de las soluciones que han dado en los comentarios, A-B-C-D-F-G-I-J (que aporta un total de 35 puntos, como era de prever). Los cambios se pueden dar en la primera parte, así podemos recorrer por la ruta CDBA, o BACD y aún quedan más variantes.

La segunda familia de soluciones, que ha descubierto Jaume Usó, sería B-A-C-E-G-H, con la variante ABCEGH, que también proporcionan 35 puntos.

La opción "suicida" de quedarse en el interior con 39 puntos es olvidar la salida, y acabar en la intersección EIG con todos los pasillos derrumbados, siguiendo la ruta ABCEGHJI. Al fin y al cabo, en todas las películas siempre hay alguien que al final viene a salvar al héroe ¿no?

1 comentario:

Anónimo dijo...

En la línea 6 de la solución hay una falta de ortografía, estaría bien si se pudiese corregir.

No es halla, sino haya (se trata del verbo haber y no hallar)

Muchas gracias