jiry_2's Blog

总算是来更分饼这篇博客了..感觉也是挺有意思的就更一下吧。

upd 5.24

嘛..昨天发了博客之后听说matrix67讲过这个问题..晚上xllend在QQ上也教了我很多东西..感觉这篇博客挺秀智商大家就看看然后嘲讽嘲讽作者低于平均水平的智商找找乐子吧...然后贴上matrix67的博客网址http://www.matrix67.com/blog/archives/3944有兴趣可以去看一看..

其实吧我感觉我们讨论的不是怎么分饼最公平？我们主要是在想每一个人对饼估价相同时，在以1到[tex]n-1[/tex]的顺序切饼按照什么顺序拿饼最公平> >如果这个还是经典问题只能说我见识太短浅了T^T反正大家就看看图个乐子就行了..主要就是讲故事嘛..

那天晚上和松爷、毛爷、DZY、树爷爷还有猪猪侠去必胜客吃饼，然后分成了三个富人和三个穷逼分开来点餐（虽然到了最后价格差不多），巧的是两组点的餐中都有一个最小号的披萨...

然而..最小号的披萨是分成四块的..

分毛啊...

于是乎我们就开始讨论怎么分饼比较公平了...

ZZX：这个我看到过，一个举着刀在饼上面移动，剩下两个人喊停！喊两次切出来的就是公平的！

然而没有人理他...

我：如果两个人的话就可以一个人切一刀，另外一个人拿走一块，第一个人拿走剩下一块..但是三个人就不知道怎么样了

松爷：第一个人切一刀，第二个人切一刀，第三个人拿走一块，第二个人拿走一块，第一个人拿走最后一块？

然后..我们就开始撕逼了..

大致就是问如果每一个人的目的都是最大化自己拿到的饼，这个切法是不是公平的...如果不公平，每一个人最多可以拿多少的饼呢？

答案是不公平，第一个人最多拿[tex]\frac{1}{3}-eps[/tex]，第二个和第三个人最多拿[tex]\frac{1}{3}+\frac{eps}{2}[/tex]的饼，[/tex]eps[/tex]可以无限接近0但是无法等于0。

假设第一个人切了[tex]x(x \leq \frac{1}{2})[/tex]的饼，我们分三种情况考虑：

1.[tex]x < \frac{1}{3}[/tex]，那么第二个人肯定把较大的饼对半切开，第一个人可以拿到大小为[tex]x[/tex]的饼。

2.[tex]x=\frac{1}{3}[/tex]，那么第二个人只要切较大的饼，无论怎么切他都可以拿到[tex]\frac{1}{3}[/tex]的饼，所以他可以随意切一刀，第一个人期望拿到饼的大小只有[tex]\frac{1}{6}[/tex]

3.[tex]\frac{1}{3} < x \leq \frac{1}{2}[/tex]，那么第二个人一定会在较大的饼上切下一块大小为[tex]x[/tex]的饼，第一个人可以拿到[tex]1-2x[/tex]的饼。

总上，第一个人无论如何都无法拿到[tex]\frac{1}{3}[/tex]的饼，最多只能拿到大小无限接近[tex]\frac{1}{3}[/tex]的饼。所以我们认为这个分发是不公平的。

然后...撕逼的问题就变成了怎么取才是公平的..

最后我们YY出来公平的分发是第一个人切，第二个人切，第三个人拿，第一个人拿，第二个人拿。