回複：A B 兩人分蛋糕 （難度適中）

兩人分蛋糕

問題：
A，B 兩人分m個相同大小的蛋糕。A切。B有n次“優先權”可以使用，0 <= n <= m。
當A分好一個蛋糕後，B可決定是否使用他的一個“優先權”來選擇其中的一塊。如果B用光其“優先權”或選擇pass， 則A會先選。

老規矩，A， B 都是和你一樣的聰明人，都要使自己利益最大化。

問雙方會如何運作。

分析：
設每塊蛋糕重1（1克，1斤，或1噸）。一個蛋糕分子重[0] 。
由於是A切。而B有n 次“優先權”可以使用，0 <= n <= m，則A有m - n 次“優先權”可以使用。顯然，A占據著主動和優勢。
問題可歸結為三點：1）A切蛋糕；2）B決定是否使用“優先權”；3）A和 B都要使自己利益最大化。1）和2）是手段，3）是目的。A如何切蛋糕和B是否使用“優先權”取決於當前的蛋糕數m和B還擁有的“優先權” 數 n。進一步分析將表明，如果B和A一樣的非常聰明，A可控製兩人的所得的蛋糕總量比。為此，我們先來定義幾個函數。

I. 四個遞歸函數。
定義1：如果有m塊蛋糕和B擁有n次“優先權”，A將第一塊蛋糕切成兩塊。小塊(m, n) 代表小塊的重量，大塊(m, n) 代表大塊的重量。

事實1：小塊(m, n) <= 大塊(m, n)。

事實2：小塊(m, n) + 大塊(m, n) = 1。

事實3：A將一塊蛋糕切成兩塊後，B如使用“優先權”，B得大塊，A得小塊；否則，A得大塊，B得小塊。

定義2：如果有m塊蛋糕和B擁有n次“優先權”，A(m, n) 代表A將所得的蛋糕總量，B(m, n) 代表B將所得的蛋糕總量。

事實4：A(m, n) + B(m, n) = m。

定理1：如果 0 < m,
(1) 大塊(m, 0) = 1 - [0] = 1；
(2) 小塊(m, 0) = [0] = 0。
(3) A(m, 0) = m - m*[0] = m；
(4) B(m, 0) = m*[0] = 0。
證明：
n = 0, 即B沒有 “優先權”。為使自己利益最大化，A將每塊蛋糕切下一個分子給B，自己貪婪地拿走幾乎整塊蛋糕。
證明畢。

推論1：大塊(0, 0) = 小塊(0, 0) = A(0, 0) = B(0, 0) = 0。
證明：
沒有蛋糕，誰都別獲利。
證明畢。

定理2：如果 0 < n < m，
(1)小塊(m, n) =（1 + B(m-1, n-1) - B(m-1, n)）/ 2；
(2) B(m, n) =（1 + B(m-1, n-1) + B(m-1, n)）/ 2。
證明：
當有m塊蛋糕和B擁有n次“優先權” 時，A將第一塊蛋糕切成大小兩塊。這樣，沒切的蛋糕還有m-1塊。因為0 < n ，B還擁有“優先權”可行使。因為 n < m，B可不行使而保留其“優先權”。因此，B可有兩種選擇：

一. 如果B行使“優先權”，根據事實3，則A 得小塊；B 得大塊。但是，B失去了一次 “優先權”。因此，B將所得的蛋糕總量B1應為大塊與當有m-1塊蛋糕和B擁有n-1次“優先權” 時，B將所得的蛋糕總量之和，即
B1 =大塊(m, n) + B(m-1, n-1) = 1 - 小塊(m, n) + B(m-1, n-1)，根據事實2；

二. 如果B不行使“優先權”，根據事實3，則A 得大塊；B 得小塊。但是，B仍有n次 “優先權”。因此，B將所得的蛋糕總量B2應為小塊與當有m-1塊蛋糕和B擁有n次“優先權” 時，B將所得的蛋糕總量之和，即
B2 =小塊(m, n) + B(m-1, n)

