两个鸡蛋 100 层楼

题

一栋 100 层的楼，鸡蛋从某层及以上扔下会碎，以下不碎——临界层未知（也可能 100 层都不碎）。你有 2 个一模一样的鸡蛋，没碎的可以捡回来再扔。最坏情况下最少要扔几次才能确定临界层？

一句话

14 次——第一颗蛋依次在 14、27、39、50……层扔，间隔每次少 1；因为 \(1 + 2 + \cdots + 14 = 105 \ge 100\)，而 \(1 + \cdots + 13 = 91 < 100\)。

关键技巧

把问题倒过来问：给定 \(k\) 个蛋、\(m\) 次机会，最多能测多少层？ 记为 \(f(k, m)\)。第一次在某层扔：

碎了——剩 \(k-1\) 个蛋、\(m-1\) 次，只能测下面，下面最多容纳 \(f(k-1, m-1)\) 层；
没碎——剩 \(k\) 个蛋、\(m-1\) 次，上面最多容纳 \(f(k, m-1)\) 层。

加上扔的这一层本身：

\[ f(k, m) = f(k-1, m-1) + f(k, m-1) + 1, \qquad f(0, m) = f(k, 0) = 0 \]

这正是帕斯卡三角的递推（差一个 \(+1\)），闭式是

\[ f(k, m) = \sum_{i=1}^{k} \binom{m}{i} \]

直觉：每个楼层对应一条"碎/不碎"的结果序列，长度 \(\le m\)、至多 \(k\) 次碎。正向 DP"\(n\) 层要几次"是 \(O(kn^2)\) 的 minimax，倒过来问只要 \(O(km)\)，还给出闭式。

解

\(k = 2\)：\(f(2, m) = m + \binom{m}{2} = \frac{m(m+1)}{2}\)。\(f(2, 13) = 91 < 100 \le 105 = f(2, 14)\)，答案 14。

方案直接从递推读出来：第一颗蛋第一次扔在第 \(f(1, 13) + 1 = 14\) 层——碎了，第二颗从 1 层逐层扔到 13 层，最坏共 \(1 + 13 = 14\) 次；没碎，问题变成"2 个蛋、13 次"，往上再跨 13 层到 27 层。依此类推，第一颗蛋的落点是

\[ 14,\ 27,\ 39,\ 50,\ 60,\ 69,\ 77,\ 84,\ 90,\ 95,\ 99,\ 100 \]

间隔 14、13、12……逐次减 1——每多扔一次第一颗蛋，就要给第二颗蛋少留一次，所以步长必须递减，最坏情况才处处等于 14。

延伸

常见错误：等距跳。每 10 层扔一次，最坏是在 100 层才碎、再从 91 扔到 99，共 \(10 + 9 = 19\) 次；遍历所有等距步长，最好也是 19。等距的问题是第一颗蛋扔得越多，留给第二颗的活没有同步减少。
\(k\) 个蛋、100 层：\(k = 1, 2, 3, 4, 5, 6, 7\) 时分别需要 100、14、9、8、7、7、7 次。\(k \ge 7\) 后就是二分，\(\lceil \log_2 101 \rceil = 7\)——蛋多到用不完，\(f(k, m) = 2^m - 1\)。
规模感：1000 层时 2 个蛋要 45 次、3 个蛋要 19 次。一般 \(f(2, m) \sim m^2/2\)，所以 2 个蛋约 \(\sqrt{2N}\) 次；\(k\) 个蛋约 \((k!\,N)^{1/k}\) 次。
正向 DP 也能做：\(W(k, n) = 1 + \min_x \max\bigl(W(k-1, x-1),\ W(k, n-x)\bigr)\)，结果与上面一致，但慢一个量级——面试里写出倒过来的版本是加分项。
同一个"数结果序列"：毒酒与小白鼠问 \(m\) 只老鼠能区分多少瓶——每只老鼠死或不死是一位，\(m\) 位最多区分 \(2^m\) 种情况。蛋题是同一招，只是"碎"的次数被 \(k\) 限住，于是 \(2^m\) 缩成 \(\sum_{i \le k} \binom{m}{i}\)。

数值验证

from math import comb
from functools import lru_cache

def floors(k, m):
    """k 个蛋、m 次扔最多能测多少层。"""
    return sum(comb(m, i) for i in range(1, k + 1))

def need(k, N):
    m = 0
    while floors(k, m) < N:
        m += 1
    return m

print(floors(2, 13), floors(2, 14))            # 91 105
print([need(k, 100) for k in range(1, 9)])     # [100, 14, 9, 8, 7, 7, 7, 7]
print(need(2, 1000), need(3, 1000))            # 45 19

@lru_cache(None)
def worst(k, n):
    """经典 minimax DP：k 个蛋、n 层未知时最坏要扔几次。"""
    if n == 0: return 0
    if k == 1: return n
    return 1 + min(max(worst(k - 1, x - 1), worst(k, n - x)) for x in range(1, n + 1))

print([worst(k, 100) for k in range(1, 8)])    # [100, 14, 9, 8, 7, 7, 7]

# 两蛋最优方案的第一颗蛋落点（最后一个截到 100）
s, plan = 0, []
for step in range(14, 0, -1):
    s += step
    plan.append(s)
    if s >= 100: break
print(plan)   # [14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 102]

def worst_equal_step(step, N=100):
    """第一颗蛋每隔 step 层扔一次，破了再从上一个安全层逐层往上。"""
    w = 0
    for t in range(N + 1):                      # t = 最高安全层
        drops, lo, x = 0, 0, step
        while True:
            x = min(x, N); drops += 1
            if x > t: break
            lo = x
            if x == N: break
            x += step
        if t < N:
            hi = x - 1
            drops += min(t, hi) - lo + (t < hi)
        w = max(w, drops)
    return w

print(worst_equal_step(10))                    # 19
print(min(worst_equal_step(s) for s in range(1, 101)))   # 19