两个孩子分蛋糕问题

题目描述&＃xff1a;假如有两个孩子--Tom和Marry&＃xff0c;两个人都特别喜欢吃蛋糕&＃xff08;A和B&＃xff09;&＃xff0c;现在有两块相同大小的蛋糕。两个人都想吃到尽可能多的蛋糕&＃xff08;即比对方吃的蛋糕多&＃xff09;&＃xff0c;那么两个人就想做一个游戏&＃xff1a;如果由Tom来切蛋糕&＃xff0c;首先Tom将第一块蛋糕切成两份&＃xff08;两份可能大小相同&＃xff0c;可能不同&＃xff09;&＃xff0c;那么Marry来指定两个人的选择顺序&＃xff0c;规则如下&＃xff1a;如果第一次Marry先选&＃xff0c;那么&＃xff0c;第二次就一定是Tom先选&＃xff1b;同理如果第一次Tom先选&＃xff0c;第二次就一定是Marry先选&＃xff0c;如果两人先选&＃xff0c;肯定选择最大的那块。

问题&＃xff1a;Tom第一次如何切分蛋糕使得自己能吃到的蛋糕最多&＃xff1f;

问题分析&＃xff1a;由于每次都是Tom来切分蛋糕&＃xff0c;所以Tom可以根据Marry指定的选择顺序进行下一次切分。不失一般性&＃xff0c;我们假设每块蛋糕大小都为1&＃xff0c;假设第一次Tom将蛋糕A切分为大小和两块&＃xff0c;假设&＃xff0c;那么先选的人肯定选择。首先我们假设Marry先选&＃xff0c;那么她第一次选择&＃xff0c;而Tom只能选择&＃xff0c;第二次肯定是Tom先选&＃xff0c;Tom为了获取更多的蛋糕&＃xff0c;那么在第二次切的时候就可以分成两份&＃xff1a;一份为整个蛋糕B&＃xff0c;另一份为大小为0&＃xff0c;即两次Marry可以得到蛋糕&＃xff0c;Tom可以得到蛋糕。其次我们假设Marry让Tom先选&＃xff0c;那么Tom第一次肯定能够得到&＃xff0c;而Marry第一次得到&＃xff0c;这样第二次就自动是Marry先选&＃xff0c;Tom为了获得的蛋糕最多&＃xff0c;那么在第二次切分的时候只能是均分&＃xff0c;这样Tom和Marry各得到一半&＃xff0c;这样Tom得到的总的蛋糕为&＃xff0c;而Marry获得的蛋糕为&＃xff0c;两次为了都能使Tom获得最多的蛋糕&＃xff0c;我们可以令Marryl两次获得的蛋糕量相等&＃xff0c;即&＃xff1a;&＃xff0c;这样我们就可以求解&＃xff0c;即Tom在第一次将蛋糕切成3/4和1/4两份&＃xff0c;这样Tom两次能获得最多5/4的蛋糕&＃xff0c;而Marry只获得的蛋糕为3/4。

通过上面的分析我们知道在这个规则下切两块蛋糕时Tom能获得的最大蛋糕量&＃xff0c;那么问题来了&＃xff0c;如果给定3块同样大小的蛋糕&＃xff0c;每次都是Tom来切&＃xff0c;Marry指定先选的人&＃xff0c;3次必须有一次是Tom先选。

问题&＃xff1a;Tom第一次如何切分蛋糕使得自己能吃到最多的蛋糕&＃xff1f;

问题分析&＃xff1a;首先蛋糕的大小还是假设为1&＃xff0c;Tom第一次将蛋糕切分为&＃xff1a;和&＃xff0c;其中。下面直接讨论选择方式&＃xff1a;

