Rompecabezas | Set 35 (2 Huevos y 100 Pisos)

La siguiente es una descripción de la instancia de este famoso rompecabezas que involucra 2 huevos y un edificio con 100 pisos. 

Suponga que deseamos saber en qué pisos de un edificio de 100 pisos es seguro dejar caer los huevos y cuáles harán que los huevos se rompan al aterrizar. ¿Qué estrategia se debe usar para dejar caer los huevos de tal manera que se minimice un número total de gotas en el peor de los casos y encontremos el piso requerido? 

Podemos hacer algunas suposiciones: 

• Un huevo que sobrevive a una caída se puede volver a utilizar.
• Un huevo roto debe ser desechado.
• El efecto de una caída es el mismo para todos los huevos.
• Si un huevo se rompe cuando se deja caer, se romperá si se cae desde un piso más alto.
• Si un huevo sobrevive a una caída, sobrevivirá a una caída más corta.

Le recomendamos encarecidamente que minimice su navegador e intente esto usted mismo primero. 

Si solo se dispone de un huevo y deseamos estar seguros de obtener el resultado correcto, el experimento se puede realizar de una sola manera. Deja caer el huevo desde la ventana del primer piso; si sobrevive, tíralo desde la ventana del segundo piso. Continúe hacia arriba hasta que se rompa. En el peor de los casos, este método puede requerir 100 excrementos. 
Supongamos que hay 2 huevos disponibles. ¿Cuál es el menor número de excrementos de huevo que se garantiza que funcionen en todos los casos? 
El problema no es en realidad encontrar el piso crítico, sino simplemente decidir los pisos desde los cuales se deben dejar caer los huevos para minimizar el número total de ensayos. 

Si usamos el método de búsqueda binaria para encontrar el piso y comenzamos desde el piso 50, terminaremos haciendo 50 comparaciones en el peor de los casos. El peor de los casos ocurre cuando el piso requerido es el piso 49. 

Método optimizado:  la idea es optimizar la solución utilizando la siguiente ecuación: 

Let us make our first attempt on x'th floor. 

If it breaks, we try remaining (x-1) floors one by one. 
So in worst case, we make x trials.

If it doesn't break, we jump (x-1) floors (Because we have
already made one attempt and we don't want to go beyond 
x attempts.  Therefore (x-1) attempts are available),
    Next floor we try is floor x + (x-1)

Similarly, if this drop does not break, next need to jump 
up to floor x + (x-1) + (x-2), then x + (x-1) + (x-2) + (x-3)
and so on.

Since the last floor to be tried is 100'th floor, sum of
series should be 100 for optimal value of x.

 x + (x-1) + (x-2) + (x-3) + .... + 1  = 100

 x(x+1)/2  = 100
         x = 13.651

Therefore, we start trying from 14'th floor. If Egg breaks on 14th floor
we one by one try remaining 13 floors, starting from 1st floor.  If egg doesn't break
we go to 27th floor.
If egg breaks on 27'th floor, we try floors form 15 to 26.
If egg doesn't break on 27'th floor, we go to 39'th floor.

An so on...

El número óptimo de ensayos es 14 en el peor de los casos. 

Vea a continuación una solución de programación para k huevos y n pisos generales. 
https://www.geeksforgeeks.org/dynamic-programming-set-11-egg-dropping-puzzle/ 

Este artículo es una contribución de Rachit . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.