三人分蛋糕问题

小时候我们常有这样的经历，如果你有一块蛋糕要和另一个小伙伴分享时，大人们会说你们可以这样分：你们其中的一个先把这块蛋糕分成两块，然后让另一个先挑。

小时候的我就觉得这个方法十分巧妙，因为分蛋糕的那个人会想：如果我分的不一样大，那么对方先挑就会拿走那块大的，所以我只有尽量使两块差不多大，这样他拿哪块我都不会吃亏。这个方法的巧妙之处就在于自动达到了“公平”的效果。

你是否想过，如果三个人分蛋糕的话，有没有类似方法能够达到同样的效果呢？为此，我们首先要确定衡量一个方法好不好的标准。对这个分蛋糕问题，我们有一个基本标准叫作“公平”：每个人都感觉自己分到了至少平均数以上的那份蛋糕。如果只是要达到这个标准的话，那么有一个相当简单的方法：

第一个人先把蛋糕切出一块他认为的1/3，然后传给第二个人。第二个人如果觉得这块蛋糕比他心目中的1/3要大一点，那么他就再切掉一点，以达到他心目中的1/3；如果他觉得这块蛋糕已经比他心目中的1/3小了，那么他就直接给第三个人。第三个人做了同样的抉择之后，我们就把这块蛋糕给最后一个切过蛋糕的人。如果第二、第三个人都没有切过蛋糕，那么这块蛋糕就给第一个人。

之后的问题就是让两个人分剩下的那份蛋糕，这个方法前面已经说过了。这个分蛋糕的方法确实十分简单，其本质上就是要比较每个人心目中的“1/3”，找出谁心中的“1/3”是最小的。这个人就可以拿走最小的“1/3”，剩下的两个人肯定会觉得从剩下的2/3再取一半，总是比他们心中的“1/3”多的。这个方法也很容易推广到许多人的情况，只要重复这个切蛋糕—传蛋糕的过程就可以了。

但是我们的分蛋糕问题还没有解决。在前面三人分蛋糕的过程中，虽然我们达到了“公平”标准，却不能避免人们产生“嫉妒”心理，也就是英文当中的“Envy”这个词。此处“Envy”的意思是：如果某个人感觉自己拿到的蛋糕比别人的少（虽然大于等于他心中的1/3），那么他就会产生“嫉妒”心理。

比如，当一个人先拿到自己心目中的1/3之后，他就只能眼巴巴看着剩下的两个人来分了。等剩下两个人分完，他观察自己手里的这块和另外某一个人拿到的那块，发现自己的那块比另一个人的小很多。他想：早知道你接下来能分到这么大一块，那我之前就不拿我这手里的这“1/3”了。这就是人性之中的黑暗面，但又是天性使然，难以避免的一面。

古人云：“不患寡，而患不均也”，意思是：大家穷不要紧，但是我见不得别人比我富（我的歪解，不要用在语文考试中）。一个分蛋糕的好方法是既能做到“公平”，又能免于“嫉妒”，每个人都不会觉得比别人所得的少，之前的两人分蛋糕方法就能达到这两个标准。

英文把第二个标准叫“Envy Free”（无嫉妒，不是“免费嫉妒”），所以就有人继续研究，有没有一种既公平，又“Envy Free”的分蛋糕方法，这个问题就要比仅仅达到公平标准难很多。但确实有人找到了对三人分蛋糕问题既“公平”且无嫉妒的方法，这种方法还不止一种。

先说其中一种。1980年，有一个叫沃尔特·斯多奎斯特的数学家提出了一种令人拍案叫绝的方法，俗称“走刀法”。假设这块蛋糕是一个长条形的，每个部分都是均匀的，邀请一个裁判和三个参与分蛋糕的人，并让他们手里各拿着一把刀。这个刀当然不是用来互砍的，只是用来切蛋糕的。

裁判先把刀放在蛋糕的一头，比如最左边，但不要切下去，而缓慢匀速地向右移动。三个分蛋糕的人站在裁判右边，始终看着裁判手中悬浮的刀的位置，评估在这右半部分蛋糕上，哪个位置是自己心目中的一半蛋糕的位置，然后保持自己手里的刀在这个位置上。

所以情形就是一个裁判站在左边持刀向右缓慢移动，另外三个人站在他的右边，也拿着各自的刀，同时把刀指向裁判的刀的右半部分的蛋糕的一半的位置。另外三个人也会缓慢地向右移动，因为裁判向右移动的话，另外三个人评估的这个一半的位置肯定也会缓慢地向右移动。

