海盗分金币问题的逻辑推理与延伸归纳优秀奖

1、“海盗分金币”问题的逻辑推理与延伸归纳（A类）北京化工大学理学院 李晓琼摘要：“海盗分金币”问题是一个典型的博弈类问题。本文通过对此问题的逻辑推理给出答案，并在此基础上做了延伸讨论，同时分析了在改变某一条件后的另一问题。关键词：海盗分金币；博弈；逻辑；推理1.背景五个海盗抢到了 100枚金币，他们决定这么分：1 .抽签决定自己的号码 ：5 4 3 2 1;2 .首先，由5号提出分配方案，然后5人共同进行表决，如果有半数或半数以上人同意时，就按照他的提案进行分配，否则 5号将被扔入大海喂鲨鱼；3 .在5号死后，由4号提出分配方案，然后4人进行表决，如果有半数或半数以上人同意时，就按照他的提案进行

2、分配，否则 4号将被扔入大海喂鲨鱼；4 .以次类推。海盗们基于三个因素来做决定：1 .要能存活下来；2 .自己得到的利益最大化；3 .在所有其他条件相同的情况下，优先选择把别人扔出船外。问题：第一个提出分配方案的海盗怎样分配才能够使自己免于下海且获得最多金 币？3.1, 分析1）假设只有2号与1号两个人来分配，则2号为了自己利益最大化会提出占有 全部金币，而1号无论赞同与反对都不会得到金币。1号为使自己利益的最大化， 会保全3号的生命以求得到金币。2号的决策是：海盗名称：2 1得金币数：100 02）假设由3, 2, 1号三人来分配，则1号只要能得到一枚金币就一定会支持 3 号的方案。3号会做

3、出这样的分配方案，自己得 99枚金币，1号得1枚金币，而 无论2号赞同与反对都不会得到金币，所以2号会保全4号的生命以求得到金币。3号的决策是：海盗名称：3 211 / 10得金币数：99 0 3）假设由4, 3, 2, 1号四个人来分配，4号所提出的方案只要得到其他三人中 的任意一人的支持就能保全自身，同时利益最大。由上一步分析，除非 4号分 100枚金币给3号，否则就不能确定得到3号的支持。4号为了利益最大化，他 只要得到2, 1号至少一人的支持就能保证自己不被处死，且他只需支付一个人 金币。如果4号选1号为同盟者，则他需要支付至少2枚金币才能得到1号的绝对支持 （因为1号赞成4号的决定只

4、能得到1枚金币，反对4号的决定也可以得到3号 分配的1枚金币）。如果4号选2号为同盟者，则他只需要支付 2号一枚金币就 能取得他的支持，因为在上一步分析中 2号没有得到金币。4号的决策是：海盗名称：4 3 21得金币数：98002或海盗名称：4 3 21得金币数：99010为求自身利益的最大化，4号会选择与2号结为同盟，即：海盗名称：4 3 21得金币数：990104）假设1、2、3、4、5号共同参与表决，由5号提出分配方案。5号需要获得 其余四人当中至少两人的支持。由上一步分析，如果由4号分配，4号最多可获得99枚金币。若5号选择与4号结盟，即使给4号99枚，仍无法保证得到4号 支持，若给4

5、号100枚金币，则5号的分配方案不能通过（因为没有足够的金币 分给其他人），所以，5号会先放弃与4号结盟的想法，即不分金币给 4号。继续上一步分析，如果由4号分配，若4号选择利益最大化，则3号与1号得不 到金币，所以，5号给3号与1号每人1枚金币就能获得两人的绝对支持，其分 配方案也能通过。5号的决策是：海盗名称：5 4 3 2 1得金币数：98 0 1 0 13.2, 延伸如果海盗的数目不止5个而金币只有100枚。继续按照这个逻辑推理，6号 的决策将是：海盗名称6 5 4 3 2 1得金币数：98 0 1 0 1 02 / 10再继续推理，得1200号的决策，如下表:表1如果有201个海盗，

