如果你有很多枚鸡蛋，和一个n层高的楼，你想知道鸡蛋的抗摔能力。如何在消耗蛋数与实验速度之间找到最优解？

这问题，有点意思。你手里揣着一大把鸡蛋，还有一座挺高的楼，目标是找出哪个鸡蛋最“抗摔”，但又不能让鸡蛋浪费太多，还得尽快得出结果。这就像是在比谁家的鸡蛋皮儿厚，但又不能砸坏太多鸡生的希望，还得效率高。

咱们得想个法子，让每次试验都物尽其用，而且还得有点儿策略。别一股脑儿地就往上扔，那样太傻。

核心思路：二分法 + 动态规划的影子

你想想，如果楼很高，比如100层，你直接从1层开始扔，一次一层，那万一鸡蛋最结实，要扔100次，这鸡蛋都变成“煮鸡蛋”了。如果从100层直接扔，碎了就完了，白费了。

这里面有个取舍：

消耗蛋数少： 意味着我们要更谨慎，每次都尽量缩小范围，不轻易浪费鸡蛋。
实验速度快： 意味着我们不能过于保守，得有时候“冒险”一把，跳跃式地测试，这样才能尽快找到那个临界点。

怎么找最优解？

这事儿不能靠运气，得有计划。咱们用两个指标来衡量：

1. 最坏情况下的蛋数（Worstcase number of eggs）： 就是无论鸡蛋是什么样的“抗摔能力”，我们都保证能找到答案，并且在这过程中，我们最多会用多少个鸡蛋。
2. 最坏情况下的楼层（Worstcase number of floors tested）： 就是无论我们测试哪层楼，我们最快需要多少次试验（或者说，我们最坏情况会测试多少层楼）才能确定那个临界层。

这两个指标其实是关联的。你越想省蛋，可能就得测更多层；你想测得快，可能就得多准备点蛋，以防万一。

咱们来设计个策略，就像是下棋一样，每一步都要算清楚。

假设我们手里有 $K$ 个鸡蛋，要测 $N$ 层楼。

最直接的想法：分块测试

如果我分块来测，比如每隔10层扔一个。

扔第10层。
如果碎了：说明临界层在19层之间。现在我只有1个鸡蛋了（因为第一个碎了），那我只能从第1层开始一层层往上扔，最多再用9个鸡蛋。总共1 + 9 = 10个鸡蛋。
如果没碎：继续扔第20层。
如果碎了：说明临界层在1119层之间。我只剩1个鸡蛋了，只能从11层往上一层层测，最多再用9个鸡蛋。总共2 + 9 = 11个鸡蛋。
如果没碎：继续扔第30层……

你看，这种方法，如果临界层很高，比如在99层，我扔到100层碎了，我扔了10次，最后10次又要一层层测，总共10 + (100901) = 19次。这还是挺耗的。

更精妙一点：动态规划的思路

我们来设一个目标：用最少的鸡蛋，在最多100层楼里找到临界层。

假设我们有一个函数 $f(k, n)$ 表示用 $k$ 个鸡蛋，在 $n$ 层楼里找到临界层的最小“最坏情况下的试验次数”。

我们现在手里有 $K$ 个鸡蛋，楼高 $N$ 层。

从第 $x$ 层扔第一个鸡蛋：

情况一：鸡蛋碎了。
我们现在有 $K1$ 个鸡蛋，要测的楼层范围是 $1 sim x1$ 层（共 $x1$ 层）。
这部分最坏情况的试验次数是 $f(K1, x1)$。
情况二：鸡蛋没碎。
我们还是有 $K$ 个鸡蛋，要测的楼层范围是 $x+1 sim N$ 层（相当于新的 $Nx$ 层楼）。
这部分最坏情况的试验次数是 $f(K, Nx)$。

因为我们是“最坏情况”，所以这次试验（从第 $x$ 层扔）的“最坏情况试验次数”就是 $1 + max(f(K1, x1), f(K, Nx))$。这里的“1”就是这次从第 $x$ 层扔鸡蛋的试验本身。