1). 如果第一次Marry先选&＃xff1a;第一次Marry获得&＃xff0c;Tom获得&＃xff0c;那么还剩两次&＃xff0c;而且Tom有一次先选的机会&＃xff0c;根据上面分析的两块蛋糕的情况&＃xff0c;后面两次Tom最多可以5/4&＃xff0c;Marry获得3/4。则第一次Marry先选可以获得蛋糕量为&＃xff1a;&＃xff0c;而Tom可获得的蛋糕量为。

2). 如果第一次Tom先选&＃xff1a;第一次Marry获得&＃xff0c;Tom获得&＃xff0c;那么后面两次都是Marry先选&＃xff0c;Tom为了获得更多的蛋糕必定均匀切分剩余的两块蛋糕&＃xff0c;即后面两块蛋糕两人均可以获得1。则第一次Tom先选可以获得的蛋糕量为&＃xff1a;&＃xff0c;而Marry可获得的蛋糕量为&＃xff1a;。

为了使得Tom获得的蛋糕最多&＃xff0c;那么我们令Marry两种情况下获得的蛋糕量相同&＃xff0c;即&＃xff0c;求解可得&＃xff1a;。即Tom第一次将蛋糕切分为5/8和3/8两块&＃xff0c;这样Tom最多可以获得3块蛋糕中的13/8&＃xff0c;而Marry可以获得11/8。

写到这里&＃xff0c;可能很多人会想&＃xff1a;在游戏规则不变的情况下&＃xff0c;这个还能不能继续扩展呢&＃xff1f;答案是肯定的。

扩展&＃xff1a;假如现在有块大小完全相同的蛋糕&＃xff0c;每次还是由Tom来进行切分&＃xff0c;而Marry来决定两人的先后选择顺序&＃xff0c;其中Tom必定有一次先选的机会&＃xff0c;那么Tom第一次如何切分蛋糕能使得自己吃到最多的蛋糕呢&＃xff0c;获得的蛋糕量为多少&＃xff1f;

问题分析&＃xff1a;首先初始假设不变&＃xff1a;蛋糕的大小还是1&＃xff0c;Tom第一次将蛋糕切分为&＃xff1a;和&＃xff0c;其中。假设Tom能获得的蛋糕量为。

1). 如果第一次Marry先选&＃xff1a;第一次Marry获得&＃xff0c;Tom获得&＃xff0c;那么还剩次&＃xff0c;而且Tom有一次先选的机会&＃xff0c;根据上面分析易知此时&＃xff0c;后面次Tom最多可以&＃xff0c;Marry获得。则第一次Marry先选可以获得蛋糕量为&＃xff1a;&＃xff0c;而Tom可获得的蛋糕量为。

2). 如果第一次Tom先选&＃xff1a;第一次Marry获得&＃xff0c;Tom获得&＃xff0c;那么后面都是Marry先选&＃xff0c;Tom为了获得更多的蛋糕必定均匀切分剩余的两块蛋糕&＃xff0c;即后面两块蛋糕两人均可以获得。则第一次Tom先选可以获得的蛋糕量为&＃xff1a;&＃xff0c;而Marry可获得的蛋糕量为&＃xff1a;。

为了使得Tom获得的蛋糕最多&＃xff0c;那么我们可以令Marry两种情况下获得的蛋糕量相同&＃xff0c;即

求解可得&＃xff1a;

那么Tom获得的蛋糕量为&＃xff1a;

这样便可以求解的递推公式&＃xff1a;

很显然我们构造了一个等比数列&＃xff1a;公比为1/2&＃xff0c;首项为&＃xff0c;这样我们便可以得到&＃xff1a;

那么根据&＃xff0c;可以求解。

即Tom第一次将蛋糕切成和两块&＃xff0c;Tom可获得的最大蛋糕量为。

上面我们分析的都是Tom有且只有一次先选机会的结果&＃xff0c;如果Tom有多次先选结果会怎么样呢&＃xff1f;其实分析方法和上面是一样的&＃xff0c;只不过假如指定Tom有次先选时&＃xff0c;需要求解出Tom有次先选时能获得最大蛋糕量的结果。这里就不详细分析了。