No es un problema de valentía ni de paciencia, sino de diseño del peor caso. Toda su elegancia está en encontrar un plan que no brille cuando todo sale bien, sino cuando todo sale mal.
El edificio de 100 pisos y los dos huevos
Enunciado
Tienes dos huevos idénticos y acceso a un edificio de 100 pisos.
Existe un piso crítico tal que:
- si un huevo se deja caer desde ese piso o desde uno superior, se rompe;
- si se deja caer desde un piso inferior, no se rompe.
Necesitas determinar ese piso crítico minimizando, en el peor caso, el número de lanzamientos.
¿Cuál es el menor número de lanzamientos que puedes garantizar en el peor caso, y qué estrategia lo consigue?
Ver solución
Solución
Respuesta: el mínimo en el peor caso es 14 lanzamientos.
Hay que equilibrar dos riesgos:
- si el primer huevo se rompe muy pronto, necesitas muchos intentos lineales con el segundo;
- si lo reservas demasiado, gastas demasiados lanzamientos en subir.
La estrategia óptima reduce en uno el tamaño del salto en cada prueba. El primer huevo se lanza desde:
- piso 14,
- piso 27,
- piso 39,
- piso 50,
- y así sucesivamente, sumando cada vez un valor una unidad menor que el anterior.
Con este diseño, si el huevo se rompe en cualquier prueba, el número de pisos que quedan por revisar con el segundo coincide exactamente con los lanzamientos aún disponibles. No se desperdicia ninguno.
Se necesita el menor entero \(n\) tal que
Como \(14 \cdot 15 / 2 = 105\), el valor mínimo es \(n = 14\).
Ese es el número de lanzamientos garantizado en el peor caso.