QQ登录

只需一步,快速开始

 找回密码
 注册

QQ登录

只需一步,快速开始

查看: 4773|回复: 23

一个很有意思的数学题

[复制链接]
发表于 2003-8-24 23:52:49 | 显示全部楼层 |阅读模式
       在网上看到一个数学题:
有10个海盗抢了100块金子,决定分配。为公平,决定采用以下办法:由最强的海盗提出分配办法,如果50%的人同意,就按这个办法分配,否则,提出分配办法的海盗将会被丢进海里.然后由次强的海盗提出办法......,依此类推,假设没有两个海盗一样强大。请问,怎样分配才能使最强的海盗得到最大的利益。
      
发表于 2003-8-25 08:37:16 | 显示全部楼层
最强的:把最弱的丢进海里去!这样我们可以得到更多的银子。
递推

呵呵!答案是不是这个呀!
回复

使用道具 举报

发表于 2003-8-25 09:39:48 | 显示全部楼层
[quote:a37cd60957="furk"]最强的:把最弱的丢进海里去!这样我们可以得到更多的银子。
递推
[/quote]

前提是,除了那个最强的其他海盗都是超级无敌大笨蛋!
回复

使用道具 举报

 楼主| 发表于 2003-8-25 09:40:46 | 显示全部楼层
这是个数学题,并且你这样做会被丢到海里去的——比你弱的人人自危,并且个个都比你弱。还有,你并未提出分配黄金的办法。
回复

使用道具 举报

 楼主| 发表于 2003-8-25 09:42:21 | 显示全部楼层
如果10个人都回答错误,我就给出答案。
回复

使用道具 举报

发表于 2003-8-25 12:41:21 | 显示全部楼层
每人十块~平均分~他们要是不同意,就给他们将马列主义~告诉他们:公产主义是我们不懈的追求……(落水声…………)
回复

使用道具 举报

 楼主| 发表于 2003-8-25 17:10:21 | 显示全部楼层
[quote:c6ca3c8e6c="默难"]每人十块~平均分~他们要是不同意,就给他们将马列主义~告诉他们:公产主义是我们不懈的追求……(落水声…………)[/quote]
你的结论很对。如果他们能够接受这些主义,就不用去做强盗了!
哈哈哈哈........
回复

使用道具 举报

发表于 2003-8-26 10:46:13 | 显示全部楼层
不一定嘛~~梁山好汉们不就是有福同享有难同当的简单的共产主义实践者嘛~~他们从理论上讲也是强盗嘛~~
或者这样:最强的海盗说:谁能在水底憋气呆上三天,那这金子就全给他~然后…… (扑通~~落水声……………………)
回复

使用道具 举报

发表于 2003-8-26 16:20:34 | 显示全部楼层
96  0  1  0  1  0  1  0   1  0
回复

使用道具 举报

发表于 2003-8-26 19:13:25 | 显示全部楼层
啊??是这样嘛??我觉得……又有一个人要落水啦…………
回复

使用道具 举报

发表于 2003-8-26 20:34:33 | 显示全部楼层
最强的海盗说:由最弱的海盗来分配金子。
回复

使用道具 举报

 楼主| 发表于 2003-8-26 21:27:41 | 显示全部楼层
我申明一下:这是个数学题。给点提示:使用递归法求解。
回复

使用道具 举报

 楼主| 发表于 2003-8-26 21:31:48 | 显示全部楼层
[quote:61210b0f2e="cxx"]96  0  1  0  1  0  1  0   1  0[/quote]
这个答案是正确的,不过没有解释为什么,大家还可以考虑一下。
回复

使用道具 举报

发表于 2003-8-27 09:21:58 | 显示全部楼层
本帖改编自《科学美国人》杂志中Ian Stewart的《凶猛海盗的逻辑》

海盗,大家听说过吧。这是一帮亡命之徒,在海上抢人钱财,夺人性
命,干的是刀头上舔血的营生。在我们的印象中,他们一般都瞎一只
眼,用条黑布或者讲究点的用个黑皮眼罩把坏眼遮上。他们还有在地
下埋宝的好习惯,而且总要画上一张藏宝图,以方便后人掘取。不过
大家是否知道,他们是世界上最民主的团体。参加海盗的都是桀骜不
驯的汉子,是不愿听人命令的,船上平时一切事都由投票解决。船长
的唯一特权,是有自己的一套餐具--可是在他不用时,其他海盗是
可以借来用的。船上的唯一惩罚,就是被丢到海里去喂鱼。

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

我们先要对海盗们作一些假设。
1)每个海盗的凶猛性都不同,而且所有海盗都知道别人的凶猛性,也
就是说,每个海盗都知道自己和别人在这个提出方案的序列中的位置。
另外,每个海盗的数学和逻辑都很好,而且很理智。最后,海盗间私
底下的交易是不存在的,因为海盗除了自己谁都不相信。
2)一枚金币是不能被分割的,不可以你半枚我半枚。
3)每个海盗当然不愿意自己被丢到海里去喂鱼,这是最重要的。
4)每个海盗当然希望自己能得到尽可能多的金币。
5)每个海盗都是现实主义者,如果在一个方案中他得到了1枚金币,而
下一个方案中,他有两种可能,一种得到许多金币,一种得不到金币,
他会同意目前这个方案,而不会有侥幸心理。总而言之,他们相信二
鸟在林,不如一鸟在手。
6)最后,每个海盗都很喜欢其他海盗被丢到海里去喂鱼。在不损害自
己利益的前提下,他会尽可能投票让自己的同伴喂鱼。

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

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

以这个思路,先考虑只有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-8-27 15:56:24 | 显示全部楼层
如果要求超过50%得,那你的分析方法就不实用了。如果只剩下p1,p2,p2就会把p1扔下海。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

GMT+8, 2024-11-9 10:26 , Processed in 0.047955 second(s), 15 queries .

© 2021 Powered by Discuz! X3.5.

快速回复 返回顶部 返回列表