There is always a bigger fish
icon2 Brain Storm | icon4 2010-11-03 17:04| icon338 Comments | 本文内容遵从CC版权协议 转载请注明出自matrix67.com

   

     Always A Bigger Fish 不但是电影情节中的经典桥段，也是各种恶搞的灵感来源——小鱼总是被大鱼吃掉，而大鱼上面总还有更大的鱼。久而久之，聪明的大鱼或许就不会去吃小鱼了，否则按照传统剧情，它身后会出现一条更大的鱼。一个有趣的问题出现了：倘若所有的鱼都是理性的，那会出现怎样的情况呢？
    让我们把问题重新叙述一下。假设有 n 条鱼，它们从小到大依次编号为 1, 2, …, n 。我们规定，吃鱼必须要严格按顺序执行。也就是说，大鱼只能吃比自己小一级的鱼，不能越级吃更小的鱼；并且只有等到第 i 条鱼吃了第 i - 1 条鱼后，第 i + 1 条鱼才能吃第 i 条鱼。第 1 条鱼则啥都不能吃，只有被吃的份儿。我们假设，如果有小鱼吃的话，大鱼肯定不会放过；但是，保全性命的优先级显然更高，在吃小鱼之前，大鱼得先保证自己不会被吃掉才行。假设每条鱼都是无限聪明的（并且它们也都知道这一点，并且它们也都知道它们知道这一点⋯⋯），那么第 1 条鱼能存活下来吗？


 
 
 
 
 
 
 
 
 
 
 
 
 
 

    答案或许有些出人意料：当 n 是奇数时，第 1 条鱼将会存活下来；当 n 是偶数时，第 2 条鱼将会吃掉第 1 条鱼。为了证明这一点，让我们来考虑一些简单的情况。当 n = 1 时，第 1 条鱼显然活得自由自在；当 n = 2 时，第 2 条鱼将会吃掉第 1 条鱼，因为第 2 条鱼是无敌的，它不用担心自己会被吃掉。当 n = 3 时，第 2 条鱼不能吃第 1 条鱼，否则情况将化为 n = 2 的情形，它将会被第 3 条鱼吃掉。有趣的事情发生在 n = 4 的时候，此时第 2 条鱼可以大胆地吃掉第 1 条鱼，因为根据前面的结论，它知道第 3 条鱼是不会吃它的⋯⋯以此类推，当 n 是奇数时，这 n 条鱼将会和平相处；当 n 是偶数时，第 1 条鱼将会被第 2 条鱼吃掉，情况就化为了 n 为奇数时的稳定状态。

Posted in Brain Storm
Tags: , ,
Trackback: http://www.matrix67.com/blog/archives/3885/trackback
我猜您可能还喜欢：

