魔方吧·中文魔方俱乐部

标题: 如何分蛋糕，更有点难度 [打印本页]

作者: 刚吃完 时间: 2008-9-9 15:39:40 标题: 如何分蛋糕，更有点难度

如何分蛋糕，更有点难度。
一块蛋糕（形状规则／不规则均可），一把切蛋糕的刀，n个人
分，怎么分？

（在现实中可应用）

作者: qq1627354 时间: 2008-9-9 15:45:20

咋有点迷糊呢。。。。说条件限制呢？？

作者: 刚吃完 时间: 2008-9-9 15:48:57

这和前边的题一样。
人数多点。
两个人的情况下，一人切一人分。
人多了怎么办？

作者: gozichen 时间: 2008-9-9 15:50:45

沿竖向切，要多少切多少

作者: kexin_xiao 时间: 2008-9-9 15:51:26

条件没有说全吧？？

作者: 刚吃完 时间: 2008-9-9 15:54:03

我以为你们全知道那？
两个人的情况下，一人切一人分。
明白吗？

作者: ares_g 时间: 2008-9-9 16:09:09

是不是说切的人最后拿？跟分粥似的。坦白讲，没看懂题。

作者: sl888000 时间: 2008-9-9 16:30:18

和楼上一样，没看懂。。。

作者: 魔鱼儿 时间: 2008-9-9 16:41:12

看不大明白楼主的意思，晕。条件不全吧

作者: 刚吃完 时间: 2008-9-9 16:45:15

急！刚才帖子够数了，没办法回答。
前边有一道，两个人分蛋糕，看到后想起这道题。
除人数外，其他条件一样。
分不规则蛋糕有名的题，两个人分，一人切一人挑。
基本公平，但人数多的情况下，
切的人最后拿，会有一问题。
其他的人，谁先挑？

作者: yjw44 时间: 2008-9-9 16:47:56

看不懂,LZ把问题条件什么的都说清楚嘛,不要跟什么前面的贴子联系在一起,前面的帖子没看的人很多..

作者: ares_g 时间: 2008-9-9 17:23:36

谁先挑都一样，切蛋糕的为了公平会把所有块切得一样大——如果我没猜错题意的话。

作者: 刚吃完 时间: 2008-9-9 17:39:51 标题: 前边的题

pumpitup：
一块蛋糕（形状规则／不规则均可），一把切蛋糕的刀，甲、乙两个人
两人都要求蛋糕要平均分成两份，请你给出一个方法，平分蛋糕，使得两人都满意！
看到答案前我觉得是不可能做到的。
欣然：
让一个人切，另一个人选。
欣然：
LZ题的意思好象就是分成两块，所以，就分一次就可以了。权利均等就是平均。
whitetiger：
甲切乙选。
本身不是是不是等分的问题，是双方觉得公平的问题。
我顺便问一下：如果若干个人分蛋糕呢？
比较简单的，可以假设蛋糕是长条的。
随意拿，分蛋糕的最后拿，肯定不是最好的答案，只能保证分蛋糕的人会保证尽量公正，但其他人不会觉得公平。
---------------------------------------------------
以上是前边的题，解答的很圆满。
现在是人数多了，怎么办？
就是简单的题意。就是难度大，我看书的时候也没想出来。

作者: yama523 时间: 2008-9-9 17:40:56

这个问题有点不知所以然呀，哈哈，看来我是不会。

作者: ares_g 时间: 2008-9-9 17:51:00

有N个人，就切成N大块，之后N个人站一圈，按顺序轮流拿刀，把其中一大块切成N小块并向下一个人传递来分蛋糕，就是按照分蛋糕的人最后拿的原则分掉每一大块。公平嘛，就是以牺牲效率为代价的。

作者: flwb 时间: 2008-9-9 18:00:25 标题: 回复 15# 的帖子

每人分一遍,虽然会切得很碎,但最公平!

作者: 刚吃完 时间: 2008-9-9 18:03:39

此方法不能杜绝联手作弊

作者: ares_g 时间: 2008-9-9 18:19:13

那就由抽签决定每次取蛋糕的顺序，前提是保证切蛋糕的最后一个拿。

作者: 清衫小白 时间: 2008-9-9 22:49:49

