清水河畔客户端下载
登录 立即注册 开启辅助访问 切换到窄版
查看: 328|回复: 9

[数学] 【搬运知乎】一个关于数学归纳法的悖论问题

[复制链接]
我的人缘0

级别:河蟹 (Lv.3)

积分
166

精华
0
帖子
228
威望
0 点
水滴
149 滴
在线时间
143 小时
发表于 2013-12-6 15:18:38 | 显示全部楼层 |阅读模式

欢迎来到清水河畔!电子科技大学学生请注册河畔,加入河畔大家庭,享受完整的论坛服务。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
提问:
此问题最早据说是澳大利亚的华裔数学神童陶哲轩在网上贴出来让大家思考,逗大家玩儿的。但却是真的把我难住了,一直百思不得其解。在此求教方家。
补题源:http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-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个红眼睛而已。旅行者说的那句【岛上有红眼睛的人】,没有输入任何新的信息,他说的就是岛上的人每天都看到的景象。所以哪怕岛上的人思维再缜密严谨,也不会有任何自杀的情况发生。

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

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

本题的升级版在:关于红眼睛蓝眼睛自杀问题,陶哲轩教授又问:旅者如何挽回自己说的话?

评分

参与人数 1水滴 +5 收起 理由
激情之焰 + 5

查看全部评分

欢迎访问清水河畔,请阅读新手导航以帮助你快速认识清水河畔。
回复

使用道具 举报

我的人缘0

级别:河蟹 (Lv.3)

积分
166

精华
0
帖子
228
威望
0 点
水滴
149 滴
在线时间
143 小时
 楼主| 发表于 2013-12-6 15:19:17 | 显示全部楼层
摘自排名第一的回答:

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

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

使用道具 举报

光电之王 该用户已被删除
发表于 2013-12-6 15:23:03 | 显示全部楼层
好复杂 看不懂
欢迎访问清水河畔,请阅读新手导航以帮助你快速认识清水河畔。
回复 支持 反对

使用道具 举报

我的人缘0

级别:鲤鱼 (Lv.7)

积分
2177

富甲一方五周年纪念勋章月饼勋章

精华
0
帖子
5361
威望
11 点
水滴
8120 滴
在线时间
1586 小时
发表于 2013-12-6 15:44:56 | 显示全部楼层
感觉就是一个递归问题……原来看到过类似的题目,说的是一个岛上的女人可以知道除他丈夫外的男人是否偷情,而知道自己丈夫偷情的女人必须杀死自己的丈夫……

这种问题,只要有一个开头,就会一直递归下去……
欢迎访问清水河畔,请阅读新手导航以帮助你快速认识清水河畔。
回复 支持 反对

使用道具 举报

我的人缘0

级别:鲤鱼 (Lv.7)

积分
2860

富甲一方富甲天下

精华
0
帖子
9811
威望
2 点
水滴
4972 滴
在线时间
1868 小时
发表于 2013-12-6 15:58:02 | 显示全部楼层
初始情况输入了新信息,N>1就不一定有新信息了吧,所以用数学归纳法是不是不太合适,或者说归纳的初始情况应该是N=2的情况
欢迎访问清水河畔,请阅读新手导航以帮助你快速认识清水河畔。
回复 支持 反对

使用道具 举报

我的人缘0

级别:河蟹 (Lv.3)

积分
497

精华
0
帖子
139
威望
0 点
水滴
857 滴
在线时间
483 小时
发表于 2013-12-6 16:02:59 | 显示全部楼层
这样的话,那这个岛会存在?假如有5个红的,95的蓝的!在没有外界信息输入的时候,任意一个红眼睛的人都已经知道岛上有4个红色的,可大家前四天都没有自杀,那到了第五天是不是红眼睛的人大家都要自杀?然后蓝眼睛的人就会明白,剩下的全是蓝眼睛了,这样理解是不是正确的呀?!
欢迎访问清水河畔,请阅读新手导航以帮助你快速认识清水河畔。
回复 支持 反对

使用道具 举报

我的人缘0

级别:草鱼 (Lv.5)

积分
962