与此同时，这三个分蛋糕的人还要始终评估在裁判刀的左侧的那部分蛋糕，如果这部分蛋糕达到他们心目中的1/3，他就要高喊一声“切”。当有人喊出“切”以后，所有人的刀就不能再移动了。此时裁判把自己的刀切下去，而右边三个分蛋糕者，要看谁的刀处于另外两把刀之间的位置，然后把中间的刀切下去，不管这把刀是谁拿着的，如此操作之后，这个蛋糕就被分成了三部分。

接下来该分蛋糕了。最左面那块，是裁判的刀切出的蛋糕，分给那个喊“切”的人。因为喊“切”的人认为那个部分已经达到了他心目中的1/3，所以他拿这块是没有大问题的。然后就看剩下两个人的刀的位置。谁的刀靠左，就拿中间这块。谁的刀靠右，就拿最右边那块。现在看看这个方法为什么“公平”且“无嫉妒”。

首先，每个人“走刀”时的最佳逻辑策略如下。

走刀策略：每个人的刀总是处于可以平分右半边蛋糕的位置。

喊“切”策略：当你认为最左边的蛋糕和你不喊“停”时可以得到的蛋糕一样大时，就需要喊“切”（若不“喊”，则左边这块可能被别人“抢”走）。具体来说，当你的刀在最左边时，在“左边=中间”时喊“切”；当你的刀在最右边时，在“左边=右边”时喊“切”；当你的刀在中间时，当“左边=中间=右边”时喊“切”。

对没有喊“切”的两人来说，他们认为裁判切出的蛋糕达不到他们心目中的1/3，所以他们绝不会嫉妒那个喊“切”的人。又因为右边两块切下的位置是在两人的刀中间，所以两人都会觉得至少得到了自己满意的那部分。

而对于喊“切”的人，若他的刀在最左边，则他认为自己拿到的蛋糕和中间那块蛋糕是一样大的，甚至比第三个人还多。刀若在最右边，则他认为自己拿到的蛋糕和右边那块蛋糕是一样大的，也比第三个人拿得多。若在中间，则他会认为大家拿的蛋糕是一样多的。

以上过程确实精妙，而且蛋糕只用切两刀就完成了分割。但这个方法的缺点也很明显，就是没有可操作性。它需要假设这个蛋糕是一块连续且均匀的物体，且每个人对刀的控制是即时且非常精确的，每个人也需要知道走刀的最佳逻辑策略。所以这种方法更像是一个计算机算法，而不是一种可以实际操作的方法。那有没有一种更具实操性，可以按轮次执行来解决三人分蛋糕问题的方法呢？

还真有。早在1960年，一个叫约翰·塞尔弗里奇的数学家就提出了一个解决方法，他把他的方法告诉了一个同行兼好友理查德·盖伊，然后盖伊又把这个方法告诉了其他许多人。但是当时他们显然都没有把这个发现当回事，所以也从未正式发表过。因而这一发现，只是在坊间流传了一段时间，并未引起较大轰动。可能塞尔弗里奇认为这只是一个雕虫小技，不值一提。也确实，相对于这个数学家在其他方面的成就，这个分蛋糕问题显得太微不足道了！

直到1993年，另外一位著名数学家约翰·康威又独立地发现了这个解法，“生命游戏”就是他发明的。巧合的是，两位发现这个分蛋糕方法的数学家名字都叫约翰，而且他们都没有正式发表这个方法，只是在私底下非正式地交流了一下。但此后的很多科普和专业文章都提到了这个方法，最终让这个方法为大家所知，所以现在这个方法就用两位数学家的姓氏来命名，称为“塞尔弗里奇 - 康威分割步骤”。

为方便大家理解，我将借用一个故事来介绍这个方法。庙里有三个和尚：一个胖和尚，一个高和尚和一个小和尚，我们让这三个和尚来分蛋糕。

话说这三个和尚平日里都很自私，谁都不愿意多付出一点，导致某日庙里的水极度短缺，饭也没法烧，三人都饥肠辘辘。这一天忽然有个行脚僧来访，欲借宿一宿。这个行脚僧说：“看三位都饿了很多天了，我这里有一块蛋糕，可供三位分着吃。”

但是对于这个蛋糕该怎么分，三个人又开始激烈地争论起来，谁也不愿意吃亏，也见不得别人比自己多分一点。行脚僧说：“别吵了，我有一个办法让大家都满意。”

