[转] 红蓝眼睛的逻辑陷阱# WaterWorld - 未名水世界
l*3
1 楼
转子知乎: http://www.zhihu.com/question/21262930
一个关于数学归纳法的悖论问题:到底是第N天有N个红眼睛自杀,还是什么都不会发生?
此问题最早据说是澳大利亚的华裔数学神童陶哲轩在网上贴出来让大家思考,逗大家玩
儿的。但却是真的把我难住了,一直百思不得其解。在此求教方家。
题目是这样的。说一个岛上有100个人,其中有5个红眼睛,95个蓝眼睛。这个岛有三个
奇怪的宗教规则。
1. 他们不能照镜子,不能看自己眼睛的颜色。
2. 他们不能告诉别人对方的眼睛是什么颜色。
3. 一旦有人知道了自己是红眼睛,他就必须在当天夜里自杀。
某天,有个旅行者到了这个岛上。由于不知道这里的规矩,所以他在和全岛人一起狂欢
的时候,不留神就说了一句话:【你们这里有红眼睛的人。】
最后的问题是:假设这个岛上的人足够聪明,每个人都可以做出缜密的逻辑推理。请问
这个岛上将会发生什么?
此问题的第一个答案是用数学归纳法得出的:如果这个岛上有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天有N个红眼睛自杀,还是什么都不会发生?
此问题最早据说是澳大利亚的华裔数学神童陶哲轩在网上贴出来让大家思考,逗大家玩
儿的。但却是真的把我难住了,一直百思不得其解。在此求教方家。
题目是这样的。说一个岛上有100个人,其中有5个红眼睛,95个蓝眼睛。这个岛有三个
奇怪的宗教规则。
1. 他们不能照镜子,不能看自己眼睛的颜色。
2. 他们不能告诉别人对方的眼睛是什么颜色。
3. 一旦有人知道了自己是红眼睛,他就必须在当天夜里自杀。
某天,有个旅行者到了这个岛上。由于不知道这里的规矩,所以他在和全岛人一起狂欢
的时候,不留神就说了一句话:【你们这里有红眼睛的人。】
最后的问题是:假设这个岛上的人足够聪明,每个人都可以做出缜密的逻辑推理。请问
这个岛上将会发生什么?
此问题的第一个答案是用数学归纳法得出的:如果这个岛上有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个红眼睛而已。旅行者说的那句【岛上有红眼睛的人】
,没有输入任何新的信息,他说的就是岛上的人每天都看到的景象。所以哪怕岛上的人
思维再缜密严谨,也不会有任何自杀的情况发生。
从这个角度来说,也对呀。
这到底是怎么一回事,我迷茫了。请求方家解答疑惑。