八达网

标题: 知乎上看到一个有意思的问题：到底是第 N 天有 N 个红眼睛自杀，还是什么都不会发... [打印本页]

作者: 喷火母鸡 时间: 2014-6-8 18:48
标题: 知乎上看到一个有意思的问题：到底是第 N 天有 N 个红眼睛自杀，还是什么都不会发...
此问题最早据说是澳大利亚的华裔数学神童陶哲轩在网上贴出来让大家思考，逗大家玩儿的。但却是真的把我难住了，一直百思不得其解。在此求教方家。
补题源：http://terrytao.wordpress.com/20 ... d-islanders-puzzle/
注：题源背景为蓝眼睛（100）、棕眼睛（900）。

题目是这样的。说一个岛上有100个人，其中有5个红眼睛，95个蓝眼睛。这个岛有三个奇怪的宗教规则。
1. 他们不能照镜子，不能看自己眼睛的颜色。
2. 他们不能告诉别人对方的眼睛是什么颜色。
3. 一旦有人知道了自己的眼睛颜色，他就必须在当天夜里自杀。（尊重博客原题，把原来的“知道自己是红眼睛”改成现在的“知道自己的眼睛颜色”）
注：虽然题设了有5个红眼睛，但岛民是不知道具体数字的。

某天，有个旅行者到了这个岛上。由于不知道这里的规矩，所以他在和全岛人一起狂欢的时候，不留神就说了一句话：【你们这里有红眼睛的人。】

最后的问题是：假设这个岛上的人足够聪明，每个人都可以做出缜密的逻辑推理。请问这个岛上将会发生什么？

此问题的第一个答案是用数学归纳法得出的：如果这个岛上有N个红眼睛，那么在旅行者说这句话的第N天，他们全部都会自杀。具体到本题则是，在第5天，这个岛上的5个红眼睛会全部自杀。（尊重原题，补：其他蓝眼睛在红眼睛集体自杀后，知道自己的眼睛颜色，也跟着自杀）。

证明过程如下：

如果这个岛上只有1个红眼睛，其他人都是蓝眼睛。那么，当旅行者说了这句话之后，此人立刻就会知道自己是红眼睛，他就会在当天自杀。即，当n取第一个值n0=1时，命题成立。

假设当这个岛上有N个红眼睛的时候，在旅行者说了这句话之后的第N天，这些红眼睛会全部自杀。

那么，当这个岛上有N+1个红眼睛的时候，在每个红眼睛看来，岛上都确定有N个红眼睛，并等待着他们在第N天自杀。而在第N天，大家都没有自杀。所以一到第N+1天，每个红眼睛都明白了这个岛上还有第N+1个红眼睛——他自己。于是大家都在第N+1天自杀了。

所以命题得证：如果这个岛上有N个红眼睛，那么在旅行者说这句话的第N天，他们全部都会自杀。

如果上述证明还让人有疑惑的话，也可以改用穷举法来证明。

当岛上只有一个红眼睛的时候，在旅行者说完这句话的当天，他就会自杀。这个无疑。

当岛上有两个红眼睛的时候。在旅行者说完这句话的当天，这两个红眼睛都在等着对方自杀，但对方却没有自杀。于是在第二天他们立刻明白了自己也是红眼睛，于是在第二天一起自杀了。

以此往下推理，当岛上有三个红眼睛的时候。旅行者说完这句话，每个红眼睛都在等着第二天另外两个红眼睛集体自杀，但他们没有自杀。所以到了第三天，大家都明白了自己也是红眼睛，就一起自杀了。

如此类推下去。就得出了命题：如果岛上有N个红眼睛，那么在旅行者说完这句话后的第N天，这个N个红眼睛会一起自杀。具体到本题就是，到了第五天，这五个红眼睛一起自杀。

以上证明看起来非常美妙。

可是可是可是可是可是可是。

陶哲轩说，这个旅行者事实上讲了一句废话，没有带来任何新的信息。因为这岛上有95个蓝眼睛，5个红眼睛。每个人都知道这岛上有红眼睛的人。无非是蓝眼睛的人看到有5个红眼睛，红眼睛的人看到有4个红眼睛而已。旅行者说的那句【岛上有红眼睛的人】，没有输入任何新的信息，他说的就是岛上的人每天都看到的景象。所以哪怕岛上的人思维再缜密严谨，也不会有任何自杀的情况发生。

