分蛋糕是极其复杂的

味美的蛋糕会令你馋涎欲滴，但分蛋糕却会令你绞尽脑汁。数学上有一个著名的分蛋糕问题：一块蛋糕有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还没停。情况是假定乙和丙勾心斗角，有各自的理性抉择，同时每个人都会嫉妒别人分到比自己多.....