切的人最后拿，n个人就变成了n-1了，以此类推，n-1个人任意挑出一个，将其中一块（一般是最大的）切掉一少部分询问大家的意见，......

作者: jerold 时间: 2008-9-10 08:42:21

方法一：
n个人选两个人当领导，其它的人可以选择跟随两个领导的其中一人， 两个人一个切，分成两份，另一个选，其它的人该随谁的跟谁 共同拥有哪一份蛋糕。一份蛋糕公平分了两份两堆人。同样方法分下 去，就把大蛋糕分成无数份。
 
方法二：
n个人，找一个人切蛋糕，切成A和B两份，其它人按顺序，选要A或B都可以，一个选了下一人再选，选A或B，
但是切蛋糕的人最后，唯一没得选的人，如果倒数第二个人选了A，切蛋糕的人只能要B。
结果蛋糕A由一群拥有，蛋糕B由另一群人拥有，同样的方法再把蛋糕继续分。
 
两个方法的原理一样，切蛋糕的人要那一份蛋糕决定于别人。

[ 本帖最后由 jerold 于 2008-9-10 10:31 编辑 ]

作者: 刚吃完 时间: 2008-9-10 09:19:40

方法一:：选领导是个问题。
方法二：没看懂

作者: envy 时间: 2008-9-10 09:31:30

切碎成渣后,按分量分

作者: kexin_xiao 时间: 2008-9-10 10:11:41

这道题以前发过吧，先切的后拿

作者: ares_g 时间: 2008-9-10 10:18:13

每个人都不信任鄙人，如果都选自己当领导，等领导选出来，蛋糕都变质了。

作者: 刚吃完 时间: 2008-9-10 20:54:29 标题: 法院的答案，玩笑

要是法院遇到这种事，法院的方案是把蛋糕拍卖，把钱了。
也比切碎成渣强。
又想起一笑话：古代兄弟俩分家，都说对方分的多。
打官司，到县衙，县官说兄弟俩交换财产就行了。
此题还是有相对好的答案。

作者: ares_g 时间: 2008-9-11 12:47:45

才尽了，等答案。

作者: Atato 时间: 2008-9-11 13:03:42

是等分成N份?我茫然了

作者: Cielo 时间: 2008-9-11 15:05:20

记得以前在书上看过的，一个人拿刀负责分，但他只能最后拿。
分的方法如下：
拿刀者拿起刀，使刀在蛋糕左上方，而且刀所在的平面垂直于桌面，他开始将刀慢慢（必须非常慢）横向移动。这样刀就逐渐移到蛋糕上方，也就是说如果这时切下去就能切下一部分蛋糕来。
 
规定：在移动刀的过程中谁最先喊“停”，那么拿刀者就停止横向移动，然后切下去，切得的部分给喊停者，这样就已经分了一个人的了。接下来重复上述步骤，最后就变成两个人分的情况了。

作者: 刚吃完 时间: 2008-9-11 16:11:48

回答正确，真是博览群书啊。
完美答案。不过我可以再设一问题。重新发帖。

作者: kexin_xiao 时间: 2008-9-11 17:59:37

在各尽所能按需分配的社会到来之前，n个人(n>1)分一块蛋糕的事总是有的。
怎么分才公平呢？这里公平的含义就是，每个人都认为自己可以使自己分得的部分不少于1/n，或者说，如果自己分得的部分少于1/n，也不是别人造成的，而只能怪自己。呵呵。如果n=2,就有个从来就通用的办法，就是甲分乙选。这是公平的，因为甲如果觉得自己分得的没有一半，只能怪自己没有分好；乙如果觉得不公平，只能怪自己没有选好。 
 
问题是，三个人怎么分？ n>3呢？ 
我们来考察与公平地分一块蛋糕这个简单得容易使人上当的问题有关的若干数学问题。所谓公平地分蛋糕的意思就是，如果有n个人分蛋糕，那么每个人都相信自己分得的一份至少为那块蛋糕的1／n。我们将继续研究几个相关的问题，它们涉及到该理论的较现代的内容。首先我们回忆一下前面所得到的结果。两个人分蛋糕时，使用历史悠久的"我分你选"算法，可以实现公平的分配。当3个人或更多的人分蛋糕时，有几种可能的分法。"修整"法是让参加分蛋糕的人依次把一份据称是分得公平的蛋糕缩小，其条件是如果没有其他人修理这份蛋糕，则最后一个修理者必须挑这份蛋糕。"依次成对"的方法则是让头两位参加分蛋糕的人公平地分蛋糕，而第三人则分别与这两人商量，以确保从已经分开的两块蛋糕中分别取得他或她认为至少有1／3的一份。而在"分割一赢得"方法中，参加分蛋糕的人力求一刀就把蛋糕切成两块，使大约一半的人觉得分到的一块是公平的而感到满意。然后对已经分开的两块蛋糕分别重复同样的方法，如此类推。这些算法全都是公平的，但这里还存在一个更复杂的问题。即使人人都相信他或她得到了公平的一份蛋糕，由于妒忌心的作怪，某些人仍然可能觉得自己受了委屈。例如，Tom，Dick和Harrp可能全都认为他们各自得到了至少1／3的蛋糕并对此感到满意，但Tom仍然可能觉得Dick的那一份比自己的大。Tom是一份是"公平"的，但他现在并不觉得很高兴。如果某种分法使任何人都不觉得其他某个人所得到的一份更大，那么这种分法就是"无妒忌的（cnvy-free）"。无妒忌分法肯定是公平的，但公平的分法不一定是无妒忌的。因此，找到一种无妒忌分配的算法比找到一种公平分配的算法更困难。两个人分蛋糕时的"你分我选"的方法显然是无妒忌算法，但上面提到的其他算法全都不是无妒忌算法。 60年代初，John Sclfridgc和John H.Conway首先发现了三个人分蛋糕时的一种无妒忌算法：第一步，Tom把蛋糕分成他认为具有等值的3块。第二步，Dick可以采取下列两个行动之一：（a）如果他认为其中两块或两块以上的蛋糕同为最大的一份，他可以什么也不做；（b）如果他认为有一块蛋糕最大，他可以对其进行修整，使之达到（a）所说的情况。把修整下来的零碎蛋糕放到一边。并称这些累积起来的零碎蛋糕为"剩余物"。第三步，Harry，Dick和Tom依次选一块蛋糕，也就是他们认为最大的一块或并列最大的一块。如果Dick在上面第二步中修整了一块蛋糕，那么他必须选修理过的蛋糕，除非Harry已经先选这一块蛋糕。到这一步时，蛋糕的一部分已经用一种无妒忌方式分完了。这样剩下的事情就是通过无妒忌方式把剩余蛋糕也分完。第四步，如果Dick在第二步什么也没有做，那么不再存在剩余蛋糕，因此蛋糕已被分完。否则，被修理过的那块蛋糕将由Dick或Harry选去。假定Harry得了这块蛋糕（如果是Dick得了这块蛋糕，那么从现在起在下面的分法中就把两个人的名字交换）。然后由Dick把剩余蛋糕分为他们认为是相等的三份。第五步，剩下的事情就是让Harry，Tom和Dick依次从剩余蛋糕中各取一份。由于Harry是第一个选，因此他没有理由眼红。无论剩余蛋糕怎么分，Tom都不会妒忌Harry，因为Harry充其量也只能选到一份Tom认为是等于 1／3块的蛋糕。Tom也不会对 Dick眼红，因为他比Dick先选。Dick也没有理由抱怨，因为剩余蛋糕本来就是他自己分的。在这一点上，人人都被难住了30年。对于n个人分蛋糕的情形，是否存在一种无妒忌分法呢？ 1995年，纽约大学的Steven J.Brains以及联盟学院的 Alan D．Taylor发现了一种引人注目的适于任意多个人的无妒忌分法。这一方法很复杂，因此我不能在此介绍给读者们。读者可以参看他们的论文"一种无妒忌分蛋糕方法"（见《美国科学月刊》（American Mathmatical Monthly），102卷，1995年 1月），或参看Jack Robertson与william Webb的精彩著作"分蛋糕算法"（马萨诸塞州拉蒂克市A.K．peters出版社1998年出版）。蛋糕理论的最令人感兴趣的特点之一就是Robertson和Webb所谓的"分歧有利"论（serendipity of disagreemen）。乍看起来，当每个人对每一小块蛋糕值多少的看法都一致时，公平分配似乎是最容易的。毕竟，在这种情况下，大家对于某一份蛋糕的价值不可能有争议了。但实际上情况正好相反：一旦参与分蛋糕的人对蛋糕价值的看法出现分歧，那就更容易使所有人皆大欢喜。例如，假定Tom和Dick采用"你分我选"的方法来分一块蛋糕。Tom把蛋糕分成两份，并认为这两份蛋糕有相等的价值，即每份均为整块蛋糕的一半。如果Dick也同意Tom的估计，那就不能再做什么了。但是，假定 Dick认为这两种蛋糕的价值各为 3／5和 2／5。这样，出于某种利他主义的理由，他可以决定把他认为是较大的一份蛋糕的1／12奉送给Tom（他估计这一小块蛋糕的价值为整块蛋糕的1/20）。根据他自己的估价，他仍然还有整块蛋糕的3／5-1/20=11／20。实现此分法的一种办法是，Dick把他认为是较大的一份蛋分成他认为具有相等价值的12份。然后他请Tom从这12份中任选一份。无论Tom选了哪一份，Dick仍然认为他得到了整块蛋糕的1／20。另外，Tom有 12小块蛋糕可以选择，而且他认为这些蛋糕和起来就相当于整块蛋糕的一半。因此，按他的估计，其中至少有一份相当于整块蛋糕的1／24。他选择了这份蛋糕后，就自以为他得到蛋糕总共至少是整块蛋糕的13／24。这样Tom和Dick现在皆大欢喜：他们都认为自己得到了比公平的一份还要多的蛋糕。这个问题上的直觉并不是说关于价值的分歧必定会导致关于何为公平分配的分歧。如果由第三方来分蛋糕，然后坚持要Tom和Dick接受这些已预先确定的某一份蛋糕，那就可能出现这种情况。遗憾的是，并非所有任务都能够公平地分配，至少是在受到一些合情合理的限制的情况下不能公平分配。以洗碗为例，如果每个人都必须洗净或者烘干一个完整的碗碟，那么在极端的情况下是不可能做到公平分配的。设想有两个人来洗两个碗，其中一个是大碗，而另一个是小碗。两个人显然都愿意洗小碗而不肯洗大碗。因此，即使在一个所有争议都将通过协商来解决的某些分歧来看仍是不可避免的。

