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.)

Advertisements

3 thoughts on “La caída de las lámparas

  1. Kardo says:

    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 says:

      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.

  2. […] 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 […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s