海盗分金——精选推荐

更新时间:2024-03-30 23:47:58 阅读: 评论:0

2024年3月30日发(作者:工作自评)

海盗分金——精选推荐

5个海盗抢到了100颗宝石,每一颗都一样的

大小和价值连城。 他们决定这么分:

1。抽签决定自己的号码(1,2,3,4,5)

2。首先,由1号提出分配方案,然后大家5人

进行表决,当且仅当超过半数的人同意时,按

照他的提案进行分配,否则将被扔入大海喂鲨

鱼。 3。如果1号死后,再由2号提出分

配方案,然后大家4人进行表决,当且仅当超

过半数的人同意时,按照他的提案进行分配,

否则将被扔入大海喂鲨鱼。 4。以此类推

条件: 每个海盗都是很聪明的人,都能很

理智的判断得失,从而做出选择。 问题:

最后的分配结果如何? 提示: 海盗判断

原则 1.保命 2.尽可能多宝石 3.尽可能多杀

大家讨论讨论喔:)

收藏 分享

0

给每一条河每一座山取一个温暖的名字

陌生人, 我也

2

#

greatjason

发表于 2003-7-7 05:21 | 只看该

作者

海盗分金问题全攻略:

小试牛刀

★原文转载自网易数学建模Algorithm版

wangzong_hui的《海盗分币问题》★

数学的逻辑有时会导致看来十分怪异的结

论。一般的规则是,如果逻辑推理没有漏

洞,那么结论就必定站得住脚,即使它与

你的直觉矛盾。 1998年9月,加利福尼

亚州帕洛阿尔托的Stephen M. Omohundro

寄给我一道难题,它恰好就属于这一类。

这难题已经流传了至少十年,但是

Omohundro对它作了改动,使它的逻辑问

题变得分外复杂了。

先来看看此难题原先的形状。10名海

盗抢得了窖藏的100块金子,并打算瓜分

这些战利品。这是一些讲民主的海盗(当

然是他们自己特有的民主),他们的习惯

是按下面的方式进行分配:最厉害的一名

海盗提出分配方案,然后所有的海盗(包

括提出方案者本人)就此方案进行表决。

如果50%或更多的海盗赞同此方案,此方

案就获得通过并据此分配战利品。否则提

出方案的海盗将被扔到海里,然后下提名

最厉害的海盗又重复上述过程。

所有的海盗都乐于看到他们的一位同

伙被扔进海里,不过,如果让他们选择的

话,他们还是宁可得一笔现金。他们当然

也不愿意自己被扔到海里。所有的海盗都

是有理性的,而且知道其他的海盗也是有

理性的。此外,没有两名海盗是同等厉害

的——这些海盗按照完全由上到下的等级

排好了座次,并且每个人都清楚自己和其

他所有人的等级。这些金块不能再分,也

不允许几名海盗共有金块,因为任何海盗

都不相信他的同伙会遵守关于共享金块的

安排。这是一伙每人都只为自己打算的海

盗。最凶的一名海盗应当提出什么样的分

配方案才能使他获得最多的金子呢?

为方便起见,我们按照这些海盗的怯

懦程度来给他们编号。最怯懦的海盗为1

号海盗,次怯懦的海盗为2号海盗,如此

类推。这样最厉害的海盗就应当得到最大

的编号,而方案的提出就将倒过来从上至

下地进行。

分析所有这类策略游戏的奥妙就在于

应当从结尾出发倒推回去。游戏结束时,

你容易知道何种决策有利而何种决策不

利。确定了这一点后,你就可以把它用到

倒数第2次决策上,如此类推。如果从游

戏的开头出发进行分析,那是走不了多远

的。其原因在于,所有的战略决策都是要

确定:“如果我这样做,那么下一个人会

怎样做?”

因此在你以下海盗所做的决定对你来

说是重要的,而在你之前的海盗所做的决

定并不重要,因为你反正对这些决定也无

能为力了。

记住了这一点,就可以知道我们的出

发点应当是游戏进行到只剩两名海盗——

即1号和2号——的时候。这时最厉害的

海盗是2号,而他的最佳分配方案是一目

了然的:100块金子全归他一人所有,1号

海盗什么也得不到。由于他自己肯定为这

个方案投赞成票,这样就占了总数的

50%,因此方案获得通过。

现在加上3号海盗。1号海盗知道,

如果3号的方案被否决,那么最后将只剩

2个海盗,而1号将肯定一无所获——此

外,3号也明白1号了解这一形势。因

此,只要3号的分配方案给1号一点甜头

使他不至于空手而归,那么不论3号提出

什么样的分配方案,1号都将投赞成票。

因此3号需要分出尽可能少的一点金子来

贿赂1号海盗,这样就有了下面的分配方

案: 3号海盗分得99块金子,2号海盗一

无所获,1号海盗得1块金子。

4号海盗的策略也差不多。他需要有

50%的支持票,因此同3号一样也需再找一

人做同党。他可以给同党的最低贿赂是1

块金子,而他可以用这块金子来收买2号

海盗。因为如果4号被否决而3号得以通

过,则2号将一文不名。因此,4号的分

配方案应是:99块金子归自己,3号一块

也得不到,2号得1块金子,1号也是一块

也得不到。

5号海盗的策略稍有不同。他需要收

买另两名海盗,因此至少得用2块金子来

贿赂,才能使自己的方案得到采纳。他的

分配方案应该是:98块金子归自己,1块

金子给3号,1块金子给1号。

这一分析过程可以照着上述思路继续

进行下去。每个分配方案都是唯一确定

的,它可以使提出该方案的海盗获得尽可

能多的金子,同时又保证该方案肯定能通

过。照这一模式进行下去,10号海盗提出

的方案将是96块金子归他所有,其他编号

为偶数的海盗各得1块金子,而编号为奇

数的海盗则什么也得不到。这就解决了10

名海盗的分配难题。

Omohundro的贡献是他把这一问题扩

大到有500名海盗的情形,即500名海盗

瓜分100块金子。显然,类似的规律依然

成立——至少是在一定范围内成立。事实

上,前面所述的规律直到第200号海盗都

成立。 200号海盗的方案将是:从1到

199号的所有奇数号的海盗都将一无所

获,而从2到198号的所有偶数号海盗将

各得1块金子,剩下的1块金子归200号

海盗自己所有。

乍看起来,这一论证方法到200号之

后将不再适用了,因为201号拿不出更多

的金子来收买其他海盗。但是即使分不到

金子,201号至少还希望自己不会被扔进

海里,因此他可以这样分配:给1到199

号的所有奇数号海盗每人1块金子,自己

一块也不要。

202号海盗同样别无选择,只能一块

金子都不要了——他必须把这100块金子

全部用来收买100名海盗,而且这100名

海盗还必须是那些按照201号方案将一无

所获的人。由于这样的海盗有101名,因

此202号的方案将不再是唯一的——贿赂

方案有101种。

203号海盗必须获得102张赞成票,

但他显然没有足够的金子去收买101名同

伙。因此,无论提出什么样的分配方案,

他都注定会被扔到海里去喂鱼。不过,尽

管203号命中注定死路一条,但并不是说

他在游戏进程中不起任何作用。相反,204

号现在知道,203号为了能保住性命,就

必须避免由他自己来提出分配方案这么一

种局面,所以无论204号海盗提出什么样

的方案,203号都一定会投赞成票。这样

204号海盗总算侥幸拣到一条命:他可以

得到他自己的1票、203号的1票、以及

另外100名收买的海盗的赞成票,刚好达

到保命所需的50%。获得金子的海盗,必

属于根据202号方案肯定将一无所获的那

101名海盗之列。

205号海盗的命运又如何呢?他可没

有这样走运了。他不能指望203号和204

号支持他的方案,因为如果他们投票反对

205号方案,就可以幸灾乐祸地看到205

号被扔到海里去喂鱼,而他们自己的性命

却仍然能够保全。这样,无论205号海盗

提出什么方案都必死无疑。206号海盗也

是如此——他肯定可以得到205号的支

持,但这不足以救他一命。类似地,207

号海盗需要104张赞成票——除了他收买

的100张赞成票以及他自己的1张赞成票

之外,他还需3张赞成票才能免于一死。

他可以获得205号和206号的支持,但还

差一张票却是无论如何也弄不到了,因此

207号海盗的命运也是下海喂鱼。

208号又时来运转了。他需要104张

赞成票,而205、206、207号都会支持

他,加上他自己一票及收买的100票,他

得以过关保命。获得他贿赂的必属于那些

根据204号方案肯定将一无所获的人(候

选人包括2到200号中所有偶数号的海

盗、以及201、203、204号)。

现在可以看出一条新的、此后将一直

有效的规律:那些方案能过关的海盗(他

们的分配方案全都是把金子用来收买100

名同伙而自己一点都得不到)相隔的距离

越来越远,而在他们之间的海盗则无论提

什么样的方案都会被扔进海里——因此为

了保命,他们必会投票支持比他们厉害的

海盗提出的任何分配方案。得以避免葬身

鱼腹的海盗包括201、202、204、208、

216、232、264、328、456号,即其号码

等于200加2的某一方幂的海盗。

现在我们来看看哪些海盗是获得贿赂

的幸运儿。分配贿赂的方法是不唯一的,

其中一种方法是让201号海盗把贿赂分给

1到199号的所有奇数编号的海盗,让202

号分给2到200号的所有偶数编号的海

盗,然后是让204号贿赂奇数编号的海

盗,208号贿赂偶数编号的海盗,如此类

推,也就是轮流贿赂奇数编号和偶数编号

的海盗。

结论是:当500名海盗运用最优策略

来瓜分金子时,头44名海盗必死无疑,而

456号海盗则给从1到199号中所有奇数

编号的海盗每人分1块金子,问题就解决

了。由于这些海盗所实行的那种民主制

度,他们的事情就搞成了最厉害的一批海

盗多半都是下海喂鱼,不过有时他们也会

觉得自己很幸运——虽然分不到抢来的金

子,但总可以免于一死。只有最怯懦的

200名海盗有可能分得一份脏物,而他们

之中又只有一半的人能真正得到一块金

子,的确是怯懦者继承财富。

临床医学证明,数学建模可以有效的

抑制老年痴呆症、小儿麻痹症,以及

下肢血管静脉曲张。

TOP

Echo

3

#

发表于 2003-7-7 05:25 | 只看该作者

这么快就给出答案了啊~~~

实习记者

TOP

4

dcyu

发表于 2003-7-7 05:45 | 只看该作者

发信人: starfish(金盆洗手,退隐江湖), 信区: Algorithm. 本篇人

气: 35

#

小试牛刀

标 题: Re: 对海盗分金块的疑问

发信站: 南京大学小百合站 (Mon Mar 31 12:04:49 2003)

本帖改编自《科学美国人》杂志中Ian Stewart的《凶猛海盗的逻

辑》

海盗,大家听说过吧。这是一帮亡命之徒,在海上抢人钱财,夺人性

0

命,干的是刀头上舔血的营生。在我们的印象中,他们一般都瞎一只

眼,用条黑布或者讲究点的用个黑皮眼罩把坏眼遮上。他们还有在地

下埋宝的好习惯,而且总要画上一张藏宝图,以方便后人掘取。不过

大家是否知道,他们是世界上最民主的团体。参加海盗的都是桀骜不

驯的汉子,是不愿听人命令的,船上平时一切事都由投票解决。船长

0

的唯一特权,是有自己的一套餐具--可是在他不用时,其他海盗是

可以借来用的。船上的唯一惩罚,就是被丢到海里去喂鱼。

现在船上有若干个海盗,要分抢来的若干枚金币。自然,这样的问题

他们是由投票来解决的。投票的规则如下:先由最凶猛的海盗来提出

分配方案,然后大家一人一票表决,如果有50%或以上的海盗同意这

方案,那么就以此方案分配,如果少于50%的海盗同意,那么这个提

方案的海盗就将被丢到海里去喂鱼,然后由剩下的海盗中最凶猛的那

个海盗提出方案,依此类推。

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

1)每个海盗的凶猛性都不同,而且所有海盗都知道别人的凶猛性,也

就是说,每个海盗都知道自己和别人在这个提出方案的序列中的位

置。

另外,每个海盗的数学和逻辑都很好,而且很理智。最后,海盗间私

底下的交易是不存在的,因为海盗除了自己谁都不相信。

2)一枚金币是不能被分割的,不可以你半枚我半枚。

3)每个海盗当然不愿意自己被丢到海里去喂鱼,这是最重要的。

4)每个海盗当然希望自己能得到尽可能多的金币。

5)每个海盗都是现实主义者,如果在一个方案中他得到了1枚金币,

下一个方案中,他有两种可能,一种得到许多金币,一种得不到金

币,

他会同意目前这个方案,而不会有侥幸心理。总而言之,他们相信二

鸟在林,不如一鸟在手。

6)最后,每个海盗都很喜欢其他海盗被丢到海里去喂鱼。在不损害自

己利益的前提下,他会尽可能投票让自己的同伴喂鱼。

现在,如果有10个海盗要分100枚金币,将会怎样?

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

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

0

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

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枚。

0

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枚金币。正如《马太福音》

说:'温柔的人有福了,因为他们必承受地土!'

【 在 beareye 的大作中提到: 】

:

: 刚刚又看到了这个问题,有个疑问,我觉得这个问题不太严密。

: 简单起见设只有3个海盗A,B,C分100个金块,如果A提出按照

100,0,0分配应该

是可?.

: 因为如果海盗B不同意,那么海盗A被杀掉,但是B同样也是一块

都拿不到,而且

还有?.

: 的危险。

: 同样是1块金块都拿不到,一种情况没有危险,一种情况有被杀掉

的危险,如果

是你?.

: 择哪种?

--

凤凰台上凤凰游,凤去台空江自流。

吴宫花草埋幽径,晋代衣冠成古丘。

三山伴落青天外,二水中分白鹭洲。

总谓浮云能蔽日,长安不见使人愁。

/dcyu

TOP

whatperson

发表于 2003-7-7 18:02 | 只看该作者

楼上引用的文章都是"分配方案有50%或以上的人同意,方案通过

5

#

新生入学

";

而搂主的题是"分配方案有一半以上的人同意才通过"

我的分析是:

无论第四个人(4)提什么方案,第五个人(5)一定反对;这样,(4)为了保

命,一定同意(3)的任何方案;

所以,(3)的方案是3)--100,(4)--0,(5)--0;

这样,(2)只要给(4),(5)最少的好处,就能得到他们的支持(否则他们什

么也得不到),再加上自己有75%的人支持自己的方案;即(2)--98,(3)--

0,(4)--1,(5)--1;

(1)的方案必须再得到另外两个人的支持才能通过,(3)只要得到1颗宝

石就支持(1),(4)或(5)只要得到2颗宝石就支持(1);

所以,(1)的方案是(1)--97,(2)--0,(3)--1,(4)--2,(5)--0;或者是

(1)--97,(2)--0,(3)--1,(4)--0,(5)--2;

不知道大家同意我的分析么?讨论讨论

海盗分金——精选推荐

本文发布于:2024-03-30 23:47:58,感谢您对本站的认可!

本文链接:https://www.wtabcd.cn/zhishi/a/171181367861951.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

本文word下载地址:海盗分金——精选推荐.doc

本文 PDF 下载地址:海盗分金——精选推荐.pdf

上一篇:号的简单造句
下一篇:返回列表
标签:海盗   方案   分配
留言与评论(共有 0 条评论)
   
验证码:
推荐文章
排行榜
Copyright ©2019-2022 Comsenz Inc.Powered by © 实用文体写作网旗下知识大全大全栏目是一个全百科类宝库! 优秀范文|法律文书|专利查询|