双蛋问题

**雙蛋問題**（**The Two Eggs Problem**）是一個經典的算法問題，它經常被描述為「給你兩個相同的異常堅硬的雞蛋，通過在一棟 100 層的樓的不同層扔下雞蛋進行實驗，試驗出可以摔碎該雞蛋的最高樓層（臨界樓層）。已知未碎的雞蛋可以重複使用。求最少的實驗次數 n, 使得在 n 次實驗後，一定能判斷出該臨界樓層。」

該問題可以擴展為這樣一類問題： 在 N 個雞蛋，k 層樓的條件下，找到一個最小的 m，使得存在一種方案，在 m 次實驗以後，一定能找到雞蛋的臨界樓層。

## 問題假設

為了更加精確地思考問題，該問題中必須滿足以下的條件：

1. 如果雞蛋在某一層沒有碎，它不會在任何更低層的破碎。
2. 如果雞蛋在某一層碎了，它在更高層上一定會碎。
3. 雞蛋可能在一樓摔破，也可能在最高層還不摔破。

## 解決方案

此時，你有 2 個雞蛋，樓高 100 層。我們可以先思考有 1 個雞蛋和有無數個雞蛋的情況。

### 1 個雞蛋

此時，由於只有一個雞蛋，所以一旦破碎，那麼就無法繼續進行試驗，我們只能從第 1 層開始，一層一層地實驗。在這種情況下最多需要 99 次實驗。

### 無數個雞蛋

容易的解決方案是二分法， $\log _{2}{100}\approx 6.644<7$ , 所以如果我們有無數個雞蛋，我們最多只需要 7 次就可以試驗出。比如，先在 64 樓扔一次雞蛋，如果碎了，那就到 32 層扔第二次，如果第二次扔雞蛋又碎了，再到 16 層去扔第三次，如果這次沒有碎，那你可以再到第 24 層去扔第四次，又沒碎，那就去 28 層扔第五次，還是沒有碎，再到 30 層扔第六次，這次又碎了，再到 29 層扔第七次，第七次碎了，那麼臨界樓層就是第 28 層，第七次沒碎，臨界樓層就是第 29 層。所以無數個雞蛋最多只需要 7 次就可以實驗。

### 兩個雞蛋

藉助於二分法提供的分組思想，我們可以嘗試將 100 平均分成 10 組，用第一個雞蛋在每組最後一層進行實驗，這樣可以實驗出臨界樓層在哪一組。然後再用第二個雞蛋從該組第一層依次實驗。這種方案的最壞情況是 19 次。

我們發現，如果 19 層是臨界樓層，只需要實驗 11 次，而如果臨界層是 99 層，就需要實驗 19 次。因此我們是否可以將 19 次平均到 11 次裡一部分？為此，有以下方案，第一組 $x$ 人，第二組 $(x-1)$ 人，第三組 $(x-2)$ 人，…… 第 x 組 1 人，考慮到 $x+(x-1)+(x-2)+\cdots +3+2+1={\frac {x(x+1)}{2}}>100$ ，解得 $x>13.65$ ，所以 $x=14$ 時，最多需要 14 次便可以找出臨界樓層。

## 推廣問題

下面是雙蛋問題的幾個推廣問題。

### 2 個雞蛋，k 層樓

類似於之前的方法，只需要 $x+(x-1)+(x-2)+\cdots +3+2+1={\frac {x(x+1)}{2}}>k$ 即可，可以求出 $k=\left\lceil {\frac {-1+{\sqrt {1+8k}}}{2}}\right\rceil $ （參見取整函數、高斯符號）

### n 個雞蛋，k 層樓

讓我們定義一個函數 $f(d,n)$ , 表示有 $n$ 個雞蛋，通過 $d$ 次實驗就一定能夠判斷出臨界樓層的最大樓層。 如果雞蛋打破，我們將能夠將臨界樓層範圍縮小到 f (d−1,n−1) 層；否則我們將能夠把範圍縮小到 f (d-1,n) 層。

