Skip to content

Solución: recolocando vagones

by en 07/04/2013

Hola!

Un domingo más llega el momento de desvelar la solución de nuestro acertijo de la semana. En esta ocasión ¡sólo un lector se animó a dar su respuesta! Y además, ¡tenemos que felicitarle, porque acertó! De modo que, desde aquí, mandamos nuestra enhorabuena a Joti. Veamos cómo se resolvía.

Os contábamos la curiosa forma de una determinada estación de tren en la que los trenes, por las necesidades físicas de la alta montaña, debían entrar en una vía muerta y volver a salir de ella para continuar su camino:

Estación de tren alpina

La peculiaridad de esta estación consiste en que al entrar el tren en la vía muerta (en vertical en la figura) el que originalmente era el primer vagón pasa a ser el último al salir. Es lo mismo que ocurre, por ejemplo, en una pila de platos: el primer plato que colocamos sobre la mesa es el último que queda cuando los vamos retirando, uno por uno.

Como vemos, la peculiaridad de las pilas es que lo primero que entra es lo último que sale. ¡Eso es justo lo que pasa con nuestros vagones! Si en la vía muerta entra el vagón 1, luego el 2 y luego el 3, el primero en salir para continuar su camino será el 3, luego el 2 y, finalmente el 1, habiéndose, efectivamente, dado la vuelta respecto al original.

Os lanzábamos la pregunta de si ante un tren con los vagones originalmente ordenados (1, 2, 3, 4, 5, 6, 7, 8, 9 y 10) situados en la estación era posible conseguir que salieran en el orden 1, 2, 3, 4, 5, 10, 9, 8, 7, 6, sabiendo que los encargados de la estación pueden enganchar y desenganchar los vagones a voluntad, aunque sólo los pueden mover de la estación hacia la vía muerta, y de ésta a la vía de salida (izquierda en la imagen).

Como nos adelantó Joti hace unos días, la respuesta es sí. Para eso, tenemos que separar el primer vagón del resto, llevarlo a la vía muerta, y sacarlo de allí sin meter ningún otro vagón. De esa forma conseguimos que el primer vagón esté ya colocado en la salida. Hacemos lo mismo con los 4 vagones siguientes, y tendremos así los 5 vagones en la vía de salida, listos y ordenados.

En la estación quedan los vagones 6, 7, 8, 9 y 10. Lo que hacemos a continuación es llevarlos, en bloque, a la vía muerta, sin separarlos. Eso dejará al vagón 6 el último (abajo del todo en la figura) y al 10 el primero (arriba). Hecho esto, sacamos los 5 vagones, que saldrán en el orden invertido respecto al original, es decir justo como los necesitamos: 10, 9, 8, 7 y 6.

Esta configuración final era fácil: en el propio acertijo os dijimos que tanto 1, 2, 3, 4, 5 como 5, 4, 3, 2, 1 se podían conseguir.

Vamos con el segundo. Os preguntábamos si se podía conseguir la configuración del tren a la salida 5, 7, 10, 9, 8, 6, 4, 3, 1, 2. ¡Esta es más difícil! La forma más sencilla de proceder es intentar sacar, en cada paso, un vagón más en el orden solicitado. En este caso el primero que queremos conseguir sacar el 5. La única forma de lograrlo es quitar de en medio los vagones que tiene por delante, y para eso sólo tenemos una opción: meter en la vía muerta los vagones 1, 2, 3 y 4. Luego metemos el 5 y lo sacamos inmediatamente, consiguiendo tener por fin el primer vagón colocado. El proceso queda así:

Vía de salida Vía muerta (de abajo a arriba) Vía de la estación
5 1, 2, 3, 4 6, 7, 8, 9, 10

El siguiente vagón que tenemos que conseguir sacar es el 7. Ese vagón aún está en la vía de entrada, junto a la estación. Para conseguir tenerlo fuera, necesitamos llevar a la vía muerta el 6, y luego meter y sacar el 7:

Vía de salida Vía muerta (de abajo a arriba) Vía de la estación
5 1, 2, 3, 4 6, 7, 8, 9, 10
5, 7 1, 2, 3, 4, 6 8, 9, 10

Toca el 10. De nuevo, nos vemos obligados a meter los vagones anteriores a él en la vía muerta:

Vía de salida Vía muerta (de abajo a arriba) Vía de la estación
5 1, 2, 3, 4 6, 7, 8, 9, 10
5, 7 1, 2, 3, 4, 6 8, 9, 10
5, 7, 10 1, 2, 3, 4, 6, 8, 9

Ahora la única posibilidad que nos falta es sacar los vagones de la vía muerta, en el orden inverso al que fueron añadidos, es decir de arriba a abajo, 9, 8, 6, 4, 3, 2, 1. Como nos dijo Joti, podremos hacerlo salvo por los dos últimos, el 1 y el 2, que nos piden en el orden inverso al que están. Por tanto, la configuración 5, 7, 10, 9, 8, 6, 4, 3, 1, 2 no es posible.

La última pregunta era 5, 6, 4, 8, 7, 3, 2, 9, 1, 10. El proceso para conseguir este resultado podemos simularlo como antes:

Vía de salida Vía muerta (de abajo a arriba) Vía de la estación
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
5 1, 2, 3, 4 6, 7, 8, 9, 10
5, 6 1, 2, 3, 4 7, 8, 9, 10
5, 6, 4 1, 2, 3 7, 8, 9, 10
5, 6, 4, 8 1, 2, 3, 7 9, 10
5, 6, 4, 8, 7 1, 2, 3 9, 10
5, 6, 4, 8, 7, 3 1, 2 9, 10
5, 6, 4, 8, 7, 3, 2 1 9, 10
5, 6, 4, 8, 7, 3, 2, 9 1 10
5, 6, 4, 8, 7, 3, 2, 9, 1 10
5, 6, 4, 8, 7, 3, 2, 9, 1, 10

Como acertó Joti, también esta configuración final es posible.

Para programar este acertijo, como muchos podréis adivinar lo más cómodo es hacer uso de una estructura de datos tipo pila. Si programas en C++ quizá quieras darte una vuelta por aquí, y si lo haces en Java por acá para ahorrarte algo de trabajo. Y, una vez que tengas tu solución, puedes probarla aquí.

¡Hasta mañana!

Anuncios

From → Soluciones

Dejar un comentario

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: