Skip to content

Solución: hormigas itinerantes

by en 23/02/2014

¡Hola!

Una semana más llega el momento de desvelar el acertijo. En esta ocasión, os hablábamos de nuestro hermano que a veces, para entretenerse, se dedica a colocar hormigas sobre un alambre en horizontal y se queda esperando a ver cuánto tardan en caer todas. Las hormigas se desplazan a velocidad constante (un centímetro por segundo) en alguno de los dos sentidos del alambre, cayendo irremediablemente al llegar a uno de los extremos. Además, cuando se encuentran dos de frente, ambas se dan la vuelta y empiezan a desplazarse en el sentido contrario al orginal.

Con estas condiciones, os retábamos a decirnos el tiempo mínimo y máximo que tardarán un grupo de hormigas en caerse, conocidas la longitud del alambre y las posiciones iniciales de las hormigas, pero no el sentido inicial de la marcha de cada una. En concreto, os hacíamos dos preguntas:

  • Un alambre de 20 centímetros con hormigas situadas en las posiciones 3, 11, 12 y 13.
  • Un alambre de 35 centímetros con hormigas situadas en las posiciones 6, 10, 11, 14, 18, 20, 22 y 27

En esta ocasión recibimos tres respuestas… ¡distintas! ¿Quién habrá acertado? 🙂

Curiosamente, Joti, el protagonista (parcialmente ficticio) de la historia de la semana, ¡no acertó! 😦 Las respuestas correctas son 9 y 17 segundos para la primera pregunta (aquí coincidieron todos), y… emoción, intriga, dolor de barriga… 17 y 29 para la segunda. ¡Enhorabuena, Gualterio, por tu acierto! Y, naturalmente, muchas gracias a Joti y David por intentarlo. ¡Habéis tenido una racha de aciertos legendaria, alguna vez había que equivocarse! 🙂

Pero, ¿por qué son esas las respuestas correctas? Vamos a verlo…

Seguramente muchos habréis llegado a la conclusión de que sacar el tiempo mínimo para que todas las hormigas caigan es bastante sencillo. Basta con asumir que todas las hormigas buscan la forma más rápida de caer del alambre, y para eso se dirigen hacia el extremo más cercano, como si estuvieran escapando de un incendio. Así, las hormigas que estén en la primera mitad del alambre se dirigirán hacia la izquierda, y las de la segunda mitad hacia la derecha. El tiempo mínimo para que todas caigan será el tiempo que tarde en caer la última, que será aquella que empiece más alejada de un extremo. Por tanto, para saber el tiempo mínimo basta con averiguar la distancia más larga al extremo más cercano de cada hormiga. La parte importante es que como todas “huyen del centro” a la misma velocidad, no se encontrarán entre ellas y no habrá ningún cambio de sentido de la marcha.

En la primera pregunta, con un alambre de 20 centímetros, tendremos:

Hormiga 1 2 3 4
Posición inicial 3 11 12 13
Extremo más cercano
Distancia 3 9 8 7

por lo que, como nos dijeron nuestros tres lectores, las hormigas tardarán como mínimo 9 segundos en caer.

Para el alambre de 35 centímetros:

Hormiga 1 2 3 4 5 6 7 8
Posición inicial 6 10 11 14 18 20 22 27
Extremo más cercano
Distancia 6 10 11 14 17 15 13 8

que también coincide con las respuestas que nos disteis en los comentarios.

La parte difícil del acertijo es averiguar el tiempo máximo que estarán sobre el alambre, porque en este caso lo que querremos, intuitivamente, es maximizar el número de encuentros entre las hormigas, para mantenerlas sobre el alambre en lugar de acercándose hacia los extremos.

Una forma de averiguar el máximo es probar con todas las posibles configuraciones iniciales de las hormigas y simular su comportamiento. Por ejemplo, podemos suponer que al principio todas las hormigas se desplazan hacia la izquierda y ver cuánto tardarán en caer. Luego suponer que la primera se desplaza hacia la derecha y todas las demás hacia la izquierda, y repetir el proceso. Pero si esta solución fuera la que esperamos, ¡el acertijo sería muy difícil! Hacerlo a mano requeriría un trabajo bastante tedioso y propenso a errores, como comentó David. Y hacerlo en un ordenador nos exigiría implementar un programa poco trivial.