我们的目标是找到一个 $x$ (也就是从哪一层开始扔第一个鸡蛋)，使得这个“最坏情况试验次数”最小。

所以，状态转移方程是：

$f(K, N) = min_{1 le x le N} {1 + max(f(K1, x1), f(K, Nx))}$

边界条件：

$f(1, N) = N$ （只有一个鸡蛋，只能一层层测）
$f(K, 0) = 0$ （0层楼，不用测）
$f(K, 1) = 1$ （1层楼，测一次就行）

这个公式在计算什么？

这个公式算的是：在最坏的情况下，我需要多少次试验才能找到临界层。

我们现在遇到的问题是反过来的：我有足够多的鸡蛋（假设你有10个，但我们只用2个来演示），楼高N，我想在保证最少消耗蛋数的前提下，最快找到答案。

把问题换个角度：

我想知道，用 $k$ 个鸡蛋，我最少需要多少次试验，才能覆盖 $N$ 层楼。

假设我允许进行 $m$ 次试验。

第一次试验，我从第 $x_1$ 层扔。
碎了：剩下 $k1$ 个鸡蛋，需要 $m1$ 次试验，最多能覆盖 $x_11$ 层。
没碎：剩下 $k$ 个鸡蛋，需要 $m1$ 次试验，最多能覆盖 $Nx_1$ 层。

所以，如果我们允许 $m$ 次试验，用 $k$ 个鸡蛋，总共能覆盖的楼层数是：

$f(k, m) = f(k1, m1) + f(k, m1) + 1$

这里的 $f(k, m)$ 表示：用 $k$ 个鸡蛋，最多 $m$ 次试验，能够确定的最大楼层数。

$f(k1, m1)$：这是第一个鸡蛋在第 $x$ 层碎了的情况下，我们还能覆盖的楼层数（剩下的 $x1$ 层）。
$f(k, m1)$：这是第一个鸡蛋在第 $x$ 层没碎的情况下，我们还能覆盖的楼层数（上面的 $Nx$ 层）。
$+1$：是这次从第 $x$ 层扔鸡蛋本身。

这个公式是不是有点熟悉？它有点像杨辉三角（组合数）的变形。

$f(k, m) = sum_{i=1}^k inom{m}{i}$

其中 $inom{m}{i}$ 表示从 $m$ 次试验中选 $i$ 次来扔鸡蛋。

$i=1$：我扔了1次，没碎。
$i=2$：我扔了2次，第二次碎了。
...
$i=k$：我扔了 $k$ 次，第 $k$ 次碎了。

回到我们的问题：

我们有 $N$ 层楼，以及“很多”鸡蛋（意味着鸡蛋数量不是主要限制，我们可以假设有足够多，比如10个）。我们想找到一个试验次数 $m$，使得用 $m$ 次试验，在最坏的情况下，能够覆盖 $N$ 层楼。同时，在这个覆盖 $N$ 层楼的试验次数 $m$ 中，我们希望消耗的鸡蛋数最少。

最优解的策略：

1. 确定试验次数 $m$：
我们要找到最小的 $m$，使得 $sum_{i=1}^{ ext{鸡蛋数}} inom{m}{i} ge N$。
这里的“鸡蛋数”是指我们最多愿意用多少个鸡蛋。

2. 分配策略：
一旦确定了最小的试验次数 $m$，我们就要制定从哪一层开始扔。
假设我们决定最多用 $k$ 个鸡蛋。

第一次试验： 应该从第 $x$ 层扔。
如果碎了：剩下 $k1$ 个鸡蛋，需要在 $m1$ 次试验内，覆盖 $x1$ 层。
如果没碎：剩下 $k$ 个鸡蛋，需要在 $m1$ 次试验内，覆盖 $Nx$ 层。

