viernes, 2 de agosto de 2013

1190 - Bugs Bunny & Elmer

Todos sabemos que Bugs Bunny le roba las zanahorias a Elmer.
Un día Bugs cansado de que Elmer lo persiga durante todo el día le hace la siguiente proposición.
-Yo tengo hechos cinco pozos que podemos denominar de  izquierda a derecha como 1,2,3,4 y 5
Cada noche voy a dormir en un pozo diferente y adyacente al que dormí el día anterior, así si ayer dormí en el 2, hoy puede ser que duerma en el 1 o en el 3, pero si dormí en el 1 solo podré dormir en el 2 al día siguiente (lo mismo si dormí en el 5, solo podré dormir en el 4). Todas las mañanas vos vas a mirar en un solo pozo, si estoy ahí ganaste y me voy, sino gano yo y no me molestas en todo el día.
Elmer aceptó pero nunca adivina donde duerme Bugs (todos sabemos que Elmer no es muy inteligente)

¿Que táctica puede usar Elmer para encontrar a Bugs? ¿ En cuantos días se asegura de encontrarlo?
Si en vez de 5 pozos hubiera N pozos se puede establecer una estrategia similar?

Adaptado de un problema de la colección de Rustan M Leino en Microsoft Research

Si lo quieres compartir o guardar
Share/Bookmark

3 comentarios:

  1. 1) miro en la 2, si no esta, en la proxima puede estar 2345
    2)miro la 3, en la proxima puede estar 1345
    3)miro la 4, en la proxima 24,
    4)miro cualquiera es lo mismo, supongamos la 4, en la proxima 13
    5)miro la 3, si no esta estaba en la 1, y en la proxima solo puede estar en la 2
    6) acierto como maximo

    ResponderEliminar
  2. Si fuera un problema de pensamiento lateral se podría resolver de la siguiente forma:
    Elmer va "cerrando" pozos de forma que reduce las posibilidades de Bugs.
    :)

    Vicente iq.

    ResponderEliminar
  3. La respuesta de Pablo es correcta: 2, 3, 4, 4, 3, 2; encontrando a Bugs en 6 días. Si hubieran N pozos se podría adoptar la misma estrategia: 2, 3, 4, 5,..., N-1, N-1, N-2,..., 4, 3, 2. Encontraría a Bugs en máximo 2N-4 días.

    La explicación, quizá un poco largo jeje, pero básicamente, primero haces un barrido hacia la derecha en los pozos, y si no encuentras a bugs al llegar al penúltimo pozo, o esta en el último, o estaba en algún momento en un pozo contiguo al que revisaste, al repetir el penúltimo pozo, si no lo encuentras es porque estuvo contiguo a tí, pero ya no podrá estarlo debido a que repetiste pozo, haces barrido hacia la izquierda y con seguridad te lo encuentras máximo al llegar al pozo 2.

    ResponderEliminar

Si quieres deja un comentario, si la entrada tiene mas de 15 dias deberás esperar a que la autorice y por favor si no tienes gmail deja tu nombre si no quedas como anónimo. Gracias!