xilihutu
[个人文集]
论坛管理员
性别: 
加入时间: 2007/03/29
文章: 9277
来自: 美国
经验值: 298820
|
|
|
作者：xilihutu 在 驴鸣镇 发贴, 来自 http://www.hjclub.org
这不需要算数，也不需要阴谋，只是需要一点点的君子风度而已。
原以为孔孟教育出来的都是君子，能不能数数中国有几多君子？
西人如何切蛋糕也特认真， 糊涂曾经听过一特聪明的数学家讲：
How to cut a cake almost fairely?
http://www.jstor.org/pss/2311357
The Surprisingly Complex Art of Cake Cutting
Mathematicians have discovered how to divide a cake fairly among three people.
Mathematicians love a good cake, so it is hardly a surprise that the problem of how to cut and apportion a Victoria sponge, say, has severely exercised them. Today, cake lovers will be excited to hear of a significant breakthrough.
The problem is this: how do you cut a cake and divide it fairly among n people when each person may have a different opinion of the value of each piece?
In 1980, Walter Stromquist at Swarthmore College near Philadelphia proved that there was an envy-free solution to the problem. In other words, it is possible to cut a cake into n pieces using n−1 cuts and to allocate one piece to each person so that everyone values his or her piece no less than any other piece.
But although a solution may be possible, finding it is hard. The open question today is whether there is an efficient algorithm that finds such a cut of the cake, say Xiaotie Deng at the City University of Hong Kong and a couple of pals.
Their contribution to the problem is to find such an algorithm, albeit with a couple of minor caveats. Impressively, their algorithm works in polynomial time, which means that a solution can always be found reasonably quickly.
The caveats? The algorithm works when dividing a cake only among three people and then only for the special case involving mathematical objects called measurable utility functions, and the result is only approximately envy-free.
Nevertheless, that should still be handy when a dispute arises at the next junior common room tea party.
Ref: arxiv.org/abs/0907.1334: On the Complexity of Envy-Free Cake Cutting
唉，到现在稀里糊涂都想不明白切个蛋糕西人居然还有数学证明。
     
作者：xilihutu 在 驴鸣镇 发贴, 来自 http://www.hjclub.org
上一次由xilihutu于2009-8-21 周五, 下午12:19修改，总共修改了5次 |
|
|
“海盗分金”中的“理性”不是真理性
