Egg Dropping Reloaded

Relevant wiki: Egg Dropping

So the strategy to obtain $24$ :

drop one egg, until it breaks, from floors 12, 12+12, 12+12+11, 12 + 12 + 11 + 11, . . . , 12 + 12 +· · ·+ 8 + 8. If it never breaks, then the egg was fake and thus it reduces to the 100-floor, two-egg problem. If it breaks on some floor, then drop both eggs on each floor from the bottom up until an egg breaks. Its easy to calculate that this strategy will use either 23 or 24 drops in all of the cases. Now, given any optimal strategy, we can modify it into another optimal strategy so that the strategy consists of iteratively dropping only one egg. Therefore, it suffices to find an increasing sequence of floors $1 ≤ a_1 < a_2 < · · · < a_n-1 < 100 ≤ a_n$ that is optimal.

If the egg never breaks then we have made n drops, so we will finish in $n + 14$ drops. If an egg drops on floor a k, then we will necessarily need 2(a k − 1 − a_k−1) more drops. Thus, we want to minimize max{ $n + 14, 1 + 2(a_1 - 1), 2 + 2(a_2 - a_1 - 1), . . . , n + 2(a_n - a_n-1 - 1)$ }.

By the averaging principle, we have

$max (1+2(a_1-1), 2+2(a_2-a_1-1), . . . , n+2(a_n-a_n-1-1)) ≥ \frac{n(n + 1)/2 + 2(a_n - n)}{n} ≥ \frac{n(n + 1)/2 + 2(100 - n)}{n})$ . When $n ≤ 9$ , this is $≥ 24$ . When $n ≥ 11, n + 14 > 24$ . Therefore, n = 10, which already means the maximum is at least 24.

---

Solution Courtesy : CMIMC.