味美的蛋糕会令你馋涎欲滴，但分蛋糕却会令你绞尽脑汁。数学上有一个著名的分蛋糕问题：一块蛋糕有N个人分，每一个人对自己分到的那块都持有不同的观点，怎么分才能让每一个人都满意（或叫Envy-free）？1980 年费城附近Swarthmore学院的Walter Stromquist证明存在一个Envy-free解。换句话说，一块蛋糕切N-1次分给N个人，让每个人都满意是可能的。N=2和N=3的情况比较简单（其实N=3已经相当繁琐了），1992年Steven Brams和Alan Taylor证明了N>3的情况，但算法过于复杂，他们为此特地写了一本书来剖析如何公平的分蛋糕。现在香港城市大学的Xiaotie Deng和同事提出了一种更高效分蛋糕算法（预印本），算法的计算可在多项式时间内完成。但唯一令人遗憾的问题是算法适用范围是N=3，另外的一些特例只能得到近似的Envy-free解。以下引用流?日?： 1. N=2：两个人分蛋糕时，一般都认为直接分一半不就得了？确实如此，但是如果两人，譬如是两位小朋友，都在意有没有公平分到水果，那这样的话谁都会想要先选，并且尽量得到越多水果越好。假如切的和先选的都是同一位，则另一位一定觉得不公平。所以最好的解决方法是“一个人切蛋糕，另一人先选”，这样第一个人就尽量不会太小心眼，而第二个人的选择也不会占到什么便宜。
2. N=3：当甲乙丙三个人要分一块蛋糕时，先将状况简化一下，蛋糕是圆形，而且每个人在意的只有蛋糕大小，对装饰不考虑。那么可能的分法有两种。 a.第一种分法，假定让甲执刀，从一条起点的半径绕着蛋糕转，剩下的乙和丙观察，如果其中有一个人(例如丙)觉得已经到1/3时喊停，让甲切下蛋糕当作丙分得的那份。剩下来的状况就和两人分一样了。这种分法也引出一另个情境，就是假定三人分蛋糕，乙和丙没有订定契约或者暗中勾结，让刀子超过1/3还没停。情况是假定乙和丙勾心斗角，有各自的理性抉择，同时每个人都会嫉妒别人分到比自己多.....
naruto01 于 2010-05-08 14:29:03发表:
努力发展生产力！
相思爱文 于 2010-04-29 10:40:28发表:
三人分蛋糕，那准备三块就行了，一人一个。
如果只有一块，那分成3的整数倍（越多越好），每人拿一份，再每人拿一份……，直到拿完。
com98cn 于 2010-03-29 09:08:22发表:
典型的需要用数学建模来解决的问题，比较复杂，呵呵估计一般人是不需要了解的，只有那些专业人员才会感兴趣，楼主你看你稍微解释一下，楼下的就晕死一大片了！
chaba 于 2009-12-10 17:13:25发表:
他们没有与时俱进，用科学发展观的眼光来和谐地分配蛋糕。
lethe 于 2009-11-20 15:34:19发表:
患生于多欲而人心难测也:0w5ty(1
zhouhedy 于 2009-10-29 10:44:34发表:
其实这哪是在讲数学题啊，完全看的是蛋糕本身的，为什么不选一个没有任何装饰的普通蛋糕呢。这样不就好分了吗，公平分要找到要蛋糕以外的人来分。
kxajd001 于 2009-08-07 13:26:13发表:
把事情看简单了 说明这人就强大了
刘冲 于 2009-07-27 21:10:34发表:
实际上，事情是很复杂的！hantu 于 2009-07-27 21:09:26发表:
事情都是简单的,复杂的是人心
l460618498 于 2009-07-26 21:08:43发表:
数学博大精深啊
l460618498 于 2009-07-26 21:08:39发表:
数学博大精深啊
litkt 于 2009-07-24 16:58:19发表:
外国人都在研究什么？
我们在研究特色社会主义，他们却在……
研究科学社会主义。
bbsytc 于 2009-07-24 10:02:32发表:
我倒
rieo232 于 2009-07-24 09:29:33发表:
什么东东，数学题？
jiehe 于 2009-07-24 07:23:46发表:
外国人都在研究什么？
我们在研究社会主义，他们却在……