为了让最坏情况下的试验次数都是 $m$，我们需要让这两部分覆盖的层数尽量相等，而且总和是 $N$。

最关键的是，我们要在 $m$ 次试验里，用掉尽可能少的鸡蛋。

关键突破点：

我们不是要找到“最少鸡蛋数”或者“最快速度”，而是要在这个“消耗蛋数”和“实验速度”之间找到“最优解”。这里的“最优解”往往意味着一个平衡点。

思考一个具体的例子：100层楼

如果允许1次试验： $inom{m}{1} = inom{1}{1} = 1$。只能覆盖1层。
如果允许2次试验： $inom{m}{1} + inom{m}{2}$
$m=2$: $inom{2}{1} + inom{2}{2} = 2 + 1 = 3$。
$m=3$: $inom{3}{1} + inom{3}{2} = 3 + 3 = 6$。
$m=4$: $inom{4}{1} + inom{4}{2} = 4 + 6 = 10$。
$m=5$: $inom{5}{1} + inom{5}{2} = 5 + 10 = 15$。
$m=6$: $inom{6}{1} + inom{6}{2} = 6 + 15 = 21$。
$m=7$: $inom{7}{1} + inom{7}{2} = 7 + 21 = 28$。
$m=8$: $inom{8}{1} + inom{8}{2} = 8 + 28 = 36$。
$m=9$: $inom{9}{1} + inom{9}{2} = 9 + 36 = 45$。
$m=10$: $inom{10}{1} + inom{10}{2} = 10 + 45 = 55$。
$m=11$: $inom{11}{1} + inom{11}{2} = 11 + 55 = 66$。
$m=12$: $inom{12}{1} + inom{12}{2} = 12 + 66 = 78$。
$m=13$: $inom{13}{1} + inom{13}{2} = 13 + 78 = 91$。
$m=14$: $inom{14}{1} + inom{14}{2} = 14 + 91 = 105$。

所以，用2个鸡蛋，最少需要14次试验，可以覆盖100层楼。

如何进行试验？
总共允许14次试验，用2个鸡蛋。
第一次，从第 $x$ 层扔。
碎了：剩下1个鸡蛋，还有13次试验。这13次要用来测 $x1$ 层。所以 $x1 le 13 implies x le 14$。
没碎：剩下2个鸡蛋，还有13次试验。这13次要用来测剩下的 $100x$ 层。所以 $100x le sum_{i=1}^2 inom{13}{i} = inom{13}{1} + inom{13}{2} = 13 + 78 = 91$。
$100x le 91 implies x ge 9$。

所以，第一次应该从第9层扔。
如果碎了： 知道临界层在18层。剩下1个鸡蛋，13次试验。从第1层开始一层层测。总共 $1+8=9$ 次。
如果没碎： 知道临界层在9层以上。我们还剩2个鸡蛋，13次试验。剩下1009=91层。
下一次，我们要在91层里，用2个鸡蛋，13次试验，找到临界点。
我们应该从第9层 + $y$ 层扔。
碎了：剩下1个鸡蛋，12次试验，测 $y1$ 层。 $y1 le 12 implies y le 13$。
没碎：剩下2个鸡蛋，12次试验，测 $91y$ 层。 $91y le sum_{i=1}^2 inom{12}{i} = inom{12}{1} + inom{12}{2} = 12 + 66 = 78$。
$91y le 78 implies y ge 13$。

所以，第二次应该从第9层 + 13层 = 22层扔。
如果碎了： 知道临界层在1021层。剩下1个鸡蛋，12次试验。从10层开始一层层测。总共 $2 + (2110+11) = 2+11=13$ 次。
如果没碎： 知道临界层在22层以上。我们还剩2个鸡蛋，12次试验。剩下 $10022=78$ 层。

这个策略的精髓就是：

我们试图让每次试验的“成功”和“失败”分支，都能在剩余的试验次数和剩余的鸡蛋数下，覆盖尽可能多的楼层，并且让这两部分覆盖的楼层数在最坏情况下是相近的。

