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
Entradas
1) miro en la 2, si no esta, en la proxima puede estar 2345
ResponderEliminar2)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
Si fuera un problema de pensamiento lateral se podría resolver de la siguiente forma:
ResponderEliminarElmer va "cerrando" pozos de forma que reduce las posibilidades de Bugs.
:)
Vicente iq.
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.
ResponderEliminarLa 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.