征集3个人分蛋糕的方法

作者:, 发表于

理论计算机笔记

查看该系列所有文章

Yao在课程《理论计算机II》的第一节课上提到的一个问题:

三个人如何平分一块蛋糕?

要求每个人拿到不少于1/3的蛋糕——这里指的是每个人认为自己拿到的蛋糕价值不少于整块蛋糕的1/3,而每个人对于蛋糕的不同区域的价值认识可能不同(即并不完全等价于面积)。

方法最好可以推广到n个人的情形。

课上讲了一种方法:

任选一个人,在蛋糕上缓慢移动,直到有人喊停,切下一块给这个喊停的人。直到分完为止,最后一块给最后一个人(没机会喊停了)。

这个有趣的问题在课堂上引起非常多的讨论,助教被要求在习题课上至少给出6种不同的方法...

请大家帮忙,踊跃发言 :)

[tags]理论计算机课程,切蛋糕,策略[/tags]

Q.E.D.


上一篇:策略游戏:医生和病人(I)2007年7月10日
我很早之前就想过这个问题,但一直只知道一个trivial的答案。前两天无意中发现网上已经有高手给出了更好的方案,故记录在此。有兴趣的可以自己想

下一篇:飞机加油问题2008年4月3日
珍爱生命,远离政治。今天我们讨论一个数学问题。 这个问题的一个基本版本是说,有N架完全相同的飞机停留在一个机场,每一架最多装的油可以支


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。