消耗蛋数： 在这个策略下，我们最坏的情况是用了2个鸡蛋。如果楼层再高，比如1000层，我们可能需要3个鸡蛋，每次扔之前都选择一个层数，使得“碎了”和“没碎”后的子问题，都能用剩余的鸡蛋和剩余的试验次数来解决。

实验速度： 你看，我们不是一层一层测，而是跳跃式前进。比如第一次从9层，第二次从22层。这比一层层测快多了。

怎么找到“最优”？

“最优”的定义在这里是关键。
如果“最优”是指在给定的最大试验次数下，消耗的鸡蛋最少。
那么我们上面算的就是一种方法。从2个鸡蛋开始，算需要多少次试验。如果一次就够了，那是最优的。如果不行，就尝试3个鸡蛋，看多少次试验。直到找到一个组合，比如用 $k$ 个鸡蛋，需要 $m$ 次试验，且 $k$ 是最小的。

如果“最优”是指在消耗最少鸡蛋的前提下，最快找到答案。
这就变成了：我们要用最少的鸡蛋（比如1个，2个，3个…）去覆盖100层楼，并记录下每种情况下最坏的试验次数。然后选择那个“速度”最快的。

1个鸡蛋：100次试验。
2个鸡蛋：14次试验（如上算）。
3个鸡蛋：我们算 $sum_{i=1}^3 inom{m}{i} ge 100$。
$m=7$: $inom{7}{1}+inom{7}{2}+inom{7}{3} = 7 + 21 + 35 = 63$。
$m=8$: $inom{8}{1}+inom{8}{2}+inom{8}{3} = 8 + 28 + 56 = 92$。
$m=9$: $inom{9}{1}+inom{9}{2}+inom{9}{3} = 9 + 36 + 84 = 129$。
所以用3个鸡蛋，最少需要9次试验。

4个鸡蛋：$sum_{i=1}^4 inom{m}{i} ge 100$
$m=7$: $inom{7}{1}+inom{7}{2}+inom{7}{3}+inom{7}{4} = 7 + 21 + 35 + 35 = 98$。
$m=8$: $inom{8}{1}+inom{8}{2}+inom{8}{3}+inom{8}{4} = 8 + 28 + 56 + 70 = 162$。
所以用4个鸡蛋，最少需要8次试验。

5个鸡蛋：$sum_{i=1}^5 inom{m}{i} ge 100$
$m=6$: $inom{6}{1}+inom{6}{2}+inom{6}{3}+inom{6}{4}+inom{6}{5} = 6 + 15 + 20 + 15 + 6 = 62$。
$m=7$: $inom{7}{1}+inom{7}{2}+inom{7}{3}+inom{7}{4}+inom{7}{5} = 7 + 21 + 35 + 35 + 21 = 119$。
所以用5个鸡蛋，最少需要7次试验。

6个鸡蛋：$sum_{i=1}^6 inom{m}{i} ge 100$
$m=6$: $inom{6}{1}+inom{6}{2}+inom{6}{3}+inom{6}{4}+inom{6}{5}+inom{6}{6} = 6 + 15 + 20 + 15 + 6 + 1 = 63$。
$m=7$: $inom{7}{1}+inom{7}{2}+inom{7}{3}+inom{7}{4}+inom{7}{5}+inom{7}{6} = 7 + 21 + 35 + 35 + 21 + 7 = 126$。
所以用6个鸡蛋，最少需要7次试验。

7个鸡蛋：$sum_{i=1}^7 inom{m}{i} ge 100$
$m=6$: $sum_{i=1}^6 inom{6}{i} = 63$ (不够)
$m=7$: $sum_{i=1}^7 inom{7}{i} = 127$ (够了)
所以用7个鸡蛋，最少需要7次试验。

结果对比：