38 条回复

  • 楼层: 沙发 | 2010-11-03 17:08 | Lutis 说：

    出乎意料。。

  • 楼层: 板凳 | 2010-11-03 17:54 | daoyuan2012 说：

    错了，只要n>=3，第一条鱼就是安全的吧

  • 楼层: 地毯 | 2010-11-03 18:23 | Amber13 说：

    你記得麼？有個拿硬幣的不拿到最後一個的題就是直接這樣判斷人數了。記不清了啊TAT。。。

  • 楼层: 地板 | 2010-11-03 18:52 | Bruno 说：

    果然还是博弈论啊。。

  • 楼层: 地下室 | 2010-11-03 19:21 | b4283 说：

    不知道為啥我的 comment 顯示不出來，系統是不是有問題啊？
    http://paste.pocoo.org/show/285438/

  • 楼层: 地基 | 2010-11-03 20:34 | Shawphy 说：

    我想起了海盗分赃的问题呢

  • 楼层: 地壳 | 2010-11-03 20:47 | darkraven 说：

    就是n,n-2,n-4....的鱼能存活嘛= =

  • 楼层: 地幔 | 2010-11-03 21:04 | P.K. 说：

    果然很海盗分赃很像

  • 楼层: 地核 | 2010-11-03 21:27 | lxm 说：

    果然，在“我猜您可能还喜欢”里给出了海盗分金.....

  • 楼层: 10楼 | 2010-11-03 21:37 | zjj 说：

    囧了
    看到下面广告的图表还以为是这道题的

  • 楼层: 11楼 | 2010-11-03 22:08 | Tweets that mention Matrix67: My Blog » Blog Archive » There is always a bigger fish -- Topsy.com 说：

    [...] This post was mentioned on Twitter by Leo Du and 阳阳猪的 GR Share, 大巨傻. 大巨傻 said: [GR share] There is always a bigger fish: Always A Bigger Fish 不但是电影情节中的经典桥段，也是各种恶搞的灵感来源——小鱼总… http://goo.gl/fb/nRWbL [...]

  • 楼层: 12楼 | 2010-11-03 22:35 | clover 说：

    有趣有趣！终于能看懂了！

  • 楼层: 12a楼 | 2010-11-03 23:20 | cat.s 说：

    字好模糊。。

  • 楼层: 14楼 | 2010-11-04 0:28 | nova 说：

    第一次在看到答案前想到解啊，而且还是在喝完酒后，真难得啊~

  • 楼层: 15楼 | 2010-11-04 4:13 | tpang 说：

    当n>=5的时候不成立吧。。。最小的不会被吃掉的吧。。

  • 楼层: 16楼 | 2010-11-04 5:19 | 亦草亦木 说：

    这个归纳法略显犀利了。。。所有的情况都可以归结为n=1，2，3.

  • 楼层: 17楼 | 2010-11-04 11:37 | foreverswz 说：

    第n条鱼吃了n-1条后，不就可以吃n-2了么。。

  • 楼层: 18楼 | 2010-11-04 12:51 | cgy4ever 说：

    原来答案这么简洁……
    这个归纳的确用的很神奇。

  • 楼层: 19楼 | 2010-11-04 18:22 | biohu 说：

    强盗分金简化版

  • 楼层: 20楼 | 2010-11-04 20:09 | 七匹狼 说：

    我也是想起了海盗分钻石

  • 楼层: 21楼 | 2010-11-04 20:59 | NULL 说：

    我也觉得只要n>=3，第一条鱼就是安全的吧

  • 楼层: 22楼 | 2010-11-04 21:55 | morrowind 说：

    第n-1条鱼不敢吃第n-2条鱼，所以n-2只要有机会一定吃n-3
    类推下来，第n-i条鱼不敢吃n-(i-1)，当i为奇数的时候
    n-(i-1)=1，就有n=i为奇数时，和平。

  • 楼层: 23楼 | 2010-11-04 22:47 | lumos 说：

    无非就是海盗分金问题嘛~~

  • 楼层: 24楼 | 2010-11-05 17:09 | 凹凸曼的马甲 说：

    是从n到1考虑的吧

  • 楼层: 25楼 | 2010-11-05 21:17 | Firm 说：

    汗，还蛮难的。。

  • 楼层: 26楼 | 2010-11-05 21:28 | 单阔 说：

    还可以学点知识
    有空经常来

  • 楼层: 27楼 | 2010-11-05 22:14 | 白左 说：

    参见很久以前科幻世界一片封面故事，捕猎滑豚的文……

  • 楼层: 28楼 | 2010-11-08 15:30 | joy 说：

    哈哈，一看就知道是海盗分金问题的变体版～

  • 楼层: 29楼 | 2010-11-11 14:47 | maomao 说：

    1=不被吃
    0=被吃
    1
    01
    101
    0101
    10101
    010101
    .
    .
    .

  • 楼层: 30楼 | 2010-11-11 22:23 | yangff 说：

    n=2
    n=3杯具
    n=4
    n=5/n-1吃掉n转化成n=4
    n=6
    n=7/n-1吃掉n转化成n=6
    ……

  • 楼层: 31楼 | 2010-11-13 9:18 | jizhouli 说：

    29楼maomao表述很简练。
    在吃掉前者的情况下，最后一个肯定是安全的，往前面走依次交替为
    n=安全.
    n-1=不安全.
    n-2=安全.
    n-3=不安全
    ... ...
    2=?
    即为问题的解，若n=2为安全，则n=1被吃掉；否则，没有鱼被吃掉。然后进入稳定状态。

  • 楼层: 32楼 | 2010-11-13 21:11 | whisky67 说：

    于是黑暗森林和猜忌链？

    文明A看到文明B。 A比B强。A要虐B，根据黑暗森林理论。B大吼：你敢灭我？我就把你位置暴露出去…。宇宙这么大总有一个文明能灭你的……

  • 楼层: 33楼 | 2010-11-30 10:14 | william H.Wei 说：

    为什么B就一定有机会把A暴露出去？ A 如果真的比 B 强，或许B连吼的机会都没有。。。。

  • 楼层: 34楼 | 2010-12-14 20:28 | franciszero 说：

    这是一个递归啊，所有提出质疑不相信递归的朋友们就请顺着作者的思路递归下去吧，递归会解除你们的质疑的。（每个成长的队列都有前面确定的队列内关系做基础的）

  • 楼层: 35楼 | 2010-12-16 3:19 | 柏 说：

    这是博弈的问题。本文中递归的条件并没有体现出“足够的聪明”。或者说，在这个博弈中并不存在一个可被明确定义的“无限聪明”。。

  • 楼层: 36楼 | 2011-06-24 10:05 | QuarterGeek » 趣题：海盗分金 说：

    [...] 受到Matrix67大牛上次那篇There is always a bigger fish的影响，看到海盗分金总是想进行状态转化，于是设海盗数量为n，从1开始推：（设Mi为第i个海盗分到的金币数量） [...]

  • 楼层: 37楼 | 2011-08-11 14:18 | orbea jersey 说：

    让人意想不到。。

  • 楼层: 38楼 | 2012-01-05 9:02 | 趣题：海盗分金 | QuarterGeek 说：

    [...] 受到Matrix67大牛上次那篇There is always a bigger fish的影响，看到海盗分金总是想进行状态转化，于是设海盗数量为n，从1开始推：（设Mi为第i个海盗分到的金币数量） [...]

您也随便说几句吧：

您可以在 Gravatar 设置您的头像。