Tag Archives for

海盗的难题

数学的逻辑有时会导致看来十分怪异的结论。一般的规则是,如果逻辑推理没有漏洞,那么结论就必定站得住脚,即使它与你的直觉矛盾。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名海盗有可能分得一份脏物,而他们之中又只有一半的人能真正得到一块金子,的确是怯懦者继承财富。

寻找真理的蟑螂

有一只聪明的蟑螂决定要去寻找真理,它的视野不超过1cm。真理位于一个同其距离Dcm的点上。蟑螂可以迈步,每步之长不大于1cm,每步之后,都会有人告诉它,究竟是离真理近了还是远了。蟑螂能够记住一切,包括自己所迈过的步子的方向。证明,它只需迈出不多于3D/2+7步,即可找到真理。

解:蟑螂可先试探性地向东、南、西、北迈出1步(每次迈出后回到原地再迈下1步),于是不超出7步,蟑螂就可以查明,“真理”位于四个正方形中的哪一个,然后,再沿着平行于这个正方形的方向走,所走的步子不超过D (2)^(1/2)<3D/2,即可找到真理。

选举总统

在密朗弗洛斯总统统治的国家安丘林中,新总统的选期临近了,国内有两千万个选民,其中只有占人口百分之一的正规军支持原总统,密朗弗洛斯想继续当总统,但另一方面,他也想使选举成为“民主的”,密朗弗洛斯这样来安排“民主选举”:选把全体选民分成人数相同的大组;其中的每一个大组又再分为若干个人数相同的组,但从不同的大组可以分出不同数量的较小的组;然后这些组继续被分划,如此等等,在最终所分成的那些组内选出小组代表——参加较大组选举的复选人,复选人在这个较大组中选举参加更大一组选举的复选人,如此等等,最后同,最大组的代表真选总统。密朗弗洛斯按自己的意愿将选举人分组,并指示他的拥护者们该如何参与选举。试问,他能通过这样的操纵来使自己当选吗?(在每一个组中,选举人按简单多数选出代表,而在舆论方面,反对派占优势。)

答案是能够的,事实上,总统的支持者共有200000人,假若最小的组由5个人组成,为了使总统能取胜,在一些小组中他的支持者该有3名。这样一来,200000个支持者(如果正解的分派他们)可在产生出的总数为4百万人的第一阶段复选人中占66666个,若再将这4百万人每4人分成一组,同为了在小组中占有多数就必须有3票,于是密朗弗洛斯可在产生的总数为1百万的第二阶段复选人中占有22222个支持者。按着划分小组可按5人一组,也可以按4 人一组(次序无关紧要),他可获得200000票中的7407票,50000票中的2469票,10000票中的823票,2000票中的274票, 500票中的91票,100票中的30票,25票中的10票,4票中的3票,从而保证自己当选。

现在也也请你再想一下,如果他的拥护者恰为164025(3^8 x 5^2)个 ,那么能否取胜?

改为单行道

尼基托夫城的道路均可双向行车,现决定在两年内全部翻修道路,为此在第一年中,有些道路线成为单行线;到了第二年,这些道路恢复双向行车,其余的道路则限制为单向行车线。现知,在翻修过程中任何时刻,都能从城市中的任何一个地点驱车前往另外任何地点。证明,可将基托夫城中的道路全部改为单行线,使得仍可由城中任一地点驱车前往另外任何地点。

证:首先将第一年修路时作为单行线的道路及其指定的单向行车方向确定下来;将这些道路染为红色,并标上原来的箭头。

我们再来分两个阶段解答问题。在第一阶段中,我们来增加红色道路的数目,并为它们标上箭头,使得在增加了它们以后,题目中的条件仍可满足,真到达到了如下程度时,我们就停止增加新的红色道路:即对任意两个用由A指向B的红色箭头直接连接的路口A和B,又都存在仅仅沿着红色箭头头即可由B到A的路径(即存在由红色箭头构成的环路)。在第二阶段中,我们来给出满足题目条件的道路走向,从而最终完成证明过程。具体作法如下:

第一阶段:设路口A和B已用红色箭头A→B连接,但由B至A却没有用红色道路。即在任何由B通向A的路径上,并不都具有红色箭头,亦即存在“空”路段。我们来任意取出一条由B至A的路段。在这条路径所包含的所有红色路段上,所标示的方向显然都与箭头A→B一致(因为由B至A有这条路径作为通道);我们只要照此(即与箭头A→B一致的方向)将“空路段”标定方向并染为红色,就可使得由B能沿着红色箭头走到A了。由于城市道路的数量是有限的。所以在若干步以后,我们就得到了许多由红箭头构成的环路,亦即许多由红色环路围成的“小岛”。

第二阶段:我们再将未包含在红色环路中的路段都染上绿色;在这些路段上目前都还存在着两个方向。但由于它们都是第二年修路时的单行线,于是我们可为每一段绿色道路都标上一个箭头,使之与第二年修路时所标的方向一样,这样一来,全城的道路都已标定了行车方向。