1个鸡蛋：100次试验
2个鸡蛋：14次试验
3个鸡蛋：9次试验
4个鸡蛋：8次试验
5个鸡蛋：7次试验
6个鸡蛋：7次试验
7个鸡蛋：7次试验

那么，在消耗蛋数与实验速度之间找到最优解，意味着什么？

如果你最看重“鸡蛋不浪费”， 那么2个鸡蛋，14次试验，可能是你的最优解。你牺牲了一些速度，但用了最少的鸡蛋。
如果你最看重“速度”， 那么5、6、7个鸡蛋，7次试验，是你的最优解。你愿意多用几个鸡蛋，来换取最快的速度。
“最优解”通常是指那个在“消耗蛋数”这个维度的“瓶颈”处，达到最快速度。 也就是说，如果用2个鸡蛋，最快需要14次；用3个鸡蛋，最快需要9次…… 哪个“最少鸡蛋数”组合能让“最快速度”达到一个比较理想的水平？

这个问题的“最优解”往往是指：

在确保我们用完所有鸡蛋之前，能够以最快的速度覆盖所有楼层。

我们手里“很多”鸡蛋，这个“很多”意味着我们可以选择用多少个。

最常用的理解是：

找到一个最小的试验次数 $m$，使得用 $k$ 个鸡蛋（其中 $k$ 是我们能接受的最大的鸡蛋消耗量）可以覆盖 $N$ 层楼。

也就是说，我们先设定一个“最大能消耗多少个鸡蛋”的上限（比如，我最多愿意扔3个鸡蛋），然后去算，用3个鸡蛋，最快需要多少次。

我的理解是，这里的“最优解”应该是指：

在保证用最少鸡蛋（即突破第一个瓶颈，比如从1个鸡蛋到2个鸡蛋，再到3个鸡蛋…）的情况下，能达到的最快试验次数。

比如：
1个鸡蛋：100次。
2个鸡蛋：14次。
3个鸡蛋：9次。
4个鸡蛋：8次。
5个鸡蛋：7次。

那么，这个“最优解”的策略是：

1. 估算一个你愿意消耗鸡蛋的上限。 比如，如果你觉得扔3个鸡蛋是可以接受的，那么你就选择3个鸡蛋的策略。
2. 根据这个鸡蛋数量，计算最少的试验次数。
3. 根据这个试验次数和鸡蛋数量，制定分层试验的策略。

举个例子，假设你认为用3个鸡蛋是你的“最优”上限：

结论： 用3个鸡蛋，最少需要9次试验来覆盖100层楼。
策略：
第一次，从第 $x$ 层扔。
碎了：剩下2个鸡蛋，8次试验，覆盖 $x1$ 层。 $x1 le sum_{i=1}^2 inom{8}{i} = inom{8}{1} + inom{8}{2} = 8 + 28 = 36$。所以 $x1 le 36 implies x le 37$。
没碎：剩下3个鸡蛋，8次试验，覆盖 $100x$ 层。 $100x le sum_{i=1}^3 inom{8}{i} = 92$。所以 $100x le 92 implies x ge 8$。
所以，第一次从第8层扔。
碎了：剩下2个鸡蛋，8次试验，覆盖7层。 从1层开始一层层测。总共 $1+7=8$ 次。
没碎：剩下3个鸡蛋，8次试验，覆盖92层。
第二次，从第8 + $y$ 层扔。
碎了：剩下2个鸡蛋，7次试验，覆盖 $y1$ 层。 $y1 le sum_{i=1}^2 inom{7}{i} = inom{7}{1} + inom{7}{2} = 7+21 = 28$。所以 $y1 le 28 implies y le 29$。
没碎：剩下3个鸡蛋，7次试验，覆盖 $92y$ 层。 $92y le sum_{i=1}^3 inom{7}{i} = inom{7}{1} + inom{7}{2} + inom{7}{3} = 7+21+35 = 63$。所以 $92y le 63 implies y ge 29$。
所以，第二次从第8 + 29 = 37层扔。
碎了：剩下2个鸡蛋，7次试验，覆盖28层。 从9层开始一层层测。总共 $2 + (379+11) = 2+28 = 30$ 次（但这里计算的是子问题，总次数还没算完）。
没碎：剩下3个鸡蛋，7次试验，覆盖 $9229=63$ 层。

