三个极度嫉妒的人分一个蛋糕，何种策略能让三人都觉得公平？ 第1页

• 若想知道「先切的人最后选」错在哪里，请先看本答案最后补充，确保自己理解问题的难点。
  
• 请勿因为配图，想当然地认为本答案「假设了矩形蛋糕」。本答案中的算法没有做这个假设。
  

====正文====

这是著名的 cake cutting 问题。

所谓「三人都满意」，数学上有多种可能的涵义，常用的两种是：

• 公平：三人都认为自己的一份不少于 1/3
  
• 无怨：三人都不觉得别人拿得比自己多 Envy-free
  

无怨一定公平，但是公平不一定无怨。

daniel 的答案，上面这两个条件都不满足，只会引起自责，不算满意／公平，是错的。

两人的情况很简单：我切，你选。

三人的情况曾经长时间没有解，40 年代找到公平程序，80 年代发表无怨程序。

多人的无怨切法还没有完满解决。

daniel 的答案是一种「走刀程序 moving-knife procedure」。真正达到「无怨」的 走刀程序 见

，80 年代由 Stromquist 提出。

需要一个裁判，从左向右走刀，三人拿着刀站在裁判右边，保持在平分右边蛋糕的位置（按各自标准）。一旦三人中有一个喊「切」，此人获得裁判左边的蛋糕。然后三人中位于中间位置的那位（B）把刀切下。没蛋糕的两位中，离裁判近的那位获得中间那块，远的那位获得右边那块。

容易证明，三人都认为自己的那份最大。

走刀程序的坏处是连续，假设了两人同时叫停的概率为零，假设了蛋糕无限可分，现实中不好操作。

一个离散程序是

60 年代由 Selfridge 提出，90 年代由 Conway 独立提出并发表。

1. A 按照自己的标准把蛋糕切三块
   
2. 如果 B 认为最大的两块一样大，那么把 C，B，A 的顺序选蛋糕，结束。
3. 如果 B 认为其中一块 M 最大，他就从 M 削去一小块 R，使之与第二大的那块一样大，把 R 放在一边。
   
4. C 先选。如果 C 没有选 M，那么 B 必须选 M，否则一切正常，A 拿最后一块。
   
5. B 和 C 中没拿 M 的那位，把 R 分成三份，让 B 和 C 中拿了 M 的那位先挑一份，然后 A 选一份，最后一份留给自己。结束。

可以证明，三人都认为自己的那一份最大，证明见维基页面。

四人无怨分割的走刀程序，1997 年由 Brams, Taylor and Zwicker 提出。多人无怨分割的离散程序，1995 年由 Brams and Taylor 提出，但是需要切的次数可能无上界，因此应该说尚未完满解决。

以上是「无怨」的切法。「公平」的切法要简单一些，这里有一个很通俗的介绍：

，波兰数学家们做了很大贡献。针对 n 人的一般公平程序如下（Banach and Knaster 提出）：

1. 先排好顺序。
   
2. 第一个人切出他认为的 1/n。
   
3. 按顺序，每个人都判断一下，这一份是不是太大。是的话就削掉一点并进原来的蛋糕，不是的话跳过。
   
4. 所有人都判断过后，这一块给最后削过蛋糕的那位；如果没有人削过蛋糕，这块给第一个人。
   
5. 重复 2－4，直至最后剩两人，用我切你选的方式决定。
   

n=3 的简化程序由 Steinhaus 在 1943 年提出。

的答案是 Steinhaus 程序的过简版本，是错的。存在的问题是，A 先选，B 第二个选，如果 B 选走的那杯不是 A 认为的最少的，那么整个过程就不公平了。

====补充====

为何 公平 不一定 无怨？这当然首先是根据数学定义，其表述就已经点明了这个逻辑关系。

而这两个概念的现实意义，是因为同一块蛋糕对每个人的价值不同。

比如下面是一个夸张的例子：

假设一个蛋糕，上面有不同的口味，巧克力，奶油，草莓等。参与分蛋糕的人口味不同，因此对不同部分赋予的价值也不同。这里几何上简单的平均分配就不能解决问题，而公平分配也不一定能让人满意。这就是这个数学问题要解决的问题。

也是在这个意义上，许多人坚持的「第一个切的最后选」，不论是

的五字超简版，还是

的冗余「严谨」版，都是错误的，前者甚至没有一个完整的算法。 第一个切的人会按自己的标准尽量平分，但这不一定是其他两人的标准，使得另两人间可能出现不公平的情况。

比如 A-B 切 C-B-A 选的「策略」，以下就是一个不公平的情况：

A 按照尺寸切出自以为的 1/3 和 2/3，但在 BC 看来，因为小的一块有更多巧克力，所以价值分别是 3/7 和 4/7。此时 B 的最佳策略是切出自以为的 3/7，3/7 和 1/7，C 眼光相同，但在 A 看来分别是 1/3，1/2 和 1/6，其中第二块尺寸更大，只是巧克力不多。如果按照 C-B-A 的顺序选，那么 A 只可能拿到他眼中的 1/6，和 BC 眼中的 1/7。

插嘴一个和题目无关的…

这学期有门选修课叫经济与法律，老师第一节课也问了这个问题。

大部分人的答案还是比较正常的，

然而有个工科男上去讲了十分钟怎么找到蛋糕的圆心，再怎么精确的把它分成三等分……

我来还原一下当时的场景：

工科男：老师，这个问题很简单啊，只要把它分成三份就好了嘛

老师吃了一鲸

工科男像教小学生一样继续解释：老师，只要在这里取一个点，然后做中垂线……