从这个角度来说，也对呀。

这到底是怎么一回事，我迷茫了。请求方家解答疑惑。

「游客没有输入任何新的信息」这个断言是错的。

N=1的情形不必说了，显然输入了新信息。

对于N>1的情形，要注意，游客必须是当着所有人的面公开做出宣告，如果他是私下分别对每个人说的，就不会起任何作用。「公开宣告」这一举动的意义不是让每个人都知道「岛上有红眼睛」，而是让每个人都知道「每个人都知道每个人都知道……每个人都知道岛上有红眼睛」。在游客公开宣告之前，岛上的人是不可能具有这个多阶知识的，这就是游客输入的新信息。

以N=2为例，公开宣告之后，红1立刻获得了一个新的2阶知识：「红2知道岛上有红眼睛」，在公开宣告之前，他没有能力判断这个2阶命题的真假，因为在这之前命题的真假依赖于红1自己的眼睛颜色。同样，红2也获得了新知识「红1知道岛上有红眼睛」。

N=3时，公开宣告使得红1立刻获得了一个新的3阶知识：「红2知道红3知道岛上有红眼睛」，在此之前，这个3阶命题的真假也是依赖于红1自己的眼睛颜色（红则为真，蓝则为假）。同样，红2和红3也获得了类似的知识。

N=4,5,6,...依此类推。

简单说，「岛上有红眼睛」这件事本来只是一项「共有知识」（Mutual knowledge），公开宣告使它变成了一项「公共知识」（Common knowledge）。这两种知识的区分在认知逻辑里面非常重要，在博弈论中有广泛的应用。

用不严谨的话粗略介绍一下这两个概念：对于一个给定的命题P和一群给定的人，共有知识只需要满足一个条件：这群人中所有人都知道P，那么P就是这群人的共有知识。
公共知识则需要满足以下所有条件：
这群人中
1、所有人都知道P；
2、所有人都知道所有人都知道P；
3、所有人都知道所有人都知道所有人都知道P；
4、所有人都知道所有人都知道所有人都知道所有人都知道P；
5、……
一直下去，直到无穷。要同时满足这无穷多个条件，才能说P是这群人的公共知识。

========
看到有些人还是不明白为什么公开宣告之前没有人自杀，为什么宣告之后就会自杀了，以及为什么要等到第N天才自杀。以下就用N=4为例来分析一下，希望能有助于理解（但也有可能让人绕得更晕）。
设4个红眼岛民分别为A, B, C, D，以下是A心中做出的推理：
我看到3个红眼，这可以划分成一共5种情况：
1、我是红的；
2、我是蓝的，且B自认为是红的；
3、我是蓝的，且B自认为是蓝的，且B认为C自认为是红的；
4、我是蓝的，且B自认为是蓝的，且B认为C自认为是蓝的，且B认为C认为D自认为是红的；
5、我是蓝的，且B自认为是蓝的，且B认为C自认为是蓝的，且B认为C认为D自认为是蓝的。
假如没有游客来公开宣告「岛上有红眼」，那么A永远无法判断上述哪一种是真的。由于岛上所有人都做出同样的推理（蓝眼岛民推出的情形多一种），所以每个人都无法判断自己眼睛的颜色，大家都不用去死。
而一旦公开宣告「岛上有红眼」，A立刻知道「B知道C知道D知道岛上有红眼」，因此可以立刻排除5；当晚没人死，因此第二天可排除4；第三天排除3；第四天排除2只剩下1，因此A在第四天晚上自杀。B, C, D也都做出完全一样的推理，所以也都在第四天晚上自杀。

====补充====
有人提到，这道题的一个必要前提是岛上的人要完全信任这个游客。这很对，但还不够。不仅每个人都要相信该游客，而且还必须每个人都知道每个人都知道……每个人都知道每个人都相信该游客。即「游客完全可信」这件事本身也必须是一个公共知识。只有这样，游客的宣告才会具备使共有知识转变为公共知识的力量。