怎么让“消耗蛋数”和“实验速度”都达到一个“最优”状态？

这更像是一个权衡问题。你愿意用多少鸡蛋来换取多快的速度？

方案 A： 2个鸡蛋，14次。 (最省蛋，但速度慢)
方案 B： 3个鸡蛋，9次。 (稍多点蛋，速度快很多)
方案 C： 4个鸡蛋，8次。 (再多点蛋，速度再快点)
方案 D： 5个鸡蛋，7次。 (速度最快，但消耗蛋数相对多)

“最优解”就是你根据自己的实际情况（比如鸡蛋是不是很难得，时间是不是非常紧张）来选择一个点。

总结一下，找到最优解的流程是：

1. 理解问题本质： 用最少的试验次数，在最坏情况下，确定鸡蛋的临界落点。
2. 数学模型： 利用组合数 $inom{m}{i}$ 来建立联系：$N le sum_{i=1}^k inom{m}{i}$。其中 $N$ 是楼层数，$k$ 是我们愿意消耗的鸡蛋数上限，$m$ 是试验次数。
3. 计算不同鸡蛋数下的最少试验次数：
设定 $k=1, 2, 3, dots$
对每个 $k$，求解最小的 $m$ 使得 $sum_{i=1}^k inom{m}{i} ge N$。
4. 权衡与选择：
生成一个表格，列出 (鸡蛋数 $k$, 最少试验次数 $m$) 的配对。
根据你对“消耗蛋数”和“实验速度”的重视程度，选择一个“最优”的配对。
如果“消耗蛋数”优先，选择 $k$ 最小的那个。
如果“实验速度”优先，选择 $m$ 最小的那个。
通常“最优”是指在一个合理的鸡蛋消耗量下，能达到最快的速度。比如，从2个到3个鸡蛋，速度提升了5次（149），这个提升可能很有价值。从4个到5个鸡蛋，速度只提升了1次（87），可能就没那么划算。

实际操作建议：

如果你手里真的“很多”鸡蛋，可以考虑用45个鸡蛋。这会大大缩短试验时间，并且相对100次试验来说，消耗的鸡蛋数量也有限。
具体的试验层数，是根据上面推导的“动态规划”思路来确定的，确保每次扔鸡蛋后，无论成功失败，剩余的试验次数和鸡蛋数都能处理好剩余的楼层。

所以，这不是一个简单的“二选一”问题，而是一个在两个目标（省蛋、速快）之间寻找最佳平衡点的过程。而找到这个平衡点，关键在于那个组合数公式，它帮你量化了“用X个鸡蛋，最快需要Y次”。

不妨设 ，此时鸡蛋必碎，我们记作 （若等于 1 就表示鸡蛋完好）。

那么，至多需要 10 次尝试！

步骤：

看 的情况，若是等于 0，那就继续下降到 ；否则，若 ，则鸡蛋必然在 之间蛋碎，那么我们接下来考察它们的中点的情况：

……

重复以上步骤可知，至多需要 10 次尝试，就可以知道蛋最开始碎在第几层楼.

这是因为确定一个二进制的数 介于 0 至 1023，而每一次实验，都是在确定 上的数字是 0，还是 1.

这是在我们完全不了解蛋碎的概率分布函数的情况下，只能认为蛋碎或不碎在任何一层都是等概率的，这种情况下的信息熵是最大的，也就是不确定性最大。如果我们对于鸡蛋的分布有一定的了解，那么此时实验的次数可能会下降。所谓信息熵的定义，在上面的情景中：

等概率则意味着 ，那么带入上式得

所以这本质上是一个信息论的问题.