注：题目选自《程序员面试逻辑题解析》
题目描述
杰里米（Jeremy）和玛丽（Marie）是两个喜欢蛋糕也喜欢数学的小孩，可能你也认识这样的小孩。于是，当大厨玛蒂娜（Martine）给他们准备了两块一模一样的长方形蛋糕后，杰里米便说服玛丽来玩一个游戏。
游戏的规则是这样的：杰里米先把一块蛋糕切成两份，这两份大小可能一样，也可能不一样。切完以后，玛丽决定是否要先选蛋糕。如果玛丽先选，她会选那份大的；如果让杰里米先选，玛丽可以预料到杰里米会选走那份大的。
随后，杰里米把另外一块蛋糕也切成两份（请注意，他可以把其中一份切得非常小）。如果之前是玛丽先选的，那么这次杰里米就可以拿走大的那份。如果之前是杰里米先选的，那么这次玛丽就可以拿走大的那份。
热身问题
假设每个小孩的目标是分得尽可能多的蛋糕，那么对于杰里米来说最好的策略是什么呢？
提示
在查看答案之前，用f和1-f来表示第一块蛋糕被切分后两部分的大小，其中f≥1/2。假设下面两种情况：
第一种，玛丽先选，拿走了f那块；
第二种，玛丽后选，拿走了1-f那块。依次分析这两种情况下的结果。
热身问题解答
根据提示，玛丽会这样推理：如果她拿了大小为f的那块，那么杰里米就几乎可以得到第二块蛋糕的全部（杰里米会切点儿蛋糕屑给玛丽，自己拿走几乎整块蛋糕）。这样，玛丽得到的份额是f，而杰里米得到的是（1-f）+1。如果她拿了小的那块（用1-f表示），那么对于杰里米来说最好是把第二块平分了，如此一来，玛丽得到的是（1-f）+1/2。根据这个推理，杰里米意识到对他来说最好的分法是使f=（1-f）+1/2，也就是2f=3/2，即f=3/4。这样，如果第一块蛋糕是玛丽先选，那么杰里米会得到第一块蛋糕的1/4和整个第二块蛋糕。如果第一块蛋糕是玛丽后选，那么杰里米会得到第一块蛋糕的3/4和第二块蛋糕的1/2。在这两种情况下，玛丽都能得到3/4的蛋糕，而杰里米能得到5/4。注意，如果杰里米在分第一块蛋糕时，大的那块小于3/4，那么玛丽只要后选，就能得到多于1/4的蛋糕，并且能得到第二块蛋糕的1/2，这样她能得到的蛋糕总量将多于3/4。对比之下，如果分第一块蛋糕时，大的那块大于3/4，那么玛丽只要先选，也能得到多于3/4的蛋糕。
我详细地分析了热身问题，因为一个星期后，会有一个更难的挑战。这次大厨玛蒂娜做了3块一模一样的长方形蛋糕，杰里米和玛丽都对它们垂涎欲滴。
扩展问题
他们制订了新规则。杰里米还是负责切蛋糕，但是玛丽有两次先选蛋糕的机会，而杰里米只有一次。也就是杰里米先切第一块蛋糕，玛丽决定她是否要先选。然后杰里米切第二块蛋糕，这次还是由玛丽决定是否先选。第三块蛋糕还是如此。唯一需要注意的是，玛丽至少要留给杰里米一次先选蛋糕的机会。
- 在新规则下，杰里米怎样做得到的蛋糕才能最多？他最多能得到多少？
- 假设有7块蛋糕，玛丽有6次先选蛋糕的机会，谁有优势？有多大优势？
- 假设总是让杰里米来切蛋糕，有没有办法可以确保两个小孩能得到一样多的蛋糕？
分析&解答
- 把第一块蛋糕分为f和1-f，其中f≥1/2。
- 玛丽先选，得到f。 那么剩下两个蛋糕，每人各一次选择机会。那么问题就转换为了热身问题。我们可以直接使用结果，即玛丽最多可以得到3/4。那么3块蛋糕则一共是f+3/4
2)玛丽后选，得到1-f。剩下两块蛋糕，玛丽两次选择机会。杰里米只能选择一半一半。 此时三块蛋糕玛丽一共得到1-f+1/2+1/2，即2-f。
因此杰里米最好的选择是f+3/4=2-f，得到f=5/8.
杰里米最多能拿到5/8+1/2+1/2=13/8
-
根据热身问题和扩展问题1，我们可以推出公式：
F(n) = f(n) + F(n-1) = 1 - f(n) + 1/2 * (n-1)
其中F(n)为有n块蛋糕时能拿到的总数，f(n)为有n块蛋糕时第一块切分的大小，f(n)≥1/2。
可以解得：f(n) = 1/2^n + 1/2。 F(n) = n/2 - 1/2^n。
因此，当有n块蛋糕，且总是由杰里米切蛋糕，而玛丽有n-1此选择机会的状况下。杰里米总是能有一点优势。 -
若总是杰里米切蛋糕，根据公式F(n) = n/2 - 1/2^n，若有n趋近于正无穷，才有F(n) = n/2。因此只有当玛蒂娜做出无穷块蛋糕时才能使两个孩子得到相同多的蛋糕。
当然，改变规则，每次都让玛丽来选择，也是另外一种答案。
网友评论