What’s The Best Way To Drop A Smartphone?

You work for a tech firm developing a smartphone that supposedly survives falls from great heights, and you want to advertise the highest floor from which it can be dropped without breaking. You are given two phones and a 100-story tower. From any floor you may drop a phone; if it survives you may reuse it, but if it breaks it is gone. Using the two phones, what is the minimum number of drops that guarantees you can find the exact highest floor from which a phone does not break? What if the tower were 1,000 stories?

The Riddler, FiveThirtyEight(original post)

Solution

Plan the drops of the first phone in advance and ask how tall a tower a fixed budget of $d$ drops can resolve. Drop the first phone at some floor. If it breaks, the second phone is your only instrument, and it must walk up one floor at a time through the untested floors below, so with $d-1$ drops left it can clear at most $d-1$ of them. To stay within budget the first drop should therefore be at floor $d$: a break there leaves floors $1$ through $d-1$ for the second phone, exactly $d-1$ more drops.

If instead the first phone survives floor $d$, one drop is spent and $d-1$ remain, so the next first-phone drop may sit $d-1$ floors higher, at $d+(d-1)$. Each survival lets the next gap shrink by one. The highest floor reachable in $d$ drops is thus $$d + (d-1) + (d-2) + \cdots + 1 = \frac{d(d+1)}{2}.$$ The smallest $d$ that covers $f$ floors is the smallest $d$ with $d(d+1)/2 \ge f$. For $f = 100$, since $\tfrac{13\cdot 14}{2}=91 < 100 \le 105 = \tfrac{14\cdot 15}{2}$, the answer is $\boxed{14}$. For $f = 1{,}000$, since $\tfrac{44\cdot 45}{2}=990 < 1000 \le 1035 = \tfrac{45\cdot 46}{2}$, the answer is $\boxed{45}$.

The computation

Encode the choice itself. Let $F(p, d)$ be the largest number of floors that $p$ phones and $d$ drops can fully resolve. One drop splits the tower: if the phone breaks, $p-1$ phones and $d-1$ drops resolve the floors below; if it survives, $p$ phones and $d-1$ drops resolve the floors above; the tested floor is pinned. So $F(p,d) = F(p-1,d-1) + F(p,d-1) + 1$. The answer is the least $d$ with $F(2, d) \ge f$.

from functools import lru_cache

@lru_cache(maxsize=None)
def resolvable(phones, drops):           # most floors p phones, d drops can resolve
    if phones == 0 or drops == 0:
        return 0
    return resolvable(phones - 1, drops - 1) + resolvable(phones, drops - 1) + 1

def min_drops(phones, floors):
    d = 0
    while resolvable(phones, d) < floors:
        d += 1
    return d

print(min_drops(2, 100), min_drops(2, 1000))
# 14 45