Two Eggs, d Drops: Maximum Floors
You have $2$ identical eggs and a building with $n$ floors. You want to find the highest floor from which an egg can be dropped without breaking -- call this the critical floor. The critical floor could be any value from $0$ (the egg breaks even on floor $1$) up to $n$ (the egg never breaks).
The rules are simple: if an egg survives a drop, you can reuse it. If it breaks, it's gone. If it breaks on floor $k$, it breaks on every floor above $k$ too, and if it survives floor $k$, it survives every floor below $k$.
What is the maximum value of $n$ such that you can always identify the critical floor using at most $d$ drops? Give the answer for $d = 10$.
Hints
- Think about your first drop. If the first egg breaks there, you are down to one egg -- what does that force you to do with the remaining drops?
- If you have $k$ drops remaining and the first egg breaks, you can only search $k - 1$ more floors (linear scan with the second egg). So the gap between consecutive first-egg drops should equal the number of remaining drops.
- The gaps decrease as you go up: $d, d-1, d-2, \ldots, 1$. The total number of floors covered is the sum $d + (d-1) + \cdots + 1$.
Worked Solution
How to Think About It: This is a classic minimax search problem. You have two eggs and a budget of $d$ drops, and you want to cover as many floors as possible. With only one egg, you would have to search linearly from the bottom, checking one floor at a time -- so one egg and $d$ drops covers $d$ floors. The second egg lets you skip ahead, but once the first egg breaks, you are back to linear search with the second egg and however many drops you have left. The key tension: the higher you go for the first drop, the more floors you skip, but the more floors you need to linearly check if it breaks. You need to balance these.
Quick Estimate: With 10 drops and 1 egg, you cover 10 floors. With 2 eggs, the second egg lets you "binary-search-ish" but not quite since you only have 2 eggs, not $\log n$. Intuitively, you can do much better than 10 but not as well as $2^{10} = 1024$. A natural strategy is to drop the first egg every $k$ floors. If it breaks at floor $k$, you linearly search floors $1$ through $k-1$ with the remaining egg. With a fixed gap of $k$ and $d$ total drops, you cover about $k \cdot (d - k + 1)$ floors, which is maximized when $k \approx d/2$, giving roughly $d^2/4 \approx 25$ floors. But we can do better by shrinking the gap as we go up. With a decreasing gap strategy, we should get roughly $d(d+1)/2 = 55$ floors.
Approach: The optimal strategy uses decreasing gaps. On your first drop, if the egg breaks, you need to linearly search the floors below with your remaining $d-1$ drops using the second egg. So the first drop should be at floor $d$, leaving you enough drops to cover the gap.
Formal Solution:
Suppose you have $d$ drops remaining and both eggs intact. Drop the first egg at floor $f_1$.
- If it breaks, you have $1$ egg and $d-1$ drops left, so you can search at most $d-1$ floors below $f_1$ (linear search). So set $f_1 = d$.
- If it survives, you have $2$ eggs and $d-1$ drops left. Now drop the first egg at floor $f_1 + (d-1)$.
- If it breaks, you have $1$ egg and $d-2$ drops, so you can search at most $d-2$ floors. The gap of $d-1$ floors (minus the one you already tested) leaves exactly $d-2$ floors to check. This works.
- If it survives, repeat with gap $d-2$, then $d-3$, and so on.
The floors tested by the first egg are:
$$f_1 = d, \quad f_2 = d + (d-1), \quad f_3 = d + (d-1) + (d-2), \quad \ldots$$
The highest reachable floor is:
$$f_d = d + (d-1) + (d-2) + \cdots + 1 = \frac{d(d+1)}{2}$$
If the egg survives every first-egg drop including floor $\frac{d(d+1)}{2}$, then the critical floor is $\frac{d(d+1)}{2}$ (the building's top floor). Every possible critical floor from $0$ to $\frac{d(d+1)}{2}$ is uniquely identifiable.
For a building with $n = \frac{d(d+1)}{2} + 1$ floors, if the egg survives all drops through floor $\frac{d(d+1)}{2}$, you cannot distinguish whether the critical floor is $\frac{d(d+1)}{2}$ or $\frac{d(d+1)}{2} + 1$. So $\frac{d(d+1)}{2}$ is the maximum.
For $d = 10$:
$$n = \frac{10 \times 11}{2} = 55$$
Answer: The maximum number of floors is $n = \frac{d(d+1)}{2}$. For $d = 10$, the answer is $\boxed{55}$.
Intuition
This problem is really about resource allocation under worst-case constraints. You have two resources -- eggs and drops -- and you need to divide your drop budget between "exploration" (jumping ahead with the first egg) and "exploitation" (linearly scanning with the second egg after a break). The decreasing-gap strategy is optimal because each time the first egg survives, you have used one of your drops, so you have fewer drops left for the linear scan if the first egg breaks on the next attempt. The gap must shrink to match.
The $d(d+1)/2$ formula is just the sum $1 + 2 + \cdots + d$, which shows up constantly in interview problems involving triangular numbers. The same structure appears in problems about minimizing worst-case queries with limited "lives" -- it generalizes to the $k$-egg version via binomial coefficients. In practice, this style of reasoning (balancing aggressive and conservative searches under a query budget) is exactly how you think about optimal execution in trading: you have a finite time window and need to balance information gathering with action.