====补充2====
从小到大，我们一次又一次地被旁人这样教训：「嘘，别说了，小心点。况且这种事谁不知道啊，还要你说？说出来又有什么用呢？你有力量改变它吗？」久而久之，我们越来越习惯于把「你懂的……」挂在嘴边，习惯于对房间里的大象视而不见，选择性遗忘了一个我们其实早就知道的重要事实：「大声说出来」跟「彼此心照不宣」有着决定性的区别。我们不是没有力量。一条恰当的宣言，哪怕它的内容只不过是「我知道」这么简简单单的一句话，也有可能引起整个社会的信念结构的根本改变，让许许多多人断然行动起来。这就是我们每一个人的力量。

作者: Sophia 时间: 2014-6-8 18:53
提示: 作者被禁止或删除内容自动屏蔽

作者: 喷火母鸡 时间: 2014-6-8 19:29

Sophia 发表于 2014-6-8 18:53
某天，有个旅行者到了这个岛上。由于不知道这里的规矩，所以他在和全岛人一起狂欢的时候，不留神就说了一句 ...

当然知道啊，但是问题是请问这个岛上将会发生什么？

作者: qq87654321 时间: 2014-6-8 19:36
不是说不能说对方眼睛是啥颜色吗

作者: qq87654321 时间: 2014-6-8 19:38
因为之前都不能告诉对方眼睛啥颜色啊

作者: 黑友 时间: 2014-6-8 19:44
这问题不是早都有结论了吗？跟开枪的有本质问题？

作者: hysteria 时间: 2014-6-8 19:58

Sophia 发表于 2014-6-8 18:53
某天，有个旅行者到了这个岛上。由于不知道这里的规矩，所以他在和全岛人一起狂欢的时候，不留神就说了一句 ...

问题在于虽然每个人都知道红眼睛存在
但是他们并不确定别人“知道” 也就是他们不确定别人也看到了“红眼睛”
在只有1个红眼睛的时候你知道有，但是红眼睛本人不知道（因为他看到的都是蓝色）
在你本人是红眼睛的时候，是别人都知道，而你不知道

所以外人来是有意义的，意义在于让每个人都知道了红眼睛的存在（当红眼睛只有1个的时候，那个倒霉蛋一听就知道是自己了）

作者: hysteria 时间: 2014-6-8 19:58
出这题的得有多丧心病狂。。。。。

作者: SCI)_W_Y_W 时间: 2014-6-8 20:14
本帖最后由 SCI)_W_Y_W 于 2014-6-8 21:04 编辑

。。。

作者: 蜡笔小旧 时间: 2014-6-8 20:18
屁，没人知道有几个红眼睛，没有人告诉对方自己是红眼睛。就不会有人自杀。
因为，只要有人看到红眼，就会觉得自己不是红颜。只有当红眼是一个的时候才有人自杀！

作者: 小小白 时间: 2014-6-8 20:30
本帖最后由小小白于 2014-6-8 23:22 编辑

蜡笔小旧发表于 2014-6-8 20:18
屁，没人知道有几个红眼睛，没有人告诉对方自己是红眼睛。就不会有人自杀。
因为，只要有人看到红眼，就会 ...

。。。。。

作者: shicepku 时间: 2014-6-8 21:01
文章是正确的一个红眼的时候情况很简单
两个红颜的时候也不复杂既然第一天没有红眼自杀那么说明还有另外一个红眼
三个以上红眼情况开始复杂了但是正如文章写的那样如果每个人都知道每个人知道有红眼那么N天后就会知道自己是不是红眼
比如如果N=5 红眼a看起来有bcde四个红眼如果自己不是红眼的话那么会假设b的眼里只有3个红眼如果这样的话那么a会猜想如果b假设b自己不是红眼那么c眼里会有2个红眼（如果c假设c自己不是红眼的话）如此即可推到n天没人自杀那么上面的假设不成立自己是红眼