6、那么201号只有把自己手中的金币全分出去，即给每海盗 名称 决策 者12345198199200个奇数编12310001001099010101010101010号（199,197,，3,14519819920099, , , ,098102010110101的海盗一个金币，这样201号就能获得超过一半人数的支持，201号也就能活着202号也只能把这100个金币全部贿赂给其他100个海盗，这100个海盗必 须是在201号分配时什么也得不到的海盗（即偶数编号的海盗与 201号中的100 个人），这样202号就能获得刚好一半人数的支持，202号也能活着了。202号100有C1。1种分配方法，其中一

7、种如下表：表2海盗名称12345198199200201202得金币数0001010110202 号可以分金币给201号，是因为由201号分配时，201号得不到金币, 当202号分金币给201号时，201号必然会赞成。而一种特殊的分配方法是：给 1 200号中的偶数编号的海盗每人一枚金币。对于203号，由于人数众多，203号没有足够的金币分给其他海盗以获得足 够的支持（他需要至少102人的支持，包括他自己），所以不论203号怎么分配,3 / 10决策都不会通过204号会分析，203号为了活着不论204号如何分配，203号都会支持（即204号得到203号的无偿支持），所以204号可以凭自己的一票

8、，203号的一票100和另外100个海盗（即奇数编号的海盗）的票正好获得50%勺支持。204号有C101 种分配方法，其中一种如下表：表3海盗名称123456198199200201202203204得金币数0010100100100204号可以分金币给202号，是因为由202号分配时，202号得不到金币， 当204号分金币给202号，202号必然会赞成。而一种特殊的分配方法是：给 1 200号中的奇数编号的海盗每人一枚金币。205 号不能得到203号和204号的无偿支持，所以如果由205号分配，他的 方案也不会通过。206号也一样，尽管他能得到205号的无偿支持，但是还差一 票。207号需要

9、得到至少104个海盗的支持，所以即使有205,206号的无偿支持 也不够。208号也是需要得到104个海盗的支持，但是有205,206,207号的无偿支持， 加上自己的一票，再加上另外100个海盗（即偶数编号的海盗）的票数，总票数100是104票，刚好获得一半人的支持。208号有C103种分配方法，其中一种如下表：表4海盗名称1234199200201202203204205206207208得金币数00000110110000208号可以分金币给 201,203,204号，是因为由204号分配时,201,203,204 号得不到金币，当208号分金币给201,203,204号，201,203

10、,204号必然会赞成。 而一种特殊的分配方法是：给1 200号中的偶数编号的海盗每人一枚金币。1.3. 规律1.3.1. 决策海盗的编号4 / 10从201号之后，在每两个能够作出决策保住自己生命的海盗之间，存在着些无论如何决策都不会通过的海盗。而这些海盗会无偿支持在这之后的那个能够 做出决策保住自己生命的海盗。用数学来表达，设在201号之后，能够作出决策保住自己生命的海盗的编号所组成的数列为N(n)0则有：N(1)=202N(n)-N(n-1)+100=N(n)(2)(注：X表示大于等于X的最小整数)对于(2),若 N(n)是偶数，则 N(n)=2N(n-1)-200(3)若 N(n)是奇数

11、，则 N(n)=2N(n-1)-199(4)若N(n)是奇数，则N(n-1)是偶数，且N(n-1)比N(n)小1。这与“在每两个 能够作出决策保住自己生命的海盗之间存在着一些无论如何决策都不会通过的 海盗”的条件矛盾，所以舍去(4) o 由(1) (3)两式，得通解：N=200+2n(n=0,1,2,3)1.3.2. 决策种数对于能够作出决策保住自己生命的海盗，他们的决策种数如下表:表5海盗名策种数100100C101100C101100C103100C105100C111表6海盗名称n决策种数2021101100+12042101100+1120831

12、03100+332164105100+552325111100+11112646121100+21215 / 10100这些海盗可能的决策种数为 Cm ,对上表数据归纳，可得:M=101+4/3*（2n/4-1）（n为偶数且 n0）M=101+2/3*（2 n-1-1）（n为奇数且 n0）2 .改变条件若将“如果有半数或半数以上人同意时”改成“如果必须有半数以上人同意 时”，其余条件不变。2.1, 分析1）假设只有2号与1号两人来分配，则无论2号如何分配都不能确定可以获得 1号的支持。如果1号不支持，那么1号获得全部金币，所以2号会保全3号的 生命以求生存。2）假设有3, 2, 1号三人来分配

