level 7
我不是悠然，但我也来出题了，呵呵~我也刚看到题目，跟亲们一起想。Q：现在船上有若干个海盗，要分抢来的若干枚金币。自然，这样的问题他们是由投票来解决的。投票的规则如下：先由最凶猛的海盗来提出分配方案，然后大家一人一票表决，如果有50%或以上的海盗同意这个方案，那么就以此方案分配，如果少于50%的海盗同意，那么这个提出方案的海盗就将被丢到海里去喂鱼，然后由剩下的海盗中最凶猛的那个海盗提出方案，依此类推。 我们先要对海盗们作一些假设。 1) 每个海盗的凶猛性都不同，而且所有海盗都知道别人的凶猛性，也就是说，每个海盗都知道自己和别人在这个提出方案的序列中的位置。另外，每个海盗的数学和逻辑都很好，而且很理智。最后，海盗间私底下的交易是不存在的，因为海盗除了自己谁都不相信。 2) 一枚金币是不能被分割的，不可以你半枚我半枚。 3) 每个海盗当然不愿意自己被丢到海里去喂鱼，这是最重要的。 4) 每个海盗当然希望自己能得到尽可能多的金币。 5) 每个海盗都是现实主义者，如果在一个方案中他得到了1枚金币，而下一个方案中，他有两种可能，一种得到许多金币，一种得不到金币，他会同意目前这个方案，而不会有侥幸心理。总而言之，他们相信二鸟在林，不如一鸟在手。 6) 最后，每个海盗都很喜欢其他海盗被丢到海里去喂鱼。在不损害自己利益的前提下，他会尽可能投票让自己的同伴喂鱼。 现在，如果有10个海盗要分100枚金币，将会怎样？
2008年08月16日 11点08分
1
level 12
1号的最佳提案绝对是97，0，1，0，2。显然楼上的方案都将楼主的问题私自窜改了（即将“一半以上的人同意这个方案则通过，否则杀死....”改成“当且仅当半数和超过半数同意则通过提案”)。下面我按楼主的意思来推论1号的最佳方案：（当然也用倒推法） 1，如只剩最后两位海盗，则不论第四位如何分他都将得不到一枚钻石，因为不可能通过半数以上。（假如他够聪明，再加上第五位仁慈点的话，他主动出个0：100的方案，可能会免掉一死）。即第四位的期望值是1，也就是说前面哪位能分给他一枚钻石他就满足了。此时的分金方案只能是0：100。 2，如果剩最后三位的话，即由第三位出方案，他只要能拉拢其余两位中的一位即可，但第因第五位只要能杀死第三位即可独吞100枚钻石，故他只能拉拢第四位，而且只需给第四位1枚钻石即可。他的最优方案必然是99：1：0；因此致到这一步时，第四位至少可得一枚金币，而第五位将一无所获。 3，如果剩最后四位的话，即由第二位出方案，他须拉拢剩下三个中的两位才行。显然他不能拉拢第三位，因此他只要比预计的第三位出的方案更吸引第四位和第五位即可成功，因此他的最优方案必然是97：0：2：1。 4，因此，第一位的方案要想获得通过，他也只需拉拢剩余四位中的两位即可，显然他不会用98枚去拉拢第二位，而他只需给第三位一枚钻石即可搞定一个，另再给第5位2枚即可。（如果给第四位的话，则至少要给3枚，因为第四位从第二位的方案中也可以至少得到2枚。-这显然不是最优方案） 因此第一位的方案必然是97：：0：1：0：2
2008年08月16日 11点08分
2
level 7
...瓦```````瓦```````看懂了``````不过```本人不擅长- -(其实瓦什么也不擅长```
2008年08月16日 13点08分
4
level 5
哇哇哇……我的语文和数学都很烂……烂到不行……放过我吧……
2008年08月17日 02点08分
8
level 7
答案~跟我想的差不多，整整用了两个小时啊。。。累死了。。。因为过程较复杂，就直接COPPY下来粘贴了一下，呵呵~要解决这类问题，我们总是从最后的情形向后推，这样我们就知道在最后这一步中什么是好的和坏的决定。然后运用这个知识，我们就可以得到最后第二步应该作怎样的决定，等等等等。要是直接就从开始入手解决问题，我们就很容易被这样的问题挡住去路：“要是我作这样的决定，下面一个海盗会怎么做？” 以这个思路，先考虑只有2个海盗的情况（所有其他的海盗都已经被丢到海里去喂鱼了）。记他们为P1和P2，其中P2比较凶猛。P2的最佳方案当然是：他自己得100枚金币，P1得0枚。投票时他自己的一票就足够50%了。 往前推一步。现在加一个更凶猛的海盗P3。P1知道——P3知道他知道——如果P3的方案被否决了，游戏就会只由P1和P2来继续，而P1就一枚金币也得不到。所以P3知道，只要给P1一点点甜头，P1就会同意他的方案（当然，如果不给P1一点甜头，反正什么也得不到，P1宁可投票让P3去喂鱼）。所以P3的最佳方案是：P1得1枚，P2什么也得不到，P3得99枚。 P4的情况差不多。他只要得两票就可以了，给P2一枚金币就可以让他投票赞同这个方案，因为在接下来P3的方案中P2什么也得不到。P5也是相同的推理方法只不过他要说服他的两个同伴，于是他给每一个在P4方案中什么也得不到的P1和P3一枚金币，自己留下98枚。 依此类推，P10的最佳方案是：他自己得96枚，给每一个在P9方案中什么也得不到的P2，P4，P6和P8一枚金币。 下面是以上推理的一个表（Y表示同意，N表示反对）： P1 P2 0 100 N Y P1 P2 P3 1 0 99 Y N Y P1 P2 P3 P4 0 1 0 99 N Y N Y P1 P2 P3 P4 P5 1 0 1 0 98 Y N Y N Y …… P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 0 1 0 1 0 1 0 1 0 96 N Y N Y N Y N Y N Y
2008年08月17日 05点08分
10
level 5
你们误会了我才懒得去想这些东西我可是全世界绝无仅有的最没有杂质的单细胞动物啊~~~~~那个是上网捞的
2008年08月17日 06点08分
11
level 7
说出方案的海盗可以为自己投票的，呵呵~知道方法就不难解题了，王妃的推理方法是对的，可是窜改了题目，所以不对，呵呵~
2008年08月17日 06点08分
12