作者: 刚吃完 时间: 2008-9-11 18:28:43

天哪，我很崇拜你。
后边的，我也看了一眼，太烦，不简洁。
忘了，这么快你就找到。你家有图书馆吧？

作者: ares_g 时间: 2008-9-11 18:31:47

高啊，喊得晚了就可能会吃亏，实在是高。又长见识了，谢谢！

作者: 刚吃完 时间: 2008-9-11 18:58:51 标题: 刚找到的网址

http://www.shumo.com/forum/viewt ... p;extra=&page=1
http://bbs.kinotown.com/viewthread.php?tid=121192
刚找到的网址也讨论过蛋糕，百度（蛋糕数学），欣然的资料哪里找的，不知道？

作者: bbshanwei 时间: 2008-9-11 21:46:28

我倒是想吃蛋糕，自己吃谁也不分。

LZ的题在考虑考虑。

作者: 打死也不说 时间: 2008-9-12 14:01:26

肯定会有多个人一起喊的情况到时候你把蛋糕给谁呢都不想要真么办？都想要下一块怎么办？然后下一块又有很多人同时喊以此类推呢

我看还是找个电子称算了

作者: 刚吃完 时间: 2008-9-12 14:21:31

抢答器也行

作者: zgh2002 时间: 2008-9-13 11:43:39

最后的方法很考验人的眼力啊!

作者: fang0402 时间: 2008-9-14 12:48:23

要是有立体空间的分的话，挺难的

作者: jiangqi 时间: 2008-9-14 15:41:13

晕还是没看懂说的是什么意思

作者: 魔方世家008 时间: 2008-9-14 16:07:24

不明白啥意思啊！！！

作者: 魔方世家008 时间: 2008-9-14 16:08:05

不明白啥意思啊！！！！

作者: bella 时间: 2008-9-15 00:01:35

<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/sad.gif" border=0 smilieid="2">  不太明白，恐怕要慢慢消化才行

作者: 497491072 时间: 2008-9-15 19:22:35

n是双数先分组n/2 蛋糕分2半然后再分依此类推一直到2个人分蛋糕

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)