比較一.和二.兩種情況, 令B1 = B2，即
1 - 小塊(m, n) + B(m-1, n-1) = 小塊(m, n) + B(m-1, n)
小塊(m, n) =（1 + B(m-1, n-1) - B(m-1, n)）/ 2。

a) 當小塊(m, n) =（1 + B(m-1, n-1) - B(m-1, n)）/ 2時，
B1 = 1 - 小塊(m, n) + B(m-1, n-1)
= 1 -（1 + B(m-1, n-1) - B(m-1, n)）/ 2 + B(m-1, n-1)
=（1 + B(m-1, n-1) + B(m-1, n)）/ 2
B2 = 小塊(m, n) + B(m-1, n)
=（1 + B(m-1, n-1) - B(m-1, n)）/ 2 + B(m-1, n)
=（1 + B(m-1, n-1) + B(m-1, n)）/ 2
所以，B1 = B2，B是否行使其“優先權”都無所謂。

b) 當小塊(m, n) <（1 + B(m-1, n-1) - B(m-1, n)）/ 2時，
B1 = 1 - 小塊(m, n) + B(m-1, n-1)
> 1 - （1 + B(m-1, n-1) - B(m-1, n)）/ 2 + B(m-1, n-1)
=（1 + B(m-1, n-1) + B(m-1, n)）/ 2
B2 = 小塊(m, n) + B(m-1, n)
<（1 + B(m-1, n-1) - B(m-1, n)）/ 2 + B(m-1, n)
=（1 + B(m-1, n-1) + B(m-1, n)）/ 2
所以，B1 > B2。這意味著A將第一塊蛋糕切成兩塊的差距足夠懸殊，所以B值得對第一塊蛋糕行使“優先權”。這樣，B(m, n) = B1 > （1 + B(m-1, n-1) + B(m-1, n)）/ 2 。

c) 當小塊(m, n) >（1 + B(m-1, n-1) - B(m-1, n)）/ 2時，
B1 = 1 - 小塊(m, n) + B(m-1, n-1)
< 1 - （1 + B(m-1, n-1) - B(m-1, n)）/ 2 + B(m-1, n-1)
=（1 + B(m-1, n-1) + B(m-1, n)）/ 2
B2 = 小塊(m, n) + B(m-1, n)
>（1 + B(m-1, n-1) - B(m-1, n)）/ 2 + B(m-1, n)
=（1 + B(m-1, n-1) + B(m-1, n)）/ 2
所以，B1 < B2。這意味著A將第一塊蛋糕切成兩塊的差距不夠大，所以B不對第一塊蛋糕行使“優先權”。這樣，B(m, n) = B2 > （1 + B(m-1, n-1) + B(m-1, n)）/ 2 。
由於B如此之聰明，為使自己利益最大化，B要權衡兩種選擇所得多少來決定是否行使“優先權”。但A也同樣聰明地看到了這點，並且發現，隻有按情況a)，將蛋糕切成 小塊(m, n) =（1 + B(m-1, n-1) - B(m-1, n)）/ 2時，B將所得的蛋糕總量為最小，即B(m, n) =（1 + B(m-1, n-1) + B(m-1, n)）/ 2 。通過這番考慮，為使自己利益最大化，A就按情況a)毫不猶豫地向第一塊蛋糕下刀了。
證明畢。

如果A不夠聰明，將小塊切得太小，以至於按情況b) 小塊(m, n) <（1 + B(m-1, n-1) - B(m-1, n)）/ 2時，B對這塊蛋糕行使了“優先權”。從而導致B所得的蛋糕總量B(m, n) > （1 + B(m-1, n-1) + B(m-1, n)）/ 2 。

如果B不夠聰明，A有意或無意將小塊切得過大，以至於按情況c) 小塊(m, n) >（1 + B(m-1, n-1) - B(m-1, n)）/ 2時，但仍 小塊(m, n) <= 大塊(m, n)，B無知地對這塊蛋糕行使了“優先權”。導致B所得的蛋糕總量B(m, n) < （1 + B(m-1, n-1) + B(m-1, n)）/ 2 。

