這是之前在網路上看到的一個數學問題。題目很簡單：假設你有兩個完全相同的保齡球，現在你想要測試這種保齡球可以承受從多高的高度掉落而不會損壞。在你的身旁有一棟 100 層樓的高樓，你可以從任何一層樓，把保齡球丟下去，看看它會不會壞掉。同時，你也可以假設，如果保齡球在某一層樓丟下去會破損，則同樣的保齡球從更高的樓層丟下去也一定會破損。另一方面，如果從某一層樓丟下去不會破損，則從更低的樓層丟下去，也不會破損。另外，如果保齡球丟下去而破損後，就完全不能再用它來進行任何進一步的測試。除此之外，你沒辦法從任何其它的方式取得任何資訊。現在，要請你設計一個方法，可以用最少的次數，知道這種保齡球，最高可以承受從第幾層樓丟下去而不會破損？
很明顯的，如果只有一個保齡球的話，唯一的方法，就是從二樓開始丟。如果從二樓丟下去不破，就從三樓丟…依此類推，直到從 100 樓的樓頂（等於是 101 樓）為止。這樣的方法，最多需要丟 100 次。當然，現在有兩個保齡球，所以第二個保齡球應該可以有些用處。
從另一個角度思考，這個問題似乎可以用類似「二分搜尋法」來處理。例如，可以先從 50 樓丟下去，如果沒破，50 樓以下的就都不用再測試了。如果破了，50 樓以上的就不需要測試了。不幸的是，因為只有兩個保齡球，所以如果 50 樓丟下去破了，那就只能乖乖的從二樓一直測到 49 樓了。所以，這樣做的話，最多需要丟 50 次。相對的，如果第一次丟沒破，那下一次可以在 75 樓丟，依此類推。
從上面的結果來看，似乎一開始不應該從 50 樓開始丟，而應該選擇比較低的樓層才對。比如說，如果從 11 樓開始丟，如果破了，就從二樓試到十樓。如果沒破，下次就從 21 樓開始丟，破了就試 12 至 20 樓，沒破再從 31 樓開始，依此類推。這樣一來，最差的情形是丟到 91 樓沒破，但 101 樓時破了，所以再從 92 樓丟到 100 樓。也就是說，總共需要丟 19 次。
這樣已經比一開始要好得多了，但是有沒有辦法讓它變得更好呢？事實上，上面說的從 11 樓開始，完全是一個隨便決定的數字。也許可以計算出一個更好的數字，例如也許從 15 樓丟會更好。要計算出最好的數字是多少，可以計算如果一開始從 n + 1 樓開始，並每次提高 n 樓，最多會需要丟多少次？
如果總樓層數是 N，那最差的情形是要先丟 N / n 次，最後一次破掉，因此再加上 n - 1 次，即
N / n + n - 1
要最佳化這個值，可以把它微分，得到 -N / n2 + 1 = 0，即 n = sqrt(N)。所以，在 100 層樓的情形，剛好是一次跳 10 層樓最好。
不過，再回到前面二分搜尋法的想法，似乎不一定要每次跳一個固定的樓層數。由於每次丟一個球沒破，就等於多測試一次，所以，也許可以考慮每次跳的樓層數都減一。比如說，一開始從 15 樓丟，如果破了，就要再丟 2 ~ 14 樓，加起來共 14 次。所以，如果沒破的話，下次應該要在 15 + 13 = 28 樓丟。因為如果從 28 樓丟破了，再丟 16 ~ 27 樓，加起來也是 14 次。如果沒破，再從 28 + 12 = 40 樓丟，依此類推。
這樣丟的話，如果有 N 樓，那麼一開始丟的樓層，應該就是要選擇 1 + 2 + 3 + 4 + ... + n >= N 的樓層。1 + 2 + 3 + ... + n = n (n+1) / 2，所以
n (n + 1) / 2 >= N
-> n2 + n - 2N >= 0
-> n >= (-1 + sqrt(1 + 8N)) / 2
N = 100 的時候，n >= 13.65，也就是應該從 14+1 即 15 樓開始。這樣最多要丟 14 次。
有沒有可能做到更好呢？看起來似乎是不太可能，因為如果從高於 15 樓開始丟（例如 16 樓），那一開始就破掉的話，就要丟 2 ~ 15 樓，那就要丟 15 次，就超過目前最佳的 14 次了。另一方面，如果從低於 15 樓（例如 14 樓）開始丟，後面就無法「補上」而一定會超過 14 次。因此，這應該是最佳解了。
現在，兩個保齡球的問題，已經有了好的解答。那麼，如果有三個，或更多個保齡球時，又會如何呢？
很明顯的，如果夠多個保齡球，就可以直接使用二分搜尋法，最多需要丟 7 次（27 = 128 > 100）。這樣需要 7 個保齡球。但是，如果沒這麼多個保齡球，要怎麼辦呢？
假設現在有三個保齡球，可以注意到一點：假設從 n 樓開始丟，而它破了。這時，就剩下兩個保齡球，也就是說，對於剩下的樓層（n + 1 ~ 100 樓），這個問題等於是變成兩個保齡球的問題。如果它沒破，那麼，這個問題就會變成 n - 1 樓層的三個保齡球的問題。也就是說，如果設 F(m, N) 是 m 個保齡球在 N 層樓的情形下最多需要丟的次數，那麼，如果一開始從 n + 1 樓開始丟，則
F(m, N) = max( F(m, n - 1), F(m - 1, N - n) ) + 1
要找到「最佳解」，可以把 n 從 1 試到 N，找出最小的 F(m, N)。這個問題可以用 dynamic programming 來解。因為，已經知道 F(1, N) = N，而且 F(m, 1) = 1，所以對每個 F(m, N)，可以從 F(m, 2)、F(m, 3)、…一直計算到 F(m, N)。
舉個例子來說，假設想要計算 F(2, 2)，把 n 從 1 試到 2：
n = 1: F(2, 2) = max( F(2, 0), F(1, 1) ) + 1 = 2
n = 2: F(2, 2) = max( F(2, 1), F(1, 0) ) + 1 = 2
有了 F(2, 2)，就可以計算 F(2, 3)：
n = 1: F(2, 3) = max( F(2, 0), F(1, 2) ) + 1 = 3
n = 2: F(2, 3) = max( F(2, 1), F(1, 1) ) + 1 = 2
n = 3: F(2, 3) = max( F(2, 2), F(1, 0) ) + 1 = 3
所以可以知道 F(2, 3) = 2。接著，就可以計算 F(2, 4)：
n = 1: F(2, 4) = max( F(2, 0), F(1, 3) ) + 1 = 4
n = 2: F(2, 4) = max( F(2, 1), F(1, 2) ) + 1 = 3
n = 3: F(2, 4) = max( F(2, 2), F(1, 1) ) + 1 = 3
n = 4: F(2, 4) = max( F(2, 3), F(1, 0) ) + 1 = 3
也就是說 F(2, 4) = 3。
這可以很容易的寫一個程式來解。
不過，這樣來解這個問題，似乎還不是最理想的。透過 dynamic programming 方式，如果遇到 N 或 m 都非常大的情況，可能會需要相當長的時間才能計算出結果。
另一個方法，是反過來考慮：如果有 m 個保齡球，最多丟 n 次的情形下，可以「應付」最多到多少樓層呢？比如說，假設兩個保齡球的情形，最多丟 5 次的話，那最多可以有幾樓？這可以這樣來考慮：首先，第一次丟，必然是在 6 樓（即五樓的樓頂），因為如果 6 樓丟而破了，那接下來要丟 2 ~ 5 樓，加起來共 5 次。如果沒破的話，則從六樓開始，就是還有兩個球的情形下，還可以再丟 4 次。因此，可以把它寫成：
P(2, 5) = P(1, 4) + 1 + P(2, 4)
或是一般化來說：
P(m, n) = P(m - 1, n - 1) + 1 + P(m, n - 1)
這同樣是一個遞廻式，但是比 dynamic programming 的方式單純多了。由於已經知道 P(1, n) = n（即若只有一個球，丟 n 次的話，最多只能應付到 n 樓的情形），所以
P(2, n) = n - 1 + 1 + P(2, n - 1)
-> P(2, n) - P(2, n-1) = n
所以 P(2, n) = n(n+1)/2，也就是前面討論過的結果。
同理，可以推導 P(3, n):
P(3, n) = P(2, n - 1) + 1 + P(3, n - 1)
-> P(3, n) - P(3, n-1) = n(n-1)/2 + 1
-> P(3, n) = (n-1)n(n+1)/6 + n
以 100 層樓的問題來說，因為 P(3, 8) = 92 而 P(3, 9) = 129，因此可以知道三個球的時候最多要丟 9 次。
推廣下去，可以得到
P(m, n) = C(n + 1, m) + C(n + 1, m - 2) + C(n + 1, m - 4) + ... - 1
C(m, n) 是組合數，即 C(m, n) = m!/n!(m-n)!
從這個結果，也可以推導出一些結論，例如：
對所有 m >= n，P(m, n) = 2n - 1
證明如下：
使用數學歸納法。設 m >= n = 1，則 P(m, n) = P(m, 1) = 21 - 1 成立。
現在設 m >= n = k 時 P(m, n) = P(k, k) = 2k - 1 成立，則
m >= n = k + 1 時，P(m, n) = P(k + 1, k + 1) = P(k, k) + 1 + P(k + 1, k) = 2k - 1 + 1 + 2k - 1 = 2k+1 - 1 也成立。
因此 m >= n 時，P(m, n) = 2n - 1。
這個結果其實是十分合理的，因為當使用二分搜尋法時，進行 n 次比較，最多只能處理到 2n - 1 筆資料。在這個問題中，當保齡球數目和需要丟的次數一樣或更多時（球更多顯然不會有什麼幫助），理論上可以直接使用二分搜尋法，因此最多只可以應付 2n - 1 樓層。
平行化版本
在上面的問題中，我們考慮的是一次丟一個球。但是，如果同時可以丟好幾個球，那情形就會不太一樣了。比如說，假設有兩個人，和兩個保齡球，樓層數是兩層。按照正常的丟法，需要丟兩次：2 樓和 3 樓各丟一次，順序倒沒什麼差別。但是，有兩個人的時候，其實可以同時在 2 樓和 3 樓丟。如果這樣算是「一次」的話，那麼就有可能需要丟的次數可以減少。某個角度來說，這算是原問題的「平行化」。
可以同時丟兩個球，能帶來多大幫助呢？除了最明顯的兩層樓的版本之外，其它樓層數也是會有幫助的。例如，五層樓的情形，如果兩個球可以同時丟的話，最多只需要丟兩次：
一開始，丟 2 和 4 樓。
如果 2 樓破了（當然 4 樓也會破），則表示從 2 樓丟就會破。
如果 2 樓沒破，但 4 樓破了，就從 3 樓丟（只剩一顆球）。
如果 2 樓和 4 樓都沒破，則同時丟 5 和 6 樓。
利用前面的方法，當有 m 個球可以同時丟的時候，可以得到：
R(m, 1) = m
也就是只丟一次時，m 個球可以應付 m 層樓（即每層樓都同時丟）。
可以丟兩次時，可以這樣看：
2 樓一定要丟，因為可能每個球都會破。
如果 2 樓沒破，但其它都破了，就剩一個球，因此可以「空一樓」，即 3 樓可以先不丟，下一個球應該從 4 樓丟。
如果 4 樓也沒破，但其它都破了，那會剩兩個球，因此可以空 R(2, 1) 樓。
依此類推…
所以可以得到
R(m, 2) = 1 + R(1, 1) + 1 + R(2, 1) + 1 + R(3, 1) + 1 + ... + R(m, 1)
例如
R(2, 2) = 1 + R(1, 1) + 1 + R(2, 1) = 1 + 1 + 1 + 2 = 5
一般化的話，就是
R(m, n) = 1 + R(1, n - 1) + 1 + R(2, n - 1) + 1 + R(3, n - 1) + 1 + ... + R(m, n - 1)
-> R(m, n) = R(1, n - 1) + R(2, n - 1) + ... + R(m, n - 1) + m
這裡可以看到一件很有意思的事情：
R(m - 1, n) = R(1, n - 1) + R(2, n - 1) + ... + R(m -1, n - 1) + m - 1
所以
R(m, n) = R(m - 1, n) + R(m, n - 1) + 1
和「非平行版」的遞廻式類似，但是不太一樣。初始條件當然也不太一樣。
由於 R(1, n) = n 這點仍不變，因此：
R(2, n) = R(1, n) + R(2, n - 1) + 1
-> R(2, n) - R(2, n - 1) = n + 1
-> R(2, n) = (n + 1)(n + 2)/2 - 1
而
R(3, n) = R(2, n) + R(3, n - 1) + 1
-> R(3, n) - R(3, n - 1) = (n + 1)(n + 2)/2 - 1 + 1 = (n + 1)(n + 2)/2
-> R(3, n) = (n + 1)(n + 2)(n + 3)/6 - 1
推導下去可以得到
R(m, n) = C(m + n, m) - 1
例如，三個球可以同時丟的話，100 層樓需要丟幾次？
因為 R(3, 6) = 83，而 R(3, 7) = 119，因此三個球可以同時丟的時候，最多只需要丟 7 次。