一个关于数学归纳法的悖论问题:到底是第 N 天有 N 个红眼睛自杀,还是什么都不会发生?

此问题最早据说是澳大利亚的华裔数学神童陶哲轩在网上贴出来让大家思考,逗大家玩儿的。 补题源:terrytao.wordpress.com/ 注:题源背景为蓝眼睛(100)、棕眼睛(900)。 题目是这样的。说一个岛上有100个人,其中有5个红眼睛,95个蓝眼睛。这个岛有三个奇怪的宗教规则。 1. 他们不能照镜子,不能看自己眼睛的颜色。 2. 他们不能告诉别人对方的眼睛是什么颜色。 3. 一旦有人知道了自己的眼睛颜色,他就必须在当天夜里自杀。(尊重…
关注者
5692
被浏览
519069

338 个回答

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

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

我们先假设“自杀”是一个有乐趣的事情,即,岛上的人很想“自杀”。我们认为岛上的人约定了一个“协议”,这个协议满足:
条件1.在世界开始之前,协议已被制定;一旦世界开始(人开始看别人的眼睛以及是否有人自杀)之后,任何人之间没有任何通信。也就是,协议可以描述为一个函数:
f(id,color,n,alive)
其中,id表示自己的身份,color表示除自己以外的人的眼睛颜色,n表示今天的日期,alive是一个二维数组,表示从开始到现在的每一天里每个人是否还活着。f的值就是自己是否“自杀”。
条件2.对任何一种眼睛颜色的配置,不存在一天,使得某个蓝眼人自杀。
如果协议满足条件2,我们说它是合法的。
如果一个协议满足,对于任何初始配置,存在一天,使得所有的红眼人都死了,那么称这个协议是完备的。

定理1:不存在一个会导致任何人自杀的合法协议(真好!)。
推论:任何合法的协议都是非完备的。
证明:反证。假设在某种协议以及某种眼睛配置的情况下,第n天有人自杀了。因为自然数是良序的,我们可以取最小的n。
这时,对某个id,color,alive,有
f(id,color,n,alive)=自杀。
由于n是最小的,所以alive里面的内容都是“活着”。这时,我们将初始配置中第id个人的眼睛颜色反转。易证,第n天前不会有人自杀(因为n是最小的),所以,这种情况下他得到的全部信息
(id,color,n,alive)
是和初始配置反转之前一样的。于是,这个协议就是不合法的。

游客的出现使得整个模型被摧毁。于是,我们只能认为,游客出现之后,岛上的人忘记了自己的眼睛颜色,之后开了个大会,讨论新的协议。这个协议与之前唯一的不同是:
条件3.如果对任何非全蓝眼的初始配置,不存在一天,使得某个蓝眼人自杀,那么称这个协议是“几乎合法”的。

定理2:存在一个几乎合法的完备的协议。
证明:这个协议的内容是:当且仅当n等于color中红眼人的数量,f(id,color,n,alive)=自杀

我们说岛上的人都是心思缜密的。什么叫心思缜密呢?我们理解为:尽量早自杀。

定义:对于两个几乎合法的完备的协议f1与f2,如果对所有初始配置,f1中所有红眼人全都自杀了的日期小于等于f2中所有红眼人自杀的日期,那么称f1<=f2
易证,<构成一个偏序

定理3:这个偏序存在唯一的最小元,即定理2的证明中的协议。
证明:留作给读者的练习。

结论就是,在这种理解之下,岛上的人“早死早超生”的方法就是在游客来了之后第N天N个红眼的集体自杀。

必须强调的是,有很多几乎合法的完备协议,例如:
第2*n天n个红眼人集体自杀
第fib(n)天n个红眼人集体自杀
。。。。。。
所以,我们必须假设岛上的人是渴望自杀的。
为什么?