分蛋糕难题[z]

我们知道，两个人分蛋糕，让每个人都觉得他分得的一份不比其他人分得的少，称为无妒忌分法。方法是一个人先切成他认为相等的两份，另一个人先选。这样，第一个人分得他认为的1/2，第二个人分得他认为的至少1/2。
    现在的问题是，三个人分蛋糕，给出一种无妒忌的分法。


--------------------------------------------------------------------------------

参考答案：

    我们来考察与公平地分一块蛋糕这个简单得容易使人上当的问题有关的若干数学问题。所谓公平地分蛋糕的意思就是，如果有n个人分蛋糕，那么每个人都相信自己分得的一份至少为那块蛋糕的1／n。我们将继续研究几个相关的问题，它们涉及到该理论的较现代的内容。

    首先我们回忆一下前面所得到的结果。两个人分蛋糕时，使用历史悠久的"我分你选"算法，可以实现公平的分配。当3个人或更多的人分蛋糕时，有几种可能的分法。"修整"法是让参加分蛋糕的人依次把一份据称是分得公平的蛋糕缩小，其条件是如果没有其他人修理这份蛋糕，则最后一个修理者必须挑这份蛋糕。"依次成对"的方法则是让头两位参加分蛋糕的人公平地分蛋糕，而第三人则分别与这两人商量，以确保从已经分开的两块蛋糕中分别取得他或她认为至少有1／3的一份。而在"分割一赢得"方法中，参加分蛋糕的人力求一刀就把蛋糕切成两块，使大约一半的人觉得分到的一块是公平的而感到满意。然后对已经分开的两块蛋糕分别重复同样的方法，如此类推。

    这些算法全都是公平的，但这里还存在一个更复杂的问题。即使人人都相信他或她得到了公平的一份蛋糕，由于妒忌心的作怪，某些人仍然可能觉得自己受了委屈。例如，Tom，Dick和Harrp可能全都认为他们各自得到了至少1／3的蛋糕并对此感到满意，但Tom仍然可能觉得Dick的那一份比自己的大。Tom是一份是"公平"的，但他现在并不觉得很高兴。如果某种分法使任何人都不觉得其他某个人所得到的一份更大，那么这种分法就是"无妒忌的（cnvy-frcc）"。无妒忌分法肯定是公平的，但公平的分法不一定是无妒忌的。因此，找到一种无妒忌分配的算法比找到一种公平分配的算法更困难。

    两个人分蛋糕时的"你分我选"的方法显然是无妒忌算法，但上面提到的其他算法全都不是无妒忌算法。 60年代初，John Sclfridgc和John H.Conway首先发现了三个人分蛋糕时的一种无妒忌算法：

    第一步，Tom把蛋糕分成他认为具有等值的3块。

    第二步，Dick可以采取下列两个行动之一：
   （a）如果他认为其中两块或两块以上的蛋糕同为最大的一份，他可以什么也不做；
   （b）如果他认为有一块蛋糕最大，他可以对其进行修整，使之达到（a）所说的情况。把修整下来的零碎蛋糕放到一边。并称这些累积起来的零碎蛋糕为"剩余物"。

    第三步，Harry，Dick和Tom依次选一块蛋糕，也就是他们认为最大的一块或并列最大的一块。如果Dick在上面第二步中修整了一块蛋糕，那么他必须选修理过的蛋糕，除非Harry已经先选这一块蛋糕。

    到这一步时，蛋糕的一部分已经用一种无妒忌方式分完了。这样剩下的事情就是通过无妒忌方式把剩余蛋糕也分完。

    第四步，如果Dick在第二步什么也没有做，那么不再存在剩余蛋糕，因此蛋糕已被分完。否则，被修理过的那块蛋糕将由Dick或Harry选去。假定Dick得了这块蛋糕（如果是Harry得了这块蛋糕，那么从现在起在下面的分法中就把两个人的名字交换）。然后由Dick把剩余蛋糕分为他们认为是相等的三份。

    第五步，剩下的事情就是让Harry，Tom和Dick依次从剩余蛋糕中各取一份。由于Harry是第一个选，因此他没有 理由眼红。无论剩余蛋糕怎么分，Tom都不会妒忌Harry，因为Harry充其量也只能选到一份Tom认为是等于 1／3块的蛋糕。Tom也不会对 Dick眼红，因为他比Dick先选。Dick也没有理由抱怨，因为剩余蛋糕本来就是他自己分的。

    在这一点上，人人都被难住了30年。对于n个人分蛋糕的情形，是否存在一种无妒忌分法呢？ 1995年，纽约大学的Steven J.Brains以及联盟学院的 Alan D．Taylor发现了一种引人注目的适于任意多个人的无妒忌分法。这一方法很复杂，因此我不能在此介绍给读者们。读者可以参看他们的论文"一种无妒忌分蛋糕方法"（见《美国科学月刊》（American Mathmatical Monthly），102卷，1995年 1月），或参看Jack Robertson与 William Webb的精彩著作"分蛋糕算法"（马萨诸塞州拉蒂克市A.K．peters出版社1998年出版）。

    分蛋糕理论的最令人感兴趣的特点之一就是Robertson和Webb所谓的"分歧有利"论（serendipity of disagreemen）。乍看起来，当每个人对每一小块蛋糕值多少的看法都一致时，公平分配似乎是最容易的。毕竟，在这种情况下，大家对于某一份蛋糕的价值不可能有争议了。但实际上情况正好相反：一旦参与分蛋糕的人对蛋糕价值的看法出现分歧，那就更容易使所有人皆大欢喜。

    例如，假定Tom和Dick采用"你分我选"的方法来分一块蛋糕。Tom把蛋糕分成两份，并认为这两份蛋糕有相等的价值，即每份均为整块蛋糕的一半。如果Dick也同意Tom的估计，那就不能再做什么了。但是，假定 Dick认为这两种蛋糕的价值各为 3／5和 2／5。这样，出于某种利他主义的理由，他可以决定把他认为是较大的一份蛋糕的1／12奉送给Tom（他估计这一小块蛋糕的价值为整块蛋糕的1/20）。根据他自己的估价，他仍然还有整块蛋糕的3／5-1/20=11／20。实现此分法的一种办法是，Dick把他认为是较大的一份蛋分成他认为具有相等价值的12份。然后他请Tom从这12份中任选一份。

    无论Torn选了哪一份，Dick仍然认为他得到了整块蛋糕的1／20。另外，Tom有 12小块蛋糕可以选择，而且他认为这些蛋糕和起来就相当于整块蛋糕的一半。因此，按他的估计，其中至少有一份相当于整块蛋糕的1／24。他选择了这份蛋糕后，就自以为他得到蛋糕总共至少是整块蛋糕的13／24。这样Tom和Dick现在皆大欢喜：他们都认为自己得到了比公平的一份还要多的蛋糕。

    这个问题上的直觉并不是说关于价值的分歧必定会导致关于何为公平分配的分歧。如果由第三方来分蛋糕，然后坚持要Tom和Dick接受这些已预先确定的某一份蛋糕，那就可能出现这种情况。

    遗憾的是，并非所有任务都能够公平地分配，至少是在受到一些合情合理的限制的情况下不能公平分配。以洗碗为例，如果每个人都必须洗净或者烘干一个完整的碗碟，那么在极端的情况下是不可能做到公平分配的。设想有两个人来洗两个碗，其中一个是大碗，而另一个是小碗。两个人显然都愿意洗小碗而不肯洗大碗。因此，即使在一个所有争议都将通过协商来解决的某些分歧来看仍是不可避免的。