|
|
发表于 2005-10-3 12:21:29| 字数 2,540| - 中国–上海–上海 教育网/第二医药大学教育网
|
显示全部楼层
我要50nb嘿嘿
海盗的难题
数学的逻辑有时会导致看来十分怪异的结论。一般的规则是，如果逻辑推理没有漏洞，那么结论就必定站得住脚，即使它与你的直觉矛盾。 1998年9月，加利福尼亚州帕洛阿尔托的Stephen M. Omohundro寄给我一道难题，它恰好就属于这一类。这难题已经流传了至少十年，但是Omohundro对它作了改动，使它的逻辑问题变得分外复杂了。
先来看看此难题原先的形状。10名海盗抢得了窖藏的100块金子，并打算瓜分这些战利品。这是一些讲民主的海盗（当然是他们自己特有的民主），他们的习惯是按下面的方式进行分配：最厉害的一名海盗提出分配方案，然后所有的海盗（包括提出方案者本人）就此方案进行表决。如果50%或更多的海盗赞同此方案，此方案就获得通过并据此分配战利品。否则提出方案的海盗将被扔到海里，然后下提名最厉害的海盗又重复上述过程。
所有的海盗都乐于看到他们的一位同伙被扔进海里，不过，如果让他们选择的话，他们还是宁可得一笔现金。他们当然也不愿意自己被扔到海里。所有的海盗都是有理性的，而且知道其他的海盗也是有理性的。此外，没有两名海盗是同等厉害的——这些海盗按照完全由上到下的等级排好了座次，并且每个人都清楚自己和其他所有人的等级。这些金块不能再分，也不允许几名海盗共有金块，因为任何海盗都不相信他的同伙会遵守关于共享金块的安排。这是一伙每人都只为自己打算的海盗。
最凶的一名海盗应当提出什么样的分配方案才能使他获得最多的金子呢？
为方便起见，我们按照这些海盗的怯懦程度来给他们编号。最怯懦的海盗为1号海盗，次怯懦的海盗为2号海盗，如此类推。这样最厉害的海盗就应当得到最大的编号，在这样的编号提示下大家开始思考吧~~~~~~~~~~
海盗的难题参考答案及推广, 供大家参考。
如果两个人分，2号必将独吞所有金子。
3个人分，分法为1号-1，2号-0，3号-99，1号会同意3号的分法，否则将一无所获。
4个人分，分法为1号-0，2号-1，3号-0，4号-99，2号会同意4号的分法，否则将一无所获。
以此类推，10个人分，分法为1号-0，2号-1，3号-0，4号-1，5号-0，6号-1，7号-0，8号-1，9号-0，10号-96，2号、4号、6号、8号会同意10号的分法，否则将一无所获。
先公布一下标准答案，后面有一个推广。
分析所有这类策略游戏的奥妙就在于应当从结尾出发倒推回去。游戏结束时，你容易知道何种决策有利而何种决策不利。确定了这一点后，你就可以把它用到倒数第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块金子。大家接着思考一下怎么分？
500个海盗分100块金子，按照题意，结局很有点讽刺意味：较厉害的海盗反而要担心自己的生死，而较弱的海盗却能得到金子。第500个海盗无论怎样分都会死掉！
依次类推, 到第200 海盗, 他分偶数号每人一块金子, 即可以.
201, 分所有奇数号每人一块金子, 自己没有, 为了不被扔下海, 包括自己有101人同意.
202, 分所有偶数号每人一块金子, 自己没有, 为了不被扔下海, 包括自己有101人同意.
203, 即使分所有奇数号每人一块金子, 自己没有, 为了不被扔下海, 201, 202只能没有肯定幸灾乐祸, 包括自己也最多有101人同意. 分所有偶数号每人一块金子, 更没有几个人同意, 所以203 一定会被扔下海.
204, 分所有200 号一下奇数号每人一块金子, 201, 202肯定不同意, 203 为了保命一定会同意, 包括自己有102 人同意.
类推205, 206, 207, 一定会被扔下去.
但208不然, 分所有200 号一下偶数号每人一块金子, 因为205, 206, 207, 加上自己同意, 又可以达到104 人, 所以一定不被扔下海.
依次类推.
200 + 2 的N 次方的人可以活下来, 其它都被扔下去.
而从200号海盗开始，只有第2的N次方号+200海盗才能生还！
并且N=1,3,5,奇数的时候, 分金子给200 号一下, 偶数号的人,
N=2,4,6,偶数的时候, 分金子给200 号一下, 奇数号的人,
所以500时候, 只有到第200+256号时候, 大家才可以同意, 可以停止. |
|
[复制链接]
|自动提醒
狗仔卡
离线
提升卡
置顶卡
变色卡