下面就来证明,按着所引入的方向,都可以沿着道路由任意一个路口A到达任一另外一个路口B。事实上,如果取这样一条由A至B的路段,使它恰是第二年修路时所走过的,那么现在在它上面就可能会有红色箭头也有绿色箭头。沿着绿色箭头,我们总是去往应去的方向,但沿着红色箭头却未必总是如此。例如,在我们所取的路径A…XY…B中的路段XY上,所标的红色箭头是由Y指向X的(即不能沿着路段XY通行),那么我们就可以沿着那样一条补上箭头Y→X后就成为第一阶段所构造的的红色环路的路径由X走到Y,由此所得到的由A至B的路径即为所求。

运输问题

现代商业社会中,物流运输是个不可缺少的环节。低成本和高效率是现代物流公司的主要目标。举个例子来说,现在许多学生早餐要喝鲜牛奶,而鲜牛奶这种商品从加工生产到完成销售所用的周期不能很长,所以生产商为了追求生产规模化和利润最大化,必须减少运输时间,节约成本。

假设,上海光明乳品厂要将一批鲜牛奶从上海运往外地,运输的参考数据如下表:
运输工具 运输速度{千米/时} 运输费用{元/千米} 装卸时间{小时} 装卸费用{元}
汽车 60 10 2 1000
火车 120 5 4 2000
飞机 300 20 2 100

若这批牛奶在运输过程中损耗为300元/时,那么应该采用哪种运输工具呢?

不妨设两地间距离为S千米,则采用三种运输工具的费用的时间如下表:
运输工具 总时间{小时} 总费用{元}
汽车 S/60+2 Q1=15S+1600
火车 S/120+4 Q2=7.5S+3200
飞机 S/300+2 Q3=21S+1600

计算得出,当两地间距离小于213千米时,汽车的运输费用比火车和飞机的都低,应该考虑用汽车运输;当两地间距离大于213千米时,火车的费用比汽车和飞机的都低,应该考虑用火车运输/当然如果牛奶在运输过程中的损耗增大,飞机就可能成本最佳的运输工具了。你可以自己计算一下,满足Q3

问题:某运输公司分配给一辆特种运输车的任务是从公司所在地S出发,将位于Ai的货物分别运送到Bi,最后将车开回公司,运输过程中货物不能装混。假定各点的位置可以用平面直角坐标{单位:千米}分别表示为S(5.00,5.00), A1(0.50,2.00),A2(7.57,2.01),A3(4.72,6.24),B1(8.38,4.50),B2(1.41,5.50),B3 (6.24,4.50),并规定任意两点Xi和Yi间的距离为|Xj - Xi| + |Yj - Yi|,试问该车如何安排,才能使行驶的总路程最短?

风险决策问题

一花店进几月生意越来越好,可是老板却为每天的进货量而愁眉苦脸,因为鲜花的进货价是2.5/束,正常销售价为5元/束,可是如果不能正常出售,就得以1.5元/束的价格处理掉,鲜花是不能积压的。如果这家花店每天销售200、300、400、500束鲜花的可能性分别为20%、40%、20%、20%,那么这家鲜花店每天应该进多少束花才能利益最大化?

其实这是一个风险决策问题。对带有随机性的客观状况的决策称为风险决策,而风险决策是以效益的期望值为决策依据的。

若这家花店进200束,则一定能卖出,那利润的期望值为L1 = 200 × 2.5 = 500元;若进货量为300束,刚有20%的可能只卖出200只,有80%的可能都卖出,那么利润的期望值为L2 = 0.2 × ( 200 × 2.5 - 100 × 1 ) + 0.8 × 300 × 2.5 = 680元;若进货400束,那么利润的期望值为L3 = 0.2 × (200 × 2.5 - 200 × 1) + 0.4 × ( 300 × 2.5 - 200 × 1) + 0.4 × ( 400 × 2.5 ) = 720元;若进货500束,则有20%的可能只卖出200束,40%的可能卖出300束,有20%的可能卖出400束,20%的可能都卖出,那么利润的期望值为L4 = 0.2 × (200 × 2.5 - 300 × 1) + 0.4 × ( 300 × 2.5 - 200 × 1) + 0.4 × ( 400 × 2.5 - 100 × 1) + 0.2 × ( 500 × 2.5 ) = 690元。

通过上面的计算,我们可以得出,当每天进货400束时,利润的期望值最大,所以这家花店的进货量为400束最好。

现在,我们有一家面包房每天卖出100、150、200、250、300只面包的可能性分别为20%、25%、30%、15%和10%。每只面包的成本为2元,销售价为4元,若当天不能售完,就以每只1元的价格处理,请问面包房生产多少只面包(生产量必须是100、150、200、250、300这五个数中的任何一个)才能获得最大利润?

  • 最新日志

  • RSS PANTAO.NAME

  • 最新评论

  • 标签