正是由於A和B同樣聰明，A必須按情況a)，將蛋糕切成 小塊(m, n) =（1 + B(m-1, n-1) - B(m-1, n)）/ 2才能將B之所得的蛋糕總量限製到最小；而B麵對A之所切，行使“優先權”與否所得相同。用Mr. James Bond 之言，“如果A，B和閣下一樣聰明，B 從頭到尾無需動用其優先權。”

推論2：如果 0 < n < m，
(1)大塊(m, n) =（1 + B(m-1, n) - B(m-1, n-1)）/ 2；
(2) A(m, n) =（1 + A(m-1, n-1) + A(m-1, n)）/ 2。
證明：
(1)大塊(m, n) = 1 - 小塊(m, n)--------------------------------------------事實2
= 1 -（1 + B(m-1, n-1) - B(m-1, n)）/ 2----------------------------------定理2(1)
= 1 + B(m-1, n) - B(m-1, n-1)）/ 2

(2) A(m, n) = m - B(m, n)--------------------------------------------------事實4
= m -（1 + B(m-1, n-1) + B(m-1, n)）/ 2----------------------------------定理2(2)
= m -（1 + （m - 1 - A(m-1, n-1)) + （m - 1 - A(m-1, n))）/ 2--------------事實4
=（1 + A(m-1, n-1) + A(m-1, n) )/ 2
證明畢。

定理2 和 推論2表明：在B對A切的第一塊蛋糕行使或不行使“優先權”以後的兩種情況下，A所得的平均值再加上半塊蛋糕就構成了A的所得； B所得的平均值再加上半塊蛋糕就構成了B的所得。
而A切的第一塊蛋糕得到大小兩塊的差值恰好是對這塊切完的蛋糕B不行使 “優先權” B之所得減去行使“優先權” B之所得的差。當然由事實2，也是A之所得的負差值。換言之，A是在估計到《蛋糕比當前少一塊，而B“優先權”數保持不變，B之所得》 與 《蛋糕比當前少一塊，而B“優先權”數也比當前少一次，B之所得》之差後，按照這個差來切第一塊蛋糕的。下麵的推論3證實了這一點。

推論3：如果 0 < n < m，大塊(m, n) -小塊(m, n) = B(m-1, n) - B(m-1, n-1) = A(m-1, n-1) - A(m-1, n)。
證明：
大塊(m, n) -小塊(m, n) = （1 + B(m-1, n) - B(m-1, n-1)）/ 2 -（1 + B(m-1, n-1) - B(m-1, n)）/ 2
----------------------------------------------------------------定理2(1) 和 推論2(1)
= B(m-1, n) - B(m-1, n-1)
= (1 - A(m-1, n)) - (1 - A(m-1, n-1))--------------------------事實2
= A(m-1, n-1) - A(m-1, n)
證明畢。

定理3：如果 0 < m,
(1) 大塊(m, m) = 1/2；
(2) 小塊(m, m) = 1/2。
(3) A(m, m) = m/2；
(4) B(m, m) = m/2。
證明：
0 < n = m，即B對A切的每塊蛋糕都有 “優先權”，為使自己利益最大化，A隻有將每塊蛋糕切成一半對一半。
證明畢。

定理1，定理2，定理3及其推論定義了A切的每塊蛋糕大小，A和B所能分到蛋糕總量對於當前的蛋糕數m和B還擁有的“優先權” 數n的遞歸函數。總結如下：

大塊(0, 0) = 小塊(0, 0) = A(0, 0) = B(0, 0) = 0。

如果 0 < m，
(1)
大塊(m, 0) = 1 - [0] = 1；
大塊(m, n) =（1 + B(m-1, n) - B(m-1, n-1)）/ 2，如果0 < n < m；
大塊(m, m) = 1/2。
(2)
小塊(m, 0) = [0] = 0。
小塊(m, n) =（1 + B(m-1, n-1) - B(m-1, n)）/ 2，如果0 < n < m；
小塊(m, m) = 1/2。
(3)
A(m, 0) = m - m*[0] = m；
A(m, n) =（1 + A(m-1, n-1) + A(m-1, n)）/ 2，如果0 < n < m；
A(m, m) = m/2。
(4)
B(m, 0) = m*[0] = 0；
B(m, n) =（1 + B(m-1, n-1) + B(m-1, n)）/ 2，如果0 < n < m；
B(m, m) = m/2。

下麵要證明這樣一個事實：麵對同樣數量的蛋糕， B擁有 “優先權” 數越多，所能分到蛋糕總量也越多。從而表明，A切的每塊蛋糕大小的遞歸函數，確實是小塊(m, n) < 大塊(m, n)。符合事實1。

I I. 小塊蛋糕確實是小塊。
引理1：如果 1 < m，B(m-1, 0) < B(m-1, 1)。
證明：
因為1 < m，B(m-1, 0) = 0，根據定理1(4)，所以隻要證明： B(m-1, 1) > 0。
對m施歸納法。
1) 當m = 2時，
B(m-1, 1) = B(1, 1) = 1/2 > 0，根據定理3(4)。
所以命題成立。

2) 假設m = k >= 2時，命題成立，即B(k-1, 1) > 0。
對於m = k + 1，
B(m-1, 1) = B(k, 1)
=（1 + B(k -1, 0) + B(k -1, 1)）/ 2------------------------------------1 < k，定理2(2)
=（1 + 0 + B(k -1, 1)）/ 2--------------------------------------------1 < k，定理1(4)
> 0----------------------------------------------------------------歸納假設
證明畢。

引理1表明B還擁有一次“優先權”所能分到蛋糕總量比B沒有“優先權”所能分到蛋糕總量多。更明確點，隻要B還擁有一次“優先權”，B就總能分到點蛋糕。

引理2：如果 1 < n < m，B(m-1, n-1) < B(m-1, n)
證明：
因為1 < n < m，m最小為3，此時n = 2。
對m施歸納法。
1) 當m = 3時，n = 2，
B(m-1, n-1) = B(2, 1)
=（1 + B(1, 0) + B(1, 1)）/ 2---------------------------------------定理2(2)
=（1 + 0 + B(1, 1)）/ 2--------------------------------------------定理1(4)
=（1 + 1/2）/ 2 ---------------------------------------------------定理3(4)
= 3/4

B(m-1, n) = B(2, 2)
= 2 / 2------------------------------------------------------------定理3(4)
= 1
所以命題成立。

2) 假設m = k >= 3時，命題成立,即B(k-1, n-1) < B(k-1, n)， 1 < n < k。
對於m = k + 1，1 < n < k + 1，

(a) 如果n = 2，
B(m-1, n-1) = B(k, 1)
=（1 + B(k -1, 0) + B(k -1, 1)）/ 2------------------------------------1 < k，定理2(2)
<（1 + B(k -1, 1) + B(k -1, 1)）/ 2------------------------------------k >= 3，引理1
<（1 + B(k -1, 1) + B(k -1, 2)）/ 2------------------------------------2 < k，歸納假設
= B(k, 2)----------------------------------------------------------------2 < k，定理2(2)
= B(m-1, n)

(b) 如果2 < n < k，
B(m-1, n-1) = B(k, n-1)
=（1 + B(k -1, n-2) + B(k -1, n-1)）/ 2--------------------------------1 < n-1 < k，定理2(2)
<（1 + B(k -1, n-1) + B(k -1, n-1)）/ 2--------------------------------1 < n-1 < k，歸納假設
<（1 + B(k -1, n-1) + B(k -1, n)）/ 2----------------------------------1 < n < k，歸納假設
= B(k, n)----------------------------------------------------------------1 < n < k，定理2(2)
= B(m-1, n)

(c) 如果n = k，
B(m-1, n-1) = B(k, k -1)
=（1 + B(k -1, k-2) + B(k -1, k-1)）/ 2--------------------------------1 < k-1 < k，定理2(2)
<（1 + B(k -1, k-1) + B(k -1, k-1)）/ 2--------------------------------1 < k-1 < k，歸納假設
=（1 + 2*B(k -1, k-1)）/ 2
=（1 + 2*(k-1)/ 2）/ 2 ------------------------------------------------0 < k-1，定理3(4)
= k/2
= B(k, k)----------------------------------------------------------------0 < k，定理3(4)
= B(m-1, n)
2) 證明畢。

證明畢。

引理2表明B擁有多於一次“優先權”時，B擁有 “優先權” 數越多，所能分到蛋糕總量也越多。

定理4：如果 0 < n < m，小塊(m, n) < 大塊(m, n)。
證明：因為
大塊(m, n) -小塊(m, n) = B(m-1, n) - B(m-1, n-1)-----------------------推論3
> 0 ----------------------------------------------------------------------引理1，引理2
所以，
小塊(m, n) < 大塊(m, n)
證明畢。

下麵幾個推論將推出關於B擁有 1次“優先權”和B擁有m-1次“優先權”兩種特殊情況下，A切的每塊蛋糕大小，A和B所能分到蛋糕總量對於當前的蛋糕數m的函數的直接數學表達式。

I I I. 兩種特殊情況下，遞歸函數的直接數學表達式。
推論4：如果 0 < m，
(1)小塊(m, 1) = 1 / 2^m；
(2) B(m, 1) = 1 - 1 / 2^m 。
證明：
對m施歸納法。
1) 當m = 1時，(1)根據定理3(2) ，小塊(1, 1) = 1/2；(2)根據定理3(4)，B(1, 1) = 1/2 = 1 - 1/2。

2) 假設m = k >= 1時，命題成立。即(1)小塊(k, 1) = 1/2^k；(2) B(k, 1) = 1 - 1/2^ k。
對於m = k + 1，
(1)小塊(m, 1) = 小塊(k + 1, 1)
=（1 + B(k , 0) - B(k , 1)）/ 2--------------------------------------------1 < k + 1，定理2(1)
=（1 + 0 - B(k , 1)）/ 2--------------------------------------------0 < k，定理1(4)
=（1 -（1 - 1/2^k））/ 2--------------------------------------------歸納假設(2)
= 1 / 2^(k+1)

(2) B(m, 1) = B(k + 1, 1)
=（1 + B(k , 0) + B(k , 1)）/ 2--------------------------------------------1 < k + 1，定理2(2)
=（1 + 0 + B(k , 1)）/ 2--------------------------------------------0 < k，定理1(4)
=（1 +（1 - 1/2^k））/ 2--------------------------------------------歸納假設(2)
=（2 - 1/2^k）/ 2
= 1 - 1/2^(k+1)
證明畢。

定理1表明在B沒有 “優先權”時，B幾乎什麽也得不到。而上邊推論4明示在B擁有 1次“優先權”情況下，B至少得半塊蛋糕，那是在隻有一塊蛋糕的時候。隨著蛋糕數量的增多，B從第一塊蛋糕所得蛋糕量成倍減少，但B所得蛋糕總量會增多。其最小上限是一塊，但永遠達不到一塊。

推論5：如果 0 < m，
(1) 大塊(m, 1) = 1 - 1 / 2^m；
(2) A(m, 1) = m - 1 + 1 / 2^m。
證明：
(1) 大塊(m, 1) = 1 -小塊(m, 1)--------------------------------------------事實2
= 1 - 1 / 2^m--------------------------------------------推論4(1)

(2) A(m, 1) = m - B(m, 1)--------------------------------------------事實4
= m - 1 + 1 / 2^m--------------------------------------------推論4(2)
證明畢。

哈哈！B(m, 1) = 大塊(m, 1) = 1 - 1 / 2^m。就是說，在B隻擁有 1次“優先權”情況下B所得蛋糕總量竟隻等於A從第一塊蛋糕所得蛋糕量。

推論6：如果 0 < m，
(1)小塊(m, m-1) = 1 / 2 - 1 / 2^m；
(2) B(m, m-1) = m / 2 - 1 / 2^m 。
證明：
對m施歸納法。
1) 當m = 1時，
(1)小塊(m, m-1) = 小塊(1, 0)
= 0--------------------------------------------定理1(2)
= 1 / 2 - 1 / 2^1
= 1 / 2 - 1 / 2^m

(2) B(m, m-1) = B(1, 0)
= 0 --------------------------------------------定理1(4)
= 1 / 2 - 1 / 2^1
= m / 2 - 1 / 2^m

2) 假設m = k >= 1時，命題成立。即
(1)小塊(k, k-1) = 1 / 2 - 1 / 2^k；
(2) B(k, k-1) = k / 2 - 1 / 2^k。
對於m = k + 1，
(1)小塊(m, m-1) = 小塊(k + 1, k)
=（1 + B(k , k-1) - B(k , k)）/ 2--------------------------------------------0 < k，定理2(1)
=（1 + (k / 2 - 1 / 2^k) - B(k , k)）/ 2--------------------------------------------歸納假設(2)
=（1 + (k / 2 - 1 / 2^k) - k / 2）/ 2--------------------------------------------0 < k，定理3(4)
=（1 - 1/2^k）/ 2
= 1 / 2 - 1/2^(k+1)
= 1 / 2 - 1/2^m

(2) B(m, m-1) = B(k + 1, k)
=（1 + B(k , k-1) + B(k , k)）/ 2--------------------------------------------0 < k，定理2(2)
=（1 + (k / 2 - 1 / 2^k) + B(k , k)）/ 2--------------------------------------------歸納假設(2)
=（1 + (k / 2 - 1 / 2^k) + k / 2）/ 2--------------------------------------------0 < k，定理3(4)
=（1 + k - 1/2^k）/ 2
= (k+1)/2 - 1/2^(k+1)
= m /2 - 1/2^m
證明畢。

定理3表明在B對A切的每塊蛋糕都有 “優先權”時，B可得蛋糕總量的一半。而上邊推論6明示在B擁有比蛋糕數量少1次“優先權”情況下，在隻有一塊蛋糕的時候，B什麽也得不到，因為B沒有“優先權”。隨著蛋糕數量的增多，B所得蛋糕量及比率也會增多，其最小上限是一半，但永遠達不到一半。

推論7：如果 0 < m，
(1) 大塊(m, m-1) = 1 / 2 + 1 / 2^m；
(2) A(m, m-1) = m / 2 + 1 / 2^m。
證明：
(1) 大塊(m, m-1) = 1 -小塊(m, m-1)--------------------------------------------事實2
= 1 - (1 / 2 - 1 / 2^m)--------------------------------------------推論6(1)
= 1 / 2 + 1 / 2^m

(2) A(m, m-1) = m - B(m, m-1)--------------------------------------------事實4
= m - (m / 2 - 1 / 2^m)--------------------------------------------推論6(2)
= m / 2 + 1 / 2^m
證明畢。

在0 <= n <= m的一般情況下，這四個函數的直接數學式還在探索中，Mr.jinjing 認為這是可能的。

所有跟帖： 

• 感謝Mr.James Bond 的問題！ 感謝Mr.jinjing 的答案！ -皆兄弟也- ♂ (0 bytes) () 07/14/2010 postreply 15:39:04

• mark mark。。。 先頂一下！！！！！！ -guest007- ♀ (0 bytes) () 07/15/2010 postreply 09:08:30

• 回複：回複：A B 兩人分蛋糕 （難度適中） -jinjing- ♀ (639 bytes) () 07/15/2010 postreply 19:40:58

• 我也想到您所提楊輝三角:C(m,n)=C(m-1,n-1)+C(m-1,n) -皆兄弟也- ♂ (99 bytes) () 07/15/2010 postreply 23:28:09

• 回複：我也想到您所提楊輝三角:C(m,n)=C(m-1,n-1)+C(m-1,n) -jinjing- ♀ (76 bytes) () 07/16/2010 postreply 07:54:31

• 用楊輝三角比較組合函數和分蛋糕函數 -皆兄弟也- ♂ (381 bytes) () 07/17/2010 postreply 10:17:38