ASPCN防雷技术论坛

标题: 头大如箩的题 [打印本页]

作者: sundy    时间: 2003-7-1 12:42
标题: 头大如箩的题
13~~~~偶看到这个题目觉得很简单,回头看到答案~比题目长10倍,你慢慢做吧,偶看得眼晕~~

            海盗分赃

 有10个海盗要分100枚金币。如何分投票来解决。规则如下:先由最凶猛的海盗来提出分配方案,然后大家一人一票表决,如果有50%或以上的海盗同意这个方案,那么就以此方案分配,如果少于50%的海盗同意,那么这个提出方案的海盗就将被丢到海里去喂鱼,然后由剩下的海盗中最凶猛的那个海盗提出方案,依此类推。

  我们先要对海盗们作一些假设。

  1) 所有海盗都知道别人的凶猛性,也就是说,每个海盗都知道自己和别人在这个提出方案的序列中的位置 
  2) 每个海盗不愿意自己被丢到海里去喂鱼,并希望自己能得到尽可能多的金币。
  5) 每个海盗都是现实主义者,如果在一个方案中他得到了1枚金币,而下一个方案中,他有两种可能,一种得到许多金币,一种得不到金币,他会同意目前这个方案,而不会有侥幸心理。总而言之,他们相信二鸟在林,不如一鸟在手。
  6) 最后,每个海盗都很喜欢其他海盗被丢到海里去喂鱼。在不损害自己利益的前提下,他会尽可能投票让自己的同伴喂鱼。
         如何分呢?


作者: richard    时间: 2003-7-1 12:47
[这个贴子最后由richard在 2003/07/01 12:54pm 第 1 次编辑]

科幻世界上有类似的小说,好象是一个星球上杀滑豚的分配法。你永远做最低层的,且要有技巧,每次都要干掉船长。。
作者: 通天雷神    时间: 2003-7-1 12:53
好题目。完全是胜利者游戏。我觉得不难做。用逆向思维就可以。

我知道怎么分了。考俺逻辑数学?


作者: sundy    时间: 2003-7-1 12:54
非常需要技巧~~
作者: richard    时间: 2003-7-1 12:55
下面引用由通天雷神2003/07/01 12:53pm 发表的内容:
好题目。完全是胜利者游戏。我觉得不难做。用逆向思维就可以。
我知道怎么分了。考俺逻辑数学?

说吧。
作者: 通天雷神    时间: 2003-7-1 13:04
太麻烦了,不过简单的说说也可以。不怎么浪费时间。

首先:应该明白只剩下两个海盗A和B时的情况。A会拿走100块让B一块也得不到,而B不会反对。因为A的提议已经通过50%的同意。

其次:三个海盗的时候,A为得到50%通过,他会给B1快金币的贿赂,而让B同意提议,C什么都得不到。

接着:四个海盗的时候,A会给B、C一人一块金币,而让D一块也得不到。

以次类推就可以推出10人的情况。

俺忙着呢,脑子现在转的不快。闲了列个逻辑群慢算。


作者: sundy    时间: 2003-7-1 13:27
思路正确,继续
作者: 焱    时间: 2003-7-1 13:37
看晕了。
作者: 克子    时间: 2003-7-1 19:04
又没事干了?
作者: xiaoyanzi    时间: 2003-7-1 19:20
下面引用由通天雷神2003/07/01 01:04pm 发表的内容:
太麻烦了,不过简单的说说也可以。不怎么浪费时间。
首先:应该明白只剩下两个海盗A和B时的情况。A会拿走100块让B一块也得不到,而B不会反对。因为A的提议已经通过50%的同意。
其次:三个海盗的时候,A为得到50% ...

强盗不仅是要利益最大化,还要防止利益最小化(被扔到海里喂鱼)
作者: sundy    时间: 2003-7-1 20:40
说了半天猜出来了没?
作者: 通天雷神    时间: 2003-7-2 00:03
俺算了,答案分为10种类型。别再折腾俺的脑子了。俺怕了:(
作者: richard    时间: 2003-7-2 15:37
下面引用由通天雷神2003/07/02 00:03am 发表的内容:
俺算了,答案分为10种类型。

????
作者: sundy    时间: 2003-7-2 15:42
偶也没明白,答案只有一个~
作者: 通天雷神    时间: 2003-7-2 16:35
一个强盗得到100块。其余的什么也没得到。

俺忘记可以设置其逻辑值为0了:(


作者: taojun    时间: 2003-7-2 16:37
编个程序算了,伤脑筋
作者: richard    时间: 2003-7-2 16:38
等于废话,要过程。
作者: taojun    时间: 2003-7-2 16:41
要过程干吗,有结果就行了:)
作者: 通天雷神    时间: 2003-7-2 16:50
过程的事情,都说给你听……

其中的道理,用心理会……


作者: taojun    时间: 2003-7-2 16:50
心里想着回家了,888了各位
作者: abao163    时间: 2003-7-2 17:01
还算简单
97 0 1 0 2
作者: sundy    时间: 2003-7-2 17:11
这是五个海盗,偶是说10个海盗~~错!
PS:通天想问题不用脑子,如果是一个海盗收100其余都没有,那偶出这题做啥?又不是脑筋急转弯

作者: abao163    时间: 2003-7-2 17:19
不好意思,我算过5个人分的。不过10个人也差不多,多花点时间而已。明天告诉你分法。
作者: xiaoyanzi    时间: 2003-7-2 22:26
这是一个博弈的问题
作者: sundy    时间: 2003-7-4 16:04
这么久还没人算出来??真得这样难??再保留两天,星期一给答案~~
PS:richard,换头像啦?
作者: xiaoyanzi    时间: 2003-7-5 09:31
其实没有答案,你能保证强盗们和你想的一样,而且10个强盗都和你想得一样,还是你有点强盗心理?
作者: cnsh1315    时间: 2003-7-5 11:30
我是实在没有精力去算。
不难,就是复杂,费时间。
作者: ASP    时间: 2003-7-5 14:04
同意 xiaoyanzi 的说法
因为10个强盗是一样的想法,所以一定会有人知道你想干吗,就算你一个也不要先把你干掉!
作者: 焱    时间: 2003-7-5 15:59
哈!有道理!换了我也这样。
作者: richard    时间: 2003-7-7 09:26
这是在做特定的题目,争论什么呀?
作者: sundy    时间: 2003-7-7 13:51
倒~~~~幸好ASP不在这艘船上,哈哈~~~
作者: sundy    时间: 2003-7-7 13:51
公布答案:

答案:97,0,1,0,2或97,0,1,2,0

要解决这类问题,我们总是从最后的情形向后推,这样我们就知道在最后这一步中什么是好的和坏的决定。然后运用这个知识,我们就可以得到最后第二步应该作怎样的决定,等等等等。要是直接就从开始入手解决问题,我们就很容易被这样的问题挡住去路:“要是我作这样的决定,下面一个海盗会怎么做?”

  以这个思路,先考虑只有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


  现在我们将海盗分金问题推广:

  1) 改变一下规则,投票中方案必须得到超过50%的票数(只得到50%票数的方案的提出者也会被丢到海里去喂鱼),那么如何解决10个海盗分100枚金币的问题?
  2) 不改变规则,如果让500个海盗分100枚金币,会发生什么?
  3) 如果每个海盗都有1枚金币的储蓄,他可以把这枚金币用在分配方案中,如果他被丢到海里去喂鱼,那么他的储蓄将被并在要分配的金币堆中,这时候又怎样?

  通过对规则的细小改变,海盗分金问题可以有许多变化,但是最有趣的大概是1)和2)(规则仍为50%票数即可)的情况,本帖只对这两种情况进行讨论。

  首先考虑1)。现在只有P1和P2的情形变得对P2其糟无比:1票是不够的,可是就算他把100枚金币都给P1,P1也照样会把他丢到海里去。可是P2很关键,因为如果P3进行分配方案的话,即使他一枚金币也不给P2,P2也会同意,这样一来P3就有P2这张铁票!P3的最佳方案就是:独吞100枚金币。

  P4要3张票,而P3是一定反对他的,而如果不给P2一点甜头,P2也会反对,因为P2可以在P3的方案中得救,目前为什么不把P4丢到海里呢?所以要分别给P1和P2一枚金币,这样P4就有包括他自己1票的3票。P4的方案为:P1,P2每人1枚金币,他自己98枚。

  P5的情况要复杂点,他也要3票。P4是会反对他的,所以不用给,给P3一枚金币就能使他支持自己的方案,因为在接下来的P4方案中他什么也得不到。问题是P1和P2:只要其中有一个支持就可以了。可是只给1枚金币是不行的,P4方案中他们一定有1枚金币可得,所以只要在他们中随便选一个,给2枚金币,另一个就对不起了,不给。这样P5的方案是:自己97枚,P3得1枚,P1或P2得2枚。

  P6的方案建立在P5的上面,只要给每个P5方案中不得益的海盗1枚金币。要注意的是,P1和P2都应该看作在P5方案中不得益的:他们可能得2枚,可是也可能1枚不得,所以只要P6给他们1枚金币,根据“二鸟在林,不如一鸟在手“的原则,就可以让他们支持P6的方案。所以P6的方案是唯一的:P1,P2,P4每人1枚金币,P6自己拿97枚。

  这样继续下去,P9的方案是:P3,P5,P7每人1枚金币,然后在P1,P2,P4,P6中任选一人给2枚金币,P9自己得95枚。最后,P10的方案是唯一的:P1,P2,P4,P6,P8每人1枚金币,P10自己得95枚。

  2)是最有趣的(提醒:我们回到50%票即可的规则)。原题解中的推理过程直到200个海盗都是成立的:P200给每个偶数号的海盗1枚金币,包括他自己,其他海盗什么也得不到。从P201开始,继续推理就变得有点困难了:P201为了不被丢到海里去,必须什么也不留给自己,而给从P1到P199中所有奇数号海盗每人1枚金币,从而争取到100票,加上他自己1票,逃过一劫。P202也什么都得不到,他必须用这100枚金币买通100个从P201的方案中什么也得不到的海盗,要注意到现在这个方案不是唯一的:P201的方案中得不到金币的海盗是所有奇数号的海盗,有101个(包括P201),所以有101种方案。

  P203必须得到102票,除了自己的1票外,他只有100枚金币,所以只能买到100票,所以可怜的家伙就被丢到海里喂鱼了。但是,P203是个很重要的角色,因为P204知道如果自己的方案不被通过,P203也一样会完蛋,所以他有P203的一张铁票。所以P204可以大出一口气:他自己一票,加上P203一票,然后加上用100枚金币买的确100票,他就得救了!100个有幸得到1枚金币的海盗,可以是P1到P202中任何100个:因为其中的偶数号的从P202的方案中什么也得不到,如果P204给他们中某个海盗1枚金币,这个海盗一定会赞同这个方案;而编号为奇数的海盗呢,只是有可能从P202的方案中得益罢了(可能性为100/101),所以根据“二鸟在林,不如一鸟在手“的原则,如果能得到1枚金币,他也会赞同这个方案。

  接下去P205是不能把希望放在P203和P204这两张票上的,因为就算他被丢到海里去,P203和P204还可以通过P204的方案机会活下来。P206虽然可以靠P205的铁票,加上自己1票和100枚金币搞到的100票,只有102票,所以他也被丢到海里喂鱼。P207好不了多少,他需要104票,而他自己以及P205和P206的铁票加上100枚金币搞到的100票只有103票——只好下海。

  P208运气比较好,他同样也要104票,可是P205,P206,P207都会投票赞成他的方案!加上他自己的1票和买来的100票,他终于逃脱了做鱼食的命运。

  这样我们就有了一种可以一直推下去的新逻辑。海盗可以什么也不留给自己,买上100票,然后依靠一部分一定会被丢下海的海盗的铁票,从而让自己的方案通过。有这样运气的海盗分别是P201,P202,P204,P208,P216,P232,P264,P328和P456……我们看到这样的号码是200加上一个2的次幂。

  哪些海盗是受益者呢,显然铁票是不用(不能)给金币的。所以只有上一个幸运号码及他以前的那些海盗才有可能得到1枚金币。于是我们得到500海盗分100枚金币的结论是:前44个最凶猛的海盗被丢进海里,然后P456给P1到P328中的100个海盗每人1枚金币。

  就这样,最凶猛的海盗被丢进海里,而比较凶猛的什么也得不到,而只有最温柔的那些海盗,才有可能得到1枚金币。


作者: 通天雷神    时间: 2003-7-7 20:51
OK。看的到是有点晕。还好看明白了。




欢迎光临 ASPCN防雷技术论坛 (http://asp.cn/) Powered by Discuz! X3.2