La caída de las lámparas
We want to figure out how strong our new super-strong light bulbs
are. We know that they will be break when dropped from the top floor
of this building (the 101st). We want to know the exact minimum floor
from which a fall will cause the light bulb to break. You’ll be given
two light bulbs for this task and we want you to do it with the
minimum number of trials.
(Extraído del blog de Louis Brandy.)
Kardo dijo:
Noviembre 17, 2009 a 9:17 pm
Lo que se intenta acá es minimizar la cantidad de intentos, entonces voy a proponer una función a la cual obtenerle el mínimo. Dejando de lado la idea de probar piso por piso, una mejor idea sería, por ejemplo, probar con una lámpara en los pisos pares. En el momento que la lámpara se rompa, probar en el piso inmediato anterior, para saber si el piso par o el impar anterior es el mínimo. De esta forma también se podría probar en los pisos múltiplos de 3. Cuando la lámpara se rompa, probar dos pisos más abajo y en el piso anterior, para saber si el piso múltiplo de 3 o alguno de los dos anteriores a este es el piso mínimo. Siguiendo este pensamiento, la idea es probar en los pisos múltiplos de N y, en el momento que la lámpara se rompe, probar en los anteriores N-1 pisos para buscar el piso mínimo. De esta forma, si buscamos el mínimo de la función f(100/N+N-1) con 1<N<100, encontramos que ese valor es 19.
mchouza dijo:
Noviembre 17, 2009 a 10:44 pm
Si, 19 es el mínimo número de intentos requerido siguiendo una secuencia “razonable”. El óptimo es 14 (en el próximo post voy a mostrar como obtenerlo mediante programación dinámica), pero no se obtiene mediante una secuencia regular de intentos.
La caída de las lámparas… resuelta « Spin Foam dijo:
Noviembre 24, 2009 a 2:26 am
[...] 24, 2009 at 2:25 am (informática, matemática, misc) En un comentario del post anterior, Kardo mostraba una solución al problema en 19 intentos: … Siguiendo este [...]