De modo que, como supondréis, hay una solución mucho más simple, que requiere pensar un poco… y hacerlo además durante un momento de inspiración 🙂 Para explicarla vamos a empezar con el caso más sencillo posible: el de una única hormiga sobre el alambre. Por poner valores, supongamos que nuestro alambre tiene 10 centímetros y la (única) hormiga está en el 3. En este caso es fácil responder a las preguntas: la hormiga tardará como mínimo 3 segundos en caer (lo que tarda en llegar al extremo más cercano), y como máximo 7 (lo que tarda en llegar al más lejano).

¡Hasta aquí ha sido fácil! El asunto se pone más divertido cuando hay dos hormigas. Añadamos la segunda, por ejemplo en el centímetro 6. Sabemos que ambas tardarán como mínimo 4 segundos en caer (lo que tarde en llegar la segunda hormiga al extremo de la derecha). La parte difícil es averiguar el tiempo máximo. Parece claro que, como en el caso de una hormiga, si el tiempo mínimo se consigue suponiendo que las hormigas se desplazan al extremo más cercano, para conseguir el tiempo máximo querremos que vayan en dirección contraria, es decir hacia el extremo más alejado. Por tanto, tendremos:

tiempo=0
1 2 3 4 5 6 7 8 9 10
tiempo=1
1 2 3 4 5 6 7 8 9 10

En este momento, las dos hormigas se encuentran y cambian el sentido de la marcha:

tiempo=2
1 2 3 4 5 6 7 8 9 10
tiempo=3
1 2 3 4 5 6 7 8 9 10

Es fácil darse cuenta de que la hormiga de la izquierda caerá 3 segundos después (instante 6), y la de la derecha un segundo después de eso.

En el esquema hemos utilizado los colores para diferenciar a cada una de las dos hormigas de manera que queda patente que la hormiga del lado izquierdo, que empezó en el centímetro 3, es la que, al encontrarse con la segunda, da la vuelta y terminará cayendo por el extremo izquierdo. Sin embargo, y aquí es donde llega la idea curiosa que facilita la resolución del acertijo, si en lugar de simular que cada una de ellas se da la vuelta suponemos que, sencillamente, continúan su camino, la situación queda:

tiempo=0
1 2 3 4 5 6 7 8 9 10
tiempo=1
1 2 3 4 5 6 7 8 9 10
tiempo=2
1 2 3 4 5 6 7 8 9 10
tiempo=3
1 2 3 4 5 6 7 8 9 10

Aparte de los colores, ¡no hay ninguna diferencia! Al suponer que las hormigas continuan su camino el resultado es exactamente el mismo con respecto al tiempo máximo para que todas caigan. Obviamente, pensando en cada hormiga de manera individual el resultado será diferente; pero no si se piensa en conjunto. Al asumir que las hormigas siguen su camino en lugar de darse la vuelta las estamos haciendo “intercambiar los papeles” de manera que la hormiga de la izquierda pasa a jugar el papel de la de la derecha y viceversa. Pero… después de todo… ¿eres capaz de diferenciar a las hormigas como para darte cuenta del cambio? 🙂

Con esta idea, hemos anulado la parte difícil del acertijo: los encuentros de hormigas. Podemos suponer que cada hormiga recorre el alambre de manera independiente a todas las demás. Con este nuevo planteamiento, saber el tiempo máximo que tardarán en caer todas las hormigas consiste en averiguar el tiempo que tardará en caer la última. Y eso significa buscar a la hormiga que esté más alejada de alguno de los extremos. Ahora, tendremos que suponer que cada hormiga empieza a desplazarse hacia el extremo más alejado, mirar la distancia, y quedarnos con la mayor. Con este truco, es fácil ver que en la primera pregunta del alambre de 20 centímetros, el tiempo máximo será de 17 segundos (la distancia al extremo derecho desde la posición de la primera hormiga), y para el alambre de 35 será de 29 segundos (de nuevo la distancia al extremo derecho de la posición de la primera hormiga).

¡Y eso es todo! Como siempre, si sabes programar y quieres probar tu solución, puedes hacerlo aquí. Y ¡te animamos a que lo intentes! Aunque el acertijo puede parecer difícil al principio, tras conocer el truco programarlo resulta sencillo, pues es cuestión de calcular el máximo y el mínimo 🙂

¡Hasta el próximo! Y, os recordamos, que esta vez tendréis que esperar un poquito más, porque el acertijo llegará el martes… con una sorpresa. ¡¡No os lo perdáis!!

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: