回复：A B 两人分蛋糕 （难度适中）

两人分蛋糕

问题：
A，B 两人分m个相同大小的蛋糕。A切。B有n次“优先权”可以使用，0 当A分好一个蛋糕后，B可决定是否使用他的一个“优先权”来选择其中的一块。如果B用光其“优先权”或选择pass， 则A会先选。

老规矩，A， B 都是和你一样的聪明人，都要使自己利益最大化。

问双方会如何运作。

分析：
设每块蛋糕重1（1克，1斤，或1吨）。一个蛋糕分子重[0] 。
由于是A切。而B有n 次“优先权”可以使用，0 问题可归结为三点：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)
事实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 (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 (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
一. 如果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) 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
所以，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 + 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 （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不够聪明，A有意或无意将小块切得过大，以至于按情况c) 小块(m, n) >（1 + B(m-1, n-1) - B(m-1, n)）/ 2时，但仍 小块(m, n)
正是由于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 (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 证明：
大块(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 (1) 大块(m, m) = 1/2；
(2) 小块(m, m) = 1/2。
(3) A(m, m) = m/2；
(4) B(m, m) = m/2。
证明：
0 证明毕。

定理1，定理2，定理3及其推论定义了A切的每块蛋糕大小，A和B所能分到蛋糕总量对于当前的蛋糕数m和B还拥有的“优先权” 数n的递归函数。总结如下：

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

如果 0 (1)
大块(m, 0) = 1 - [0] = 1；
大块(m, n) =（1 + B(m-1, n) - B(m-1, n-1)）/ 2，如果0 大块(m, m) = 1/2。
(2)
小块(m, 0) = [0] = 0。
小块(m, n) =（1 + B(m-1, n-1) - B(m-1, n)）/ 2，如果0 小块(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 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 B(m, m) = m/2。

下面要证明这样一个事实：面对同样数量的蛋糕， B拥有 “优先权” 数越多，所能分到蛋糕总量也越多。从而表明，A切的每块蛋糕大小的递归函数，确实是小块(m, n)
I I. 小块蛋糕确实是小块。
引理1：如果 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 =（1 + 0 + B(k -1, 1)）/ 2--------------------------------------------1 > 0----------------------------------------------------------------归纳假设
证明毕。

引理1表明B还拥有一次“优先权”所能分到蛋糕总量比B没有“优先权”所能分到蛋糕总量多。更明确点，只要B还拥有一次“优先权”，B就总能分到点蛋糕。

引理2：如果 1 证明：
因为1 对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) 对于m = k + 1，1
(a) 如果n = 2，
B(m-1, n-1) = B(k, 1)
=（1 + B(k -1, 0) + B(k -1, 1)）/ 2------------------------------------1 = 3，引理1
= B(k, 2)----------------------------------------------------------------2 = B(m-1, n)

(b) 如果2 B(m-1, n-1) = B(k, n-1)
=（1 + B(k -1, n-2) + B(k -1, n-1)）/ 2--------------------------------1 = B(k, n)----------------------------------------------------------------1 = 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 =（1 + 2*B(k -1, k-1)）/ 2
=（1 + 2*(k-1)/ 2）/ 2 ------------------------------------------------0 = k/2
= B(k, k)----------------------------------------------------------------0 = B(m-1, n)
2) 证明毕。

证明毕。

引理2表明B拥有多于一次“优先权”时，B拥有 “优先权” 数越多，所能分到蛋糕总量也越多。

定理4：如果 0 证明：因为
大块(m, n) -小块(m, n) = B(m-1, n) - B(m-1, n-1)-----------------------推论3
> 0 ----------------------------------------------------------------------引理1，引理2
所以，
小块(m, n) 证明毕。

下面几个推论将推出关于B拥有 1次“优先权”和B拥有m-1次“优先权”两种特殊情况下，A切的每块蛋糕大小，A和B所能分到蛋糕总量对于当前的蛋糕数m的函数的直接数学表达式。

I I I. 两种特殊情况下，递归函数的直接数学表达式。
推论4：如果 0 (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 =（1 + 0 - B(k , 1)）/ 2--------------------------------------------0 =（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 =（1 + 0 + B(k , 1)）/ 2--------------------------------------------0 =（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 (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 (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 =（1 + (k / 2 - 1 / 2^k) - B(k , k)）/ 2--------------------------------------------归纳假设(2)
=（1 + (k / 2 - 1 / 2^k) - k / 2）/ 2--------------------------------------------0 =（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 =（1 + (k / 2 - 1 / 2^k) + B(k , k)）/ 2--------------------------------------------归纳假设(2)
=（1 + (k / 2 - 1 / 2^k) + k / 2）/ 2--------------------------------------------0 =（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 (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