13、，则2号会无偿支持3号的决策。3号会给自 己100枚金币，1号反对也无效。3号的决策是：海盗名称：3 2 1 得金币数：100 003）假设有4, 3, 2, 1号四个人来分配，4号所提出的方案要得到其他三人中至 少两人的支持才能保全自身性命。由上一步分析，即使4号给3号100枚金币，4号的方案仍不能通过，所以他只有得到 2, 1号两人的支持才能保证自己的方 案通过。同时为了保证自己利益最大化，他给 2, 1号每人1枚金币。4号的决 策是： 海盗名称：4 3 2 1得金币数：9801 14）假设1、2、3、4、5号表决，则由5号提出分配方案。5号需要获得其余四人中至少两人的支持。由上一步分析，

14、如果由4号分配，4号最多可获得98枚6 / 10金币。若5号选择与4号结盟，即使给4号98枚，仍无法保证得到4号支持， 若给4号99或100枚金币，则5号的分配方案也不能通过（因为没有足够金币 给其余海盗用来获得支持），所以5号会先放弃与4号结盟的想法。继续上一步 分析，如果由4号分配，若4号选择利益最大化，则3号得不到金币，所以5号 给3号1枚金币，给1号或2号两枚金币（若只给1号或2号1枚金币或1, 2 号每人1枚金币，则不能确定能获得绝对支持）就能获得两个人的支持，其分配 方案就能通过，5号会获得97枚金币。5号的决策是： 海盗名称：5 4 3 2 1得金币数：97 0 1 0 2或海盗

15、名称：5 4 3 2 1得金币数：97 0 1 2 02.2, 延伸如果海盗的数目不止5个而金币只有100枚。假设1、2、3、4、5、6号共同参与表决，则由6号提出分配方案。6号需 要获得其余5人中至少3人的支持。6号必定得不到5号的支持，所以不分金币 给5号，给4号一枚金币即可得到4号的支持。对于1,2号，由于他们不能确定 5号是否会给自己两枚金币，所以 6号只须给1, 2号各一枚金币即可得到两人 的支持。6号的决策将是：海盗名称6 5 4 3 2 1得金币数：97 0 1 0 1 1*6 200号之间的偶数编号的海盗都采用与6号相似的决策*继续推理可得下表：表7191919 1910111

16、21314156789200海盗123456789名称101 0100103 0 004 110 987 / 1052010970210976110109772010109602101096811010109692010101095021010109510110101010951120101010109402101010109412110101010109413201010101010930210101010109314110101010101093152010101010101092021010101010109219 11010102619 2010101171191819 1101001

17、09200如表1,上表也有规律可循。从表中可以看出，一直到 199号都能通过分配 方案，而200号的分配方案不能通过。如果有201号，201号需要得到101人的支持。因为200号的方案不能通过， 所以201号可以得到200号的无偿支持。201号可以得到3-199号中所有奇数 编号的支持，即有99票，加上200号与自己的票，201号的方案可以通过，且100为了利益最大化，201号可以得到一枚金币。202号有C101种分配方法，其中一 种（即利益最大化的情况下）方案如下表：表8海盗名称123451981992002018 / 10得金币数001010101若由202号分配，则需要至少102票。20

18、2号无论怎么分配也不会得到102票。若由203号分配，则需要至少102票。203号会得到202的无偿支持，加上自己100与另外100个海盗，刚好102票。203号有C101种分配方法，其中一种如下表：表9海盗名称123456198199200201202203得金币数110101100000若由204, 205号分配，则至少需要103票。204,205号的分配无法通过。若由206号分配，则至少需要104票。206号的分配无法通过。若由207号分配，则至少需要104票。207号可以的到204,205,206号的无偿支100持，加上自己与另外100票，刚好可以通过。207号有C1。3种分配方法，其中一 种如下表：表10海盗名称1234199200201202203204205206207得金币数00101010000002.3. 规律：2.3.1. 决策