====正文====
这是著名的 cake cutting 问题。
Fair division所谓「三人都满意」,数学上有多种可能的涵义,常用的两种是:
无怨一定公平,但是公平不一定无怨。
daniel 的答案,上面这两个条件都不满足,只会引起自责,不算满意/公平,是错的。
两人的情况很简单:我切,你选。
三人的情况曾经长时间没有解,40 年代找到公平程序,80 年代发表无怨程序。
多人的无怨切法还没有完满解决。
daniel 的答案是一种「走刀程序 moving-knife procedure」。真正达到「无怨」的 走刀程序 见
Stromquist moving-knife procedure,80 年代由 Stromquist 提出。
需要一个裁判,从左向右走刀,三人拿着刀站在裁判右边,保持在平分右边蛋糕的位置(按各自标准)。一旦三人中有一个喊「切」,此人获得裁判左边的蛋糕。然后三人中位于中间位置的那位(B)把刀切下。没蛋糕的两位中,离裁判近的那位获得中间那块,远的那位获得右边那块。
容易证明,三人都认为自己的那份最大。
走刀程序的坏处是连续,假设了两人同时叫停的概率为零,假设了蛋糕无限可分,现实中不好操作。
一个离散程序是
Selfridge60 年代由 Selfridge 提出,90 年代由 Conway 独立提出并发表。
可以证明,三人都认为自己的那一份最大,证明见维基页面。
四人无怨分割的走刀程序,1997 年由 Brams, Taylor and Zwicker 提出。多人无怨分割的离散程序,1995 年由 Brams and Taylor 提出,但是需要切的次数可能无上界,因此应该说尚未完满解决。
以上是「无怨」的切法。「公平」的切法要简单一些,这里有一个很通俗的介绍:
Mathematics In Europe,波兰数学家们做了很大贡献。针对 n 人的一般公平程序如下(Banach and Knaster 提出):
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。
插嘴一个和题目无关的…
这学期有门选修课叫经济与法律,老师第一节课也问了这个问题。
大部分人的答案还是比较正常的,
然而有个工科男上去讲了十分钟怎么找到蛋糕的圆心,再怎么精确的把它分成三等分……
我来还原一下当时的场景:
工科男:老师,这个问题很简单啊,只要把它分成三份就好了嘛
老师吃了一鲸
工科男像教小学生一样继续解释:老师,只要在这里取一个点,然后做中垂线……
本站所有内容均为互联网搜索引擎提供的公开搜索信息,本站不存储任何数据与内容,任何内容与数据均与本站无关,如有需要请联系相关搜索引擎包括但不限于百度,google,bing,sogou 等
© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有