作者: shicepku 时间: 2014-6-8 21:13
或者用递归的思想
一喝红颜第一天就会死
两个红眼第二天发现对方没死就全自杀了
三个红眼每人看到有两个红眼会以为另两个人眼里都只有一个红眼那么第二天会都自杀但是到第二天没人自杀就说明了还有一个红眼就是自己于是三人都在第三天自杀了
四个红眼也是一样会以为其他三个红眼每人眼里有两个红眼套用上面的结论会在第三天同时自杀但实际情况却是每人眼里都是三个红眼在第三天都在等另三个人自杀所以第三天没人自杀于是到了第四天只看到三个红颜的人明白自己就是第四个红颜就四个都要自杀了
之后同理在n-1天没人自杀那么自己肯定是红眼所以n个红眼会在n天自杀其中 n-1为自己认为的红眼数 n为实际红眼数

作者: SCI)_W_Y_W 时间: 2014-6-8 21:19
楼上是对的。开始我想错了。

作者: [t.h]zhw 时间: 2014-6-8 21:23
现在这种无意义，同时又自以为显智商的题不看

作者: 我来自福州 时间: 2014-6-8 21:32
N+1天以后所有人知道自己蓝眼全自杀了？

作者: adunadam 时间: 2014-6-8 22:05
本来就相安无事，所以其实根本就没人会自杀。

作者: Sophia 时间: 2014-6-8 22:10
提示: 作者被禁止或删除内容自动屏蔽

作者: hysteria 时间: 2014-6-8 22:24

Sophia 发表于 2014-6-8 22:10
题目是5个人嘛，那明显不需要提醒人人都知道有红有蓝嘛

下面有行小字
注：虽然题设了有5个红眼睛，但岛民是不知道具体数字的。

作者: hysteria 时间: 2014-6-8 22:28

shicepku 发表于 2014-6-8 21:13
或者用递归的思想
一喝红颜第一天就会死
两个红眼第二天发现对方没死就全自杀了

这个解释是最贴切的。。。

作者: 911℃ 时间: 2014-6-8 22:29
楼上都是当代华罗庚

作者: LOY 时间: 2014-6-8 22:42
文章是正确的。对于数学神童来说，只是lv20逗lv1玩的题目。

作者: shicepku 时间: 2014-6-8 23:15
我在13，14楼的解释仅仅是文章中的“证明”的部分算是文章一半的内容后面提出的问题才是有意思的部分

作者: 小小白 时间: 2014-6-8 23:24
想通了一点。

两个人的时候，红眼的眼中是98蓝+1红，他需要等第二天看另一红的情况，才能判断自己眼睛的颜色。另一红自杀了，说明自己是蓝色，另一红没自杀，说明另一红眼里还有红眼，那就是自己了。

作者: 假装淫荡 时间: 2014-6-9 06:18
毫无逻辑性，还神童呢
首先岛上的人肯定知道有红蓝两种眼睛
而后面来的人只说了你们岛上有红眼睛，又没说具体数目
请问你怎么确认自己的红还是蓝？难道100个人互相交流你看到了多少个红眼睛？

作者: elffkdx 时间: 2014-6-9 07:55
不错的题，嘿嘿。

作者: 小小白 时间: 2014-6-9 08:16

假装淫荡发表于 2014-6-9 06:18
毫无逻辑性，还神童呢
首先岛上的人肯定知道有红蓝两种眼睛
而后面来的人只说了你们岛上有红眼睛，又没说 ...

再看看，想一会儿

作者: 德约科维奇 时间: 2014-6-9 09:21
本屌为自己的智商拙计

作者: 星空下的2货 时间: 2014-6-9 10:25

假装淫荡发表于 2014-6-9 06:18
毫无逻辑性，还神童呢
首先岛上的人肯定知道有红蓝两种眼睛
而后面来的人只说了你们岛上有红眼睛，又没说 ...

不需要交流，岛民拥有严密的逻辑，可以自己推理出有几个红眼。
当岛上只有一个红眼时，当游客说岛上有红眼睛时，当天岛上唯一的红眼看到99个蓝眼就会自杀。有两个时，两个红眼都以为岛上只有一个红眼，第一天都在等对方自杀，而到了第二天两人都没有自杀再看到其他98个蓝眼，立马就能推理出自己和对方都是红眼，第二天两人都会自杀。其就他以此类推了

欢迎光临八达网 (https://www.8-da.com/)