三人将信将疑，但没有其他办法，就让行脚僧说说看，这个行脚僧说，我的方法是这样的：

小和尚你先过来，把这块蛋糕分成三块，但是记住你将是最后一个选的，所以请你把蛋糕分成你认为最均匀的三块，这样你到时候拿哪块都不吃亏。小和尚虽然认为这个差事看上去并不太好，但还是努力把这个蛋糕分成了自己认为公平的三块。

然后行脚僧对胖和尚说：“如果让你第一个选，你会选哪块？”胖和尚暗自开心：这个问题好，原来是我先挑啊。他马上选了他认为的最大的那块。行脚僧接着说：“慢着，你还不能拿这块。现在请你在剩下的两块中再选一块，你觉得比较大的。”胖和尚也不知道这个行脚僧葫芦里卖的什么药，只好再选了一块次大的。然后胖和尚说：“现在我可以拿蛋糕了吗？”

“不行”，行脚僧说：“刚才你已经选了最大的和一块次大的，那么现在请你从你选的最大的那块当中，切一点下来，放到一边。你的目标是使这块最大的和那块次大的看上去大小是一样的。”

胖和尚一听有点泄气了，原来前面是在试探我啊。但是没办法，现在行脚僧是权威，所以就小心翼翼地从他认为最大的那块当中切了一小块出来放在一边。此时他觉得最大的和次大的两块蛋糕在他心目当中已经是一样大的了。

行脚僧说：“好了，现在轮到高和尚了，你可以从小和尚分的这三块里面随便挑一块，当然其中一块是被胖和尚切掉一点的。如果你喜欢这块被切过的蛋糕的话，你也还是可以选它。”

高和尚一听太开心了：“原来是我先选啊！”高和尚看了三块蛋糕之后，觉得胖和尚次选的那块才是他的最爱，所以他选了那块。这时候行脚僧说：“胖和尚，现在因为高和尚拿了他想要的那块了，而且他没有拿你切过的那块，所以你现在必须拿你刚才切过的这块。你刚才也认为你切过的这块比最后一块要好一点，所以你拿这一块应该没有什么不满意的。”

胖和尚一想确实如此，所以就拿了自己切过的这一块。最后行脚僧说：“小和尚你可以拿剩下的这块。这块是当初你自己分的，而且你认为三块是一样大的，所以你应该也没什么不满意。”小和尚就拿了最后一块。

但是小和尚说：“不对，这里还有胖和尚切下的一小块没有分。这块蛋糕虽然小，但是浪费也不好。”行脚僧胸有成竹地说：“对，那我们现在就来分这剩下的一小块。有请高和尚，你过来，把这一小块分成你认为公平的三块吧。”于是高和尚小心地分了三块。

然后行脚僧说：“这次请胖和尚先选一块。”胖和尚就从这三块中选了自己认为最满意的一块。然后行脚僧说：“再请小和尚来选一块。”小和尚也挑了一块自己喜欢的，最后高和尚拿走了剩下的最后一小块。行脚僧此时说：“好了，蛋糕都分完了，三位满意吗？”

三个和尚开始在心里算计起来。胖和尚是这么想的：第一轮我拿到了自己切过的那一块。这块我觉得跟高和尚拿走的那块相比是一样的，要比小和尚的那块好。第二轮呢，又是我第一个选，所以我选的这块肯定要比高和尚和小和尚的好，所以我当然没什么不满意的。

高和尚是怎么算计的呢？他想：第一轮我是第一个选的，所以我觉得我这块比另外两个和尚拿到的都好。第二轮这三块是我分的，对我来说这三块都一样，我也无所谓，所以两次加起来呢，我应该比另外两个和尚好，这个结果挺好。

小和尚是这样算计的，他想：第一轮我拿的这块是自己切的。这块对我来说与高和尚的那块是一样好的，但是比胖和尚切过后拿走的那块要好一点。第二轮我比高和尚先选，所以我总体来说肯定比高和尚拿到的要好一点。如果我跟胖和尚比，胖和尚只是拿了我当初切的1/3，切掉的那一小块又被我和高和尚各分走一点，所以他总体拿的还不如我第一轮拿的多，我比他划算太多了，所以这次分蛋糕对我来说是很划算的。

就这样，一个神奇的局面出来了。三个和尚都觉得自己分得的蛋糕比别人只多不少，所以三个人都满意，行脚僧圆满完成任务！