精华
0
帖子
1842
威望
4 点
水滴
64 滴
在线时间
758 小时
发表于 2013-12-7 17:03:45 | 显示全部楼层
tanfc808 发表于 2013-12-6 16:02
这样的话,那这个岛会存在?假如有5个红的,95的蓝的!在没有外界信息输入的时候,任意一个红眼睛的人都已 ...

问题在于,在没有外界输入的时候,岛上的红眼睛,无法推断出自己的颜色。就好比,假如只有一个红眼睛,他以为自己是蓝眼睛,其他的蓝眼睛都在想,这个红眼睛为啥不自杀。假如有两个红眼睛,会都以为自己是蓝眼睛,在想另一个这红眼睛为啥不自杀。
所以,就是缺一个条件,让大家都知道,并且知道所有人都完全知道,所有人都可以在此基础上进行推断的开始时机。
回复 支持 反对

使用道具 举报

我的人缘0

级别:河蟹 (Lv.3)

积分
449

精华
0
帖子
740
威望
0 点
水滴
157 滴
在线时间
375 小时
发表于 2013-12-9 00:16:24 | 显示全部楼层
如果只有一个红的话 会自杀  但是多余一个就不会了  因为一个红的话红眼的人不知道有红眼  而旅行者的话提供了新的信息  当人数大于一时 他们都知道有红眼睛的人 因此旅行者的话不会有任何影响 除非他看着一个红眼的人说
欢迎访问清水河畔,请阅读新手导航以帮助你快速认识清水河畔。
回复 支持 反对

使用道具 举报

我的人缘0

级别:草鱼 (Lv.5)

积分
962

精华
0
帖子
1842
威望
4 点
水滴
64 滴
在线时间
758 小时
发表于 2013-12-10 10:31:41 | 显示全部楼层
tudoudigua86 发表于 2013-12-9 00:16
如果只有一个红的话 会自杀  但是多余一个就不会了  因为一个红的话红眼的人不知道有红眼  而旅行者的话提 ...

LS的,就是没考虑全面。只有一个红眼,他看到其他人都是蓝眼睛,旅行者说有红眼,所以他得自杀,对不。
假设,你也在这个村子中,看到除了你,其他人就只有一个红眼,旅行者说了有红眼,第一天他没自杀,为什么?  你得想一想,为什么那个红眼的没自杀。因为你也是红眼,他以为自己是蓝眼睛,而等着你第一天自杀。
第一天,你们两个都没自杀,村子里除了你们两个,其他都是蓝眼睛,你说,你还分析不出自己的眼睛么。

2个人的时候,旅行者没来时,你看着另一个红眼,想这家伙怎么还不自杀,难道他以为自己是蓝眼睛?另一个红眼也是同样这么想的。所以长久了,都维持着知道村里有红眼,却没人自杀的情况。
旅行者的话,上面都分析过了,关键在于他是对所有人说的。所以你知道 另一个红眼听到了,你认为他如果是唯一红眼的话,第一天就得自杀。
假设,旅行者只对你一个人说,那就没有提供新信息,因为你知道了,而且也不会产生影响。
但,你知道旅行者的话,那个红眼也听到了,而且过了第一天,那个红眼没有自杀,你是不是该分析一下,为什么?
回复 支持 反对

使用道具 举报

我的人缘0

级别:河蟹 (Lv.3)

积分
270

精华
0
帖子
394
威望
1 点
水滴
292 滴
在线时间
226 小时
发表于 2013-12-13 14:57:17 | 显示全部楼层
本帖最后由 左岸绿影 于 2013-12-13 15:02 编辑

这就是固定数值和随机变量的区别了嘛,穷举和数学归纳都是针对固定的数值(X=x),但X既然是随机变量所以所有的归纳都没有用处,当假设它为一个数时,已经和原题目相距甚远了
欢迎访问清水河畔,请阅读新手导航以帮助你快速认识清水河畔。
回复 支持 反对

使用道具 举报

除水手之家外其他版块禁止回复灌水无意义内容或纯表情。请注意时间,不要挖坟。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Powered by Discuz! X3.4 © 1998-2017 StarStudio

GMT+8, 2021-6-23 16:47 , Processed in 0.466800 second(s), 156 queries , Gzip On, Redis On.

快速回复 返回顶部 返回列表