关于切蛋糕

来源: 康MM 于 2007-11-26 18:47:23 [档案] [博客] [旧帖] [给我悄悄话] 本文已被阅读：次 (1149 bytes)

本文内容已被 [ 康MM ] 在 2007-12-03 13:46:55 编辑过。如有问题，请报告版主或论坛管理删除.

长周末时花了点时间看乱弹介绍的切蛋糕文章，有好几篇文章，而且都很长，只能挑着看，把已经看了的向大家介绍一下。

问题的要求是n个人分一个蛋糕，每个人都要求自己分到的一份至少是（按自己的标准）并列最大。

两个人的时候当然就是一个人去另一个人挑。三个或更多人的时候按照我们以前讨论中认定的方法，（即每人只知道自己的喜好，而且一个人切的时候别人不参与意见，）有限解不存在。（还没有看证明。）如果不限制这个方法，可以有有限解。

三个人时可以用两把移动刀来解：首先一个人按自己的标准把蛋糕切成相等的三份，然后让另两个人挑最大的。如果两人挑的不同，就没事了。如果两人挑了同一块，则由第一个人拿两把刀从这一块的两端开始以同样速度向里移动找切点，（切下来的两小块要加到另外两块上。）另外两人等到这一块与另外两块其中之一（加上一小块）相等时喊停。然后第一个人在此切下去。喊停的人拿走他认为相等的另一块，没喊停的人拿走切小了的这一块。（他没喊停证明他还认为这块最大。）拿刀的人拿走剩下的一块（加上一小块）。

四个人时解法非常复杂，要三把刀同时移动，而且要切很多次。我还没有看完，不知好不好玩。

更一般时，对任意n,可以证明有限解总是存在的，即如果有一个人知道所有人的喜好，他总可以把蛋糕切成有限份，让所有人都满意。但是没有看到有具体的有限解法。