上述分蛋糕的故事就是根据塞尔弗里奇 - 康威分割步骤改编的。要说明的一点是，这个故事并没有覆盖到所有可能的选择，但已经足够说明整个步骤的框架。关于具体细节，各位可以自行思考或上网查找。这个步骤的最神奇之处，就是能实现“无嫉妒”的目标，即最后分析时，每个人都会打小算盘算计，但是怎么算都会觉得自己分得的蛋糕是大于等于其他人的。

现在你肯定在想这个方法能否推广到三人以上的情况呢？这是一个非常困难的问题。因为这个问题分为两种情形：在上面三个和尚切蛋糕的过程当中，每个人分得的蛋糕是一大块和一小块，是断开的。但在走刀程序中，蛋糕的切割结果是完整的，每个人都可拿到一块完整的蛋糕。可以想象，要使最终的切割结果是完整的要比断开的困难得多。如果要得到完整的蛋糕，就不能做调整，必须一次切出大家都满意的结果。

在20世纪90年代，人们发现的所有的四人或四人以上的分蛋糕方法，都可能需要无穷多个切割步骤，或者更准确地说是“问询步骤”。所谓“问询步骤”，就是说去问某一个分蛋糕的人，哪个位置是你需要的，或哪块蛋糕是最好的。对于这个分蛋糕问题，“问询”是最主要的操作步骤，因为并不是每次问询都会产生一次切割。而且，如果需要得到连续的蛋糕，那么n个人肯定最多只能切n-1刀，所以能真正评估某个切割方法好坏的标准就是“问询”的次数。

直到20世纪90年代末，人们虽然发现了很多分割方法，但是这些方法都可能需要无穷多个问询步骤。在2000年到2010年这十年间，人们证明了：对不要求蛋糕连续的情况，这个问询步骤的下限，即最少次数是 O （n ² ），其中n为参与分割的人数，意即与人数的平方成正比例关系，但这只是下限。

而要求最终结果是不断开的蛋糕的话，这个下限是无穷大，即证明了没有一个只用有限问询次数的方法来切出大家都满意的连续的蛋糕。可以看到“走刀法”从本质上讲，也是一种需要无限问询次数的方法，因为每一小段刀的移动都等价于产生了无数次问询。

但是在很长一段时间里，人们不知道，在不要求结果是连续的蛋糕的情况下，有没有一个有限的切割步骤？虽然我们知道它有一个下限，但是这个上限还是不为人所知的。这个问题直到2016年才取得突破，两位澳大利亚的研究者证明，对四人或四人以上不要求切割结果完整的情形问题，具有一个有限的上限，这个上限数字十分神奇：

这个数字当然是大得可怕，哪怕是n=2，一般计算器都无法显示其结果。但不管怎样，这总算告诉我们这个问题是有一个有限的答案的，这是非常重大的突破。也许以后有人能证明出更小的上限或者更大的下限。因为目前来看，这个上限要比这个它的下限 O (n ² )大很多。

最后值得一提的是，这个分蛋糕问题还有很多有趣的变体，比如蛋糕的形状不是一个抽象的直线形，而是一个二维的圆形，就有更简便的走刀法。另外如果蛋糕部分分完，允许剩下一些部分的话，那么对任何人数来说，都有一个相对简单且有限问询次数的分割方法。但这种情况的缺点就在于，随着人数增多，未分完的蛋糕的比例也越来越大，虽然可以重复这个步骤，继续分未分完的蛋糕，但总有不能分完的蛋糕。

相信你此时也在思考如何扩展塞尔弗里奇 - 康威分割步骤到四个人呢？好消息是已经知道存在有限的步骤能完成分割；坏消息是步骤次数上限为 。我要警告你，这会是一个很难的问题，否则不会拖到现在都没有人找到！当然，如果你找到了，这将是一个重大的发现。但请你注意，你要确保自己的方法是“无嫉妒”的，即任何两人之间进行比较，每个人都觉得自己只多不少，这一点被很多人忽略。

思考题

大老李陪你一起“玩”

1.如果蛋糕是圆形的，可以采用怎样的“走刀法”，完成三人分蛋糕？

2.你觉得在生活中的哪些地方能用上“三人分蛋糕”策略呢？ uIfXxvBmMakE+cr52v19dRI/p7hicx3DAETPT60CEy5b+1Jl3blFOZk5Rz5onOIw