因此， $f(d,n)=1+f(d-1,n-1)+f(d-1,n)$ 。這只是一個遞歸關係，而我們必須找到一個函數 f (d,n)。

因此，我們將定義一個輔助函數 $g(d,n):g(d,n)=f(d,n+1)-f(d,n)$

根據我們的第一個方程

 ${\begin{aligned}g(d,n)&=f(d,n+1)-f(d,n)\\&=f(d-1,n+1)+f(d-1,n)+1-f(d-1,n)-f(d-1,n-1)-1\\&=[f(d-1,n+1)-f(d-1,n)]+[f(d-1,n)-f(d-1,n-1)]\\&=g(d-1,n)+g(d-1,n-1)\end{aligned}}$ 函數 $g(d,n)$ 可以寫成 $g(d,n)={\binom {d}{n}}$ （參見二項式係數）

但是我們有一個問題：根據之前的關係 $f$ 和 $g$ ，對於任何 $n$ ， $f(0,n)$ 以及 $g(0,n)$ 都是 $0$ 。然而，在 $n=0$ 時會發生矛盾，因為 $g(0,0)={\binom {0}{0}}=1$ ，但對於每一個 $n$ ， $g(0,n)$ 應該是 $0$ ! 

我們可以通過重定義 $g(d,n)$ 修復這個問題如下：

$$
g(d,n)={\binom {d}{n+1}}
$$

遞歸是仍然有效。

現在，展開 f (d,n), 我們可以把它寫成

$$
{\begin{aligned}f(d,n)=&[f(d,n)-f(d,n-1)]\\+&[f(d,n-1)-f(d,n-2)]\\+&\cdots \\+&[f(d,1)-f(d,0)]\\+&f(d,0).\end{aligned}}
$$

我們知道 $f(d,0)=0$ , 因此

$$
f(d,n)=g(d,n-1)+g(d,n-2)+\cdots +g(d,0)
$$

我們也知道

$$
g(d,n)={\binom {d}{n+1}}
$$

 
因此，

$$
g(d,n-1)+g(d,n-2)+\cdots +g(d,0)={\binom {d}{n}}+{\binom {d}{n-1}}+\cdots +{\binom {d}{1}}
$$

最後，

$$
f(d,n)=\sum _{i=1}^{n}{\binom {d}{i}}
$$

我們知道 $f(d,n)$ 是所有最少實驗次數為 $d$ 的總樓層數中最大的一個，我們只要找到一個 $k$ 滿足以下條件即可：

$$
f(d,n)\geqslant k
$$

使用我們最後的公式，

$$
\sum _{i=1}^{n}{\binom {d}{i}}\geqslant k
$$

讓我們來試驗一下:

$$
f(t,3)=\sum _{i=1}^{3}{\binom {t}{i}}={\frac {t(t^{2}+5)}{6}}
$$

因此有 $f(8,3)=92,f(9,3)=129$

所以我們如果有三個雞蛋，可以保證在 9 次實驗之內找到臨界樓層。

### 其他方法

除了解析法之外，最常見的方法是遞歸法。

想像以下情況：n 個雞蛋，k 層樓，然後你把雞蛋在連續的 h 層中的第 i 層進行試驗。

如果雞蛋打破：這個問題會減少為 n-1 雞蛋和 i-1 個剩餘樓層的問題；如果不打破：這個問題會減少為 n 雞蛋和 h-i 個剩餘樓層的問題。
現在我們可以定義一個函數 $W(n,h)$ 計算所需的最小實驗次數：

我們可以編寫上述結果為確定找到下面的遞歸 $W(n,h)$ :

以下代碼由 C++ 編寫

$$
W(n,h)=1+min(max(W(n-1,i-1),W(n,h-i)))
$$

## 參見

* 遞歸
* 二項式係數
* 取整函數、高斯符號

 

## 參考資料

## 外部連結

1. 雙蛋問題的另一個遞歸程序（頁面存檔備份，存於網際網路檔案館）
2. 李永樂老師（頁面存檔備份，存於網際網路檔案館）
3. 相關動態規劃問題（頁面存檔備份，存於網際網路檔案館）