蓝眼睛岛的困惑 blue-eyed islanders puzzle
来自陶泽轩的博客。先把问题翻译过来，以后来谈我个人的解答。
原文地址：http://terrytao.wordpress.com/2011/04/07/the-blue-eyed-islanders-puzzle-repost/
有一个岛，岛上有一个部落，由n=1000个居民组成。这个部落有一个禁忌：他们不能知道自己的眼睛的颜色，甚至不能相互谈论这件事情，如果一个部落成员知道了自己的眼睛的颜色，按照部落的宗教禁忌，此人就要在第二天中午当着所有人的面在部落广场上自杀，部落成员都是绝对虔诚的，他们都会遵从这个禁忌。这个部落的人都具有良好的视力，他们可以看见其他所有人的眼睛的颜色，亦即他们都知道其他人的眼睛的颜色。这个部落的人不使用镜子，也不从水中观看自己的眼睛，总之，他们无法由外界知道自己的眼睛的颜色。也许正是这个宗教禁忌使得这个部落的人不使用镜子。
这个部落的人都具有高度的逻辑推理能力。他们也都知道部落的其他成员具有高度的逻辑推理能力、其他成员也都是绝对虔诚的、其他成员也都知道除自己外的其他人的眼睛的颜色。
岛上的居民的眼睛有两种颜色，棕色和蓝色，其中有900个人为棕色眼睛，另外100个为蓝色眼睛。但是每一个居民都并不知道这一点，因为他不知道自己的眼睛的颜色。蓝色眼睛的人能看到岛上有900个人为棕色眼睛和其他99个人为蓝色眼睛。棕色眼睛的人类似。
有一天，一个外来者到这个岛上访问。外来者的眼睛为蓝色的。一天晚上，为了向岛上居民致谢，外来者面对所有居民发表了一个演讲。外来者不知道岛上关于眼睛颜色的禁忌，在演讲中提到：“在这里看到一个和我一样的蓝色眼睛，是多么不寻常的一件事啊”。
现在的问题是，这句话会产生什么后果？
|
lifubo  发表文章数: 522 |
|
||
|
卢昌海  |
陶泽轩可能是一流学者中写博客最勤快的人，已经以博客文章为内容出了好几本书了。我看了他博客上有关本问题的一些讨论，真是公说公有理，婆说婆有理。等福波兄贴出个人解答后再看有什么可以掺和的吧。:-)
 宠辱不惊，看庭前花开花落
|
||
|
暴走迦楼罗  发表文章数: 737 |
外来者将被众人挖出眼珠子
|
||
|
impig  发表文章数: 47 |
我有点惊奇为什么他贴出solution 1. 那个证明不是明显有缺陷的么。外来者的声明很显然揭示了更多的信息，比如如果只有一个蓝眼睛，那这个人在听到声明以前就不知道是否存在蓝眼睛。
|
||
|
卢昌海 |
:: 外来者的声明很显然揭示了更多的信息，比如如果只有一个蓝眼睛，那这个人在听到声明以前就不知道是否存在蓝眼睛。
那倒也不然，因为岛上所有人都已经知道至少有99个蓝眼睛，在这种情况下外来者的声明，即至少存在一个蓝眼睛，貌似就不带来新信息了。 宠辱不惊，看庭前花开花落
|
||
|
biohu  发表文章数: 121 |
99天之后所有蓝眼睛的人自杀。(肯定很壮观)
|
||
|
快刀浪子  发表文章数: 216 |
很经典的智力题。和下面这道题本质上是一样的
－－－－－－－－－－－－ 一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种。每个人都能看到其它人帽子的颜色，却看不到自己的。主持人告诉大家最少有一锭帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？ 1、若是只有一个人，则他第一次就会打自己耳光。 2，若是两个人，设A、B是黑帽子,第二次关灯就会有人打耳光。原因是A看到B第一次没打耳光，就知道B也一定看到了有带黑帽子的人，可A除了知道B带黑帽子外，其他人都是白帽子，就可推出他自己是带黑帽子的人！同理B也是这么想的，这样第二次熄灯会有两个耳光的声音。 3，如果是三个人，A,B,C。 A第一次没打耳光，因为他看到B,C都是带黑帽子的；如果只有他们两个人带黑帽子，第二次应该有人打耳光；可第二次却没有。。。于是他知道B和C一定看到了除BC之外的其他人带了黑帽子，于是他知道BC看到的那个人一定是他，所以第三次有三个人打了自己一个耳光！
|
||
|
快刀浪子 发表文章数: 216 |
假设只有A、B两个人，他们都是蓝眼睛。现在有人告诉他们，他们这里最少有一个蓝眼睛。
虽然A、B都已经知道最少有一个蓝眼睛，但他们还是获得了新的信息，A知道B知道最少有一个人蓝眼睛，A知道B知道A知道最少有一个蓝眼睛，…………
|
||
|
卢昌海 |
嗯，不过一旦有三个人以上，情况就又不同了。
宠辱不惊，看庭前花开花落
|
||
|
快刀浪子 发表文章数: 216 |
一样的啊。
假设有A、B、C三个人，都是蓝眼睛。现在有人告诉他们：你们这里最少有一个蓝眼睛。 C的推理如下： 假设自己是棕眼睛。 这时A将看到C是棕眼睛，B是蓝眼睛。A认为：如果自己是棕色的，B将看到两个棕眼睛。所以B在第一天自杀。B在第一天不自杀，所以A在第二天知道是棕眼睛。这样A应该在第二天自杀。但事实上A没有在第二天自杀。 所以第三天C知道自己的假设是错的。即他知道自己是蓝眼睛。 稍为形式化一点， C知道A知道B知道有一个蓝眼睛 推出 C知道（如果C是棕色的，那么A知道（如果A是棕色的，那么B知道自己是棕色的）） 推出 C知道（如果C是棕色的，那么A知道（如果A是棕色的，那么B将在第一天自杀）） 又从第一天没人自杀 可推出 C知道（如果C是棕色的，那么A在第二天知道自己是蓝色的） 推出 C知道（如果C是棕色的，那么A在第二天自杀） 而第二天也没人自杀 提出 C在第三天知道自己是蓝色的
|
||
|
dfj  发表文章数: 282 |
联想到庞家莱谈过的一个问题（不是智力题）：如果数学理论都是从一些简单的公理一步一步通过严格的逻辑推理得出，那为这些理论是否等价于一些同义反复？
数学中那些丰富多彩的内容是怎么来的？
|
||
|
快刀浪子 发表文章数: 216 |
假设ABC都是蓝眼睛。
则A知道B知道C是蓝眼睛，所以A知道B知道最少有一个蓝眼睛。但C不知道A知道B知道最少有一个蓝眼睛（因为C不知道自己眼睛的颜色。如果是棕色，则这时A不知道B知道有一个蓝眼睛。） 当有一个人告诉他们，最少有一个蓝眼睛。则C获得了新的信息，这时C知道A知道B知道有一个蓝眼睛。
|
||
|
zhangqq 发表文章数: 549 |
快刀的推理对原题来说并不成立，因为无论外人说不说，这些够聪明的人都早已经知道每个人都知道至少有一个蓝眼睛，以此推理他们早就该自杀了，不用等到外人来宣布，除非他们又不够聪明，哈哈。
|
||
|
卢昌海 |
快刀兄的说法有道理，我刚才一边写天机当铺（将在12小时内上传），一边写回复，想得不够细，惭愧。
宠辱不惊，看庭前花开花落
|
||
|
zhangqq 发表文章数: 549 |
快刀的推理对4个及以上蓝眼睛的情形就不成立了。
|
||
|
卢昌海 |
zhangqq网友的推理并不能驳倒快刀兄。两者的差别在于“每个人至少看到一个蓝眼睛”不同于“每个人都知道每个人至少看到一个蓝眼睛”。拿三个人的情形来说，如果A看到两个蓝眼睛，那么他可以断定“每个人至少看到一个蓝眼睛”，却不能断定“每个人都知道每个人至少看到一个蓝眼睛”。四个人的情形也类似，如果A看到三个蓝眼睛，那么他可以断定“每个人至少看到一个蓝眼睛”，却不能断定“每个人都知道每个人至少看到一个蓝眼睛”，因为如果他自己是棕眼睛，那么B将只看见两个蓝眼睛，而B并不知道自己眼睛的颜色，因此B会认为如果自己是棕眼睛，那么C将只看见一个蓝眼睛，而C同样并不知道自己眼睛的颜色，因此会认为如果自己是棕眼睛，那么D将只看见棕眼睛，从而不是“每个人都知道每个人至少看到一个蓝眼睛”。更多人的情况也类似。外来者的话提供了“每个人都知道”（乃至它的n次方）这样一个重要环节，在这点上确实是一种新信息。
宠辱不惊，看庭前花开花落
|
||
|
zhangqq 发表文章数: 549 |
我重新想了一下。我的观点不对。
A看到BC都是蓝的，知道BC只要对看一下，BC都知道至少有一个蓝眼睛，而自己也知道，所以A认为其他人都知道至少有一个蓝眼睛。那么A现在会想B和C知道A自己知道“其他人都知道至少有一个蓝眼睛”这个事实么？ 至少有一个蓝眼睛 其他人都知道至少有一个蓝眼睛 这两个是不一样的。
|
||
|
zhangqq 发表文章数: 549 |
我还是没写对。重写一遍。
知道每个人知道至少有一个蓝眼睛。 知道每个人都知道其他人都知道每个人知道至少有一个蓝眼睛。 二阶的，哈哈。
|
||
|
huang 发表文章数: 30 |
这个好像高秩信息
|
||
|
快刀浪子 发表文章数: 216 |
::我刚才一边写天机当铺（将在12小时内上传），一边写回复，想得不够细，惭愧。
可见，高手分心也会失手:-) 昌海兄下面的分析过程好像和结论不一致。比如有三个人，A知道B知道有一个蓝眼睛。根据对称性，就可以得出每个人知道每个人知道有一个蓝眼睛。但“每个人知道每个人知道每个人知道有一个蓝眼睛”不成立。
|
||
|
快刀浪子 发表文章数: 216 |
只有AB两个蓝眼睛
A知道最少有一个蓝眼睛 并非A知道（B知道最少有一个蓝眼睛） 有ABC三个蓝眼睛 A知道最少有一个蓝眼睛 A知道（B知道最少有一个蓝眼睛） 并非A知道（B知道（C知道最少有一个蓝眼睛）） 有ABCD四个蓝眼睛 A知道最少有一个蓝眼睛 A知道（B知道最少有一个蓝眼睛） A知道（B知道（C知道最少有一个蓝眼睛）） 并非A知道（B知道（C知道（D知道最少有一个蓝眼睛））） 可见如果有n个人，则n－1阶信息成立，n阶信息不成立。 n阶信息： 每个人知道每个人知道（重复n次）最少有一个蓝眼睛。 当有人告诉他们：最少有一个蓝眼睛，则 任意阶信息都成立
|
||
|
暴走迦楼罗 发表文章数: 737 |
细想了一下 快刀浪子是对的 问题是那最后的结论会是什么？
|
||
|
lifubo 发表文章数: 522 |
没想到这个问题得到大家的关注，平地起高楼了。陶哲轩提供了两种可能对后果。我估计很多人知道这两种答案，但我仍然把它们列举出来，并陈诉清楚。真正的问题在这一个帖子的最后面。
======== 记蓝眼睛总数为n=100，棕色眼睛总数为m=900.总人数N=n+m=1000. 答案1：没有任何后果，岛上的居民一如既往地生活。 蓝眼睛的人知道至少有n-1=99个蓝眼睛，而棕色眼睛的人则知道至少有n=100个蓝眼睛。因此，岛上的每一个居民，都知道至少有n-1=99个蓝眼睛。于是，他们都知道岛上至少有一个蓝色眼睛的人，他们也都知道其他人也都知道岛上至少有99个蓝眼睛，以及m-1=899个棕色眼睛（有多少棕色眼睛与我们的问题关系不大，只是为了阐述得更清晰一点）。因而外来者并没有讲出什么新的、岛上居民以前所不知道的信息，所以外来者所讲的话对岛上的居民没有任何影响。 -------- 答案2：岛上的蓝眼睛居民将在第101天中午全体自杀。 我们用归纳法来证明，若岛上有n个蓝眼睛居民，则岛上的蓝眼睛居民将在第n天知道自己是蓝色眼睛，并在第 n+1=101 天中午自杀。 对岛上的蓝眼睛居民的人数n进行归纳。 第一步。假设n=1，即只有一个蓝眼睛居民。那么在此人听到外来者的话之后，马上（当天，第n=1天）就明白了外来者所讲的蓝眼睛居民就是他，于是他应该在接下来的一天，即第n+1=2天自杀。 第二步。对于一般的n，按照数学归纳法，我们的归纳假设为：若蓝眼睛居民为(n-1)个，则这些人将在第(n-1)天知道自己眼睛的颜色，并在第n天自杀。事实上这个归纳假设还蕴含结论：若蓝眼睛居民人数不超过(n-1)，则他们将在第n天到来之前或恰好就在第n天中午，都已经自杀了。 设B1为某个蓝眼睛居民，在第n天，B1如下推理： 若我（B1）为棕色眼睛，那么岛上一共有(n-1)个蓝眼睛居民，另一个蓝眼睛居民（设为B2，其实对任意一个其他的蓝眼睛居民也适用），按照归纳假设，在第(n-1)天就会认识到自己是蓝色眼睛，于是B2会在第n天自杀。既然B2没有在第n天自杀，这说明岛上的蓝眼睛居民人数不少于n. 但是我（B1）能够看到岛上的全部 (m+n) 个居民中，除我自己之外，有(n-1)个蓝眼睛，m个棕色眼睛，那么要使得蓝眼睛不少于n个，只能是我（B1）也是蓝色眼睛。 于是蓝眼睛B1在第n天知道自己为蓝色眼睛，并在第(n+1)天自杀，当然，所有的蓝眼睛都将在第(n+1)天自杀。而在第(n+1)天，所有棕色眼睛的居民也都会知道自己实际上是棕色眼睛，并将在第(n+2)天全体自杀。 我们不厌其详的写下每一个细节，目的是为了后面的分析，我们需要确保上述的证明，若仅仅从归纳法的角度看是正确（恰当？）叙述的。 ============ 上面给出了两种可能的后果。也许还有其他的后果，但我们只关心上述两种情形。上述问题只能有一个后果。所以，真正的问题是，到底哪一个是正确的，而错误的那一个又错在何处？ 如何调和二者之间的不一致？
|
||
|
dfj 发表文章数: 282 |
如楼上所说，这个问题的关键不在于岛上居民的命运如何，而是，我们应该如何理解外来人那句话的影响，为什么表面上没有任何信息量的一句话会起那么大的作用？
又联想到一个概率题，感觉跟这个类似： 某家庭有两个孩子，已经知道其中一个是儿子，在星期二出生，问这人有两个儿子的概率是多少。 zhidao.baidu.com/question/167442826.html
|
||
|
大漠孤狼  发表文章数: 183 |
我的思路是这样：
外乡人没有提供至少有1个蓝眼睛信息前 岛上只有1人时。那么，他无法知道自己的眼睛颜色。 岛上有2人时，由于他们知道眼睛的颜色有棕蓝2种可能，但却不知道棕蓝比例，因而有3种可能：2棕，1棕1蓝，2蓝；其中任意一人看到对方眼睛颜色只有棕与蓝2种可能。无论是棕还是蓝，都对应2种可能的分布，因而无法推断出自己的眼睛颜色。 岛上有3人时，可能的分布是：1,3棕；2,1棕2蓝；3,2棕1蓝，4，3蓝。任意一个人看到其余人的眼睛颜色可能是：1,2棕；2，一棕一蓝；3，2蓝。这些观察结果的每一个都对应2种可能，因而该人无法推断出自己的眼睛颜色。 以此类推，当岛上有n个人时，无论他们的眼睛颜色如何分布，在不知棕蓝比的情况下，无论某个人的观察结果是什么，都无法推断出自己的眼睛颜色是什么。
|
||
|
快刀浪子 发表文章数: 216 |
我在上面已经说了答案啊。
当有n个蓝眼睛时，则他们有从1到n－1阶的信息，但不具备n阶以上的信息。 n阶信息的定义： 每个人都知道（重复n次）最少有一个蓝眼睛。 当有人告诉他们时，则他们拥有了任意阶的信息。即获得了新的信息。 举个例子，有3个人时，每个人都知道每个人都知道最少有一个蓝眼睛。 但只有别人告诉他们“这里最少有一个蓝眼睛”。 “每个人都知道每个人都知道每个人都知道最少有一个蓝眼睛”才成立。 也就是说上面说的答案2是正确的。没有矛盾
|
||
|
dfj 发表文章数: 282 |
嗯，知识的“阶”，陶哲轩自己给出的提示也是这样的。
|
||
|
卢昌海 |
我比较认同快刀兄的推理（我前面回帖对信息的阶或者秩的分类不够细致，快刀兄的说法更准确）。Tao博客的第二种答案与快刀兄的或许是等价的，但快刀兄的推理似乎比Tao博客的第二种答案更直接地揭示了信息的阶或者秩所起的作用。
宠辱不惊，看庭前花开花落
|
||
|
tan9p 发表文章数: 24 |
如果蓝眼睛人数和棕眼睛人数一样会怎么样？
一蓑烟雨任平生。
|
||
|
lifubo 发表文章数: 522 |
答案1有一个错误。“于是，他们都知道岛上至少有一个蓝色眼睛的人，他们也都知道其他人也都知道岛上至少有99个蓝眼睛，以及m-1=899个棕色眼睛”应为“...他们也都知道其他人也都知道岛上至少有98个蓝眼睛，以及m-1=898个棕色眼睛”。
说点题外话。关于（共同common knowledge）知识，我总会想起拉姆斯菲尔德的名言：(un)known (un)known，一共4种组合。
|
||
|
星空浩淼  发表文章数: 725 |
在这个问题的基础上，如果外来者再加上一句话，可否变成类似那个“意想不到的老虎”悖论？
联想到庞家莱谈过的一个问题（不是智力题）：如果数学理论都是从一些简单的公理一步一步通过严格的逻辑推理得出，那为这些理论是否等价于一些同义反复？ 数学中那些丰富多彩的内容是怎么来的？ ---------------------------- 你这个问题，属于“逻辑演算中的信息增量问题”。就是说，如果采用“当且仅当”式的逻辑推导，貌似整个推理过程没有给我们带来任何新的信息。 我的看法是，如果A有许多完全等价的其他“马甲”，如果你只知道其中的部分马甲，那么通过逻辑推导给出你过去并没有见过的新马甲时，对你而言，你就获得了新的信息。 就如同去年有人给出万有引力的“熵力”解释，一些人觉得这个熵力解释，看起来更像是把一些物理事实倒过来变成前提而推导出来的，因此貌似没有多大意义。但事实上，如同Lorentz由Lorentz变换公式推导出光速不变的结论，而Einstein反过来由光速不变原理推导出Lorentz变换公式，这仍然是有意义的。至少，他给出了万有引力一个新的身份。事实上，从1995年开始，陆陆续续地有人开始把万有引力理论当做热力学来描述。人们把与引力相关的作用量，做重新解释和处理，把作用量看作是熵，作用量相对于度规的变分，改为熵相对于另一个变量的变分，最小作用量原理，换成最大熵原理，时间换成虚时间——对应温度的倒数。最后得到爱因斯坦场方程，等价于热力学方程dE=TdS-PdV，这样，黑洞力学的四大定理，变成黑洞热力学的四大定理，就成了顺理成章的事情。再由等效原理，Unruh效应也就不足为奇了。 有一个很好的比方：由温度、压强、速度等宏观参数描述的流体，深入微观本质，宏观上连续分布的流体是由在空间上离散分布的分子组成的，有着内部的微观自由度，因此我们说，流体是emergent的。同理，引力与其他几种相互作用的相比特立独行的个性，它的普适性（万有性），它与热力学之间奇妙的关系（例如黑洞视界附近的引力加速度，等同于Hawking辐射温度。更一般地，Unruh效应中，加速度与温度对应），可能正是说明万有引力是emergent的。那么，引力是否需要量子化呢？既然流体或其他宏观体系可以存在“相互作用的集体合作效应”——元激发（例如声子，自旋波等等），那么同理，即使引力是emergent的，引力一样可以量子化，此时引力子类似一种元激发。 我在故我思
|
||
|
wizard 发表文章数: 7 |
我认为第一给答案正确。
在这里用数学归纳法有个致命的错误，那就是初始假设。 ‘如果只有一个蓝眼睛‘ 是一个人人都知道的假命题。所以，作这个初始假设是根本不符合逻辑。 没有这个假设，就没有以后的结论。所以这完全是没有道理的。
|
||
|
wizard 发表文章数: 7 |
一个蓝眼睛
二个蓝眼睛 。。。 都是数学家自己虚构的新体系。 但岛上的居民，只生活在100个蓝眼睛这一个体系中，作为岛上居民，只能基于自己体系中已知的信息，对不确的信息做出假设。比如蓝眼睛的人，可以假设有100个蓝眼睛，或者99个蓝眼睛。如果这两个假设能给出一个结论，则这个结论才可信。如果你对这个岛上有多少个蓝眼睛一无所知，则可以做一个蓝眼睛。。。等假设。但岛上居民却知道的至少有99个蓝眼睛。我没学过信息论，不过我认为这个只是强行引入别的信息才导致矛盾结论。 至于那个男孩，女孩问题，就是一个简单的条件概率，并不存在争议。
|
||
|
dfj 发表文章数: 282 |
那个星期二男孩问题不知道这里讨论过没有？否则可以另开一贴。
对这个问题，网上讨论很多的(比如参见那个百度帖子)，不是“不存在争议”。 符合直觉的答案是1/2，而标准答案(对此我不确定)是13/27。
|
||
|
lifubo 发表文章数: 522 |
星期二男孩问题，准确答案：1/2.简单的条件概率。
设星期二生下的孩子为A,另一个为B. 则(A,B)的可能取值为（男女），（男男），（女男），（女女）。 现在，条件为{A=男}，即{（男女），（男男）}，要计算的概率为 P(男男|A=男)，显然等于1/2. 这个题目没有太大讨论的价值，比 Monty Hall Problem 简单多了。
|
||
|
dfj 发表文章数: 282 |
只要在google上搜一下，就知道不是所有人都同意楼上的答案，为了节省版面，这里就不拷过来了；甚至可以说，网上这些讨论给人的印象是，标准答案应该是13/27才对。我自己以前也曾得出13/27这个答案。到底应该是多少，我现在也不确定，需要再想想（就像蓝眼问题一样，需要指出另一种计算方法错在哪里）。
http://www.google.com/search?sourceid=chrome&ie=UTF-8&q=%E6%98%9F%E6%9C%9F%E4%BA%8C%E7%94%B7%E5%AD%A9 (可看其中前几个结果)
|
||
|
lifubo 发表文章数: 522 |
在某种意义上可以说星期二男孩问题的叙述不是很清晰，也就是说会产生歧义，那么转换为数学公式的时候就会有多种可能的方式。到底哪一种方式正确，这是一个语文问题而不是数学问题。类似地，我们都知道的Betrand悖论就是如此。Betrand悖论是说：随机取园一条弦，那么这条弦长度大于半径的1/2的概率是多少？有几个很自然的数字：1/2,1/3,1/4,到底是哪一个取决于你怎么解释随机这个词语，即取弦的方式如何随机化。也就是说，即使你看起来很好地叙述的话语，也同样可能是包含歧义的。再举个例子。随机的取一个整数，是什么意思？通常人们理解随机，都包含某种等可能性，但是你不可能等可能地取无限多个整数中的一个。这是de Feniti的例子，他试图以此来否定概率的可列可加性。对于星期二男孩问题，我以为其他的数字比如13/27也有一点道理，但是正如前面说的，这是语文的问题。进一步说，即使我认为这是一个文字上的问题而不是数学问题，我还是认为13/27这个结果太过古怪。也就是说，就自然语言表述的那个问题而言，我不能证明那个13/27是错误的，我只是说那个计算过程显得荒诞、滑稽。
|
||
|
lgy737 发表文章数: 45 |
这个和微软的一条老面试题相似，关于枪决病狗的，大家可以Google一下。对类似问题我觉得下面的陈述更为简明清楚，转帖如下：一群人在一个大厅开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其他人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就离开大厅自我消失。第一次关灯，没人离开。于是再开灯，大家再看一遍，关灯时仍然没人离开。一直到第三次关灯，这时有若干人离开了大厅。问有多少人戴着黑帽子？
答案是3人。具体推理见网上，请大家先弄明白这个推理，然后，回到这里，可以发现，蓝眼睛岛的困惑题面是有漏洞的，出题者有点弄巧成拙。实际上，“如果一个部落成员知道了自己的眼睛的颜色，按照部落的宗教禁忌，此人就要在第二天中午当着所有人的面在部落广场上自杀”这条规定才是启动程序的开始，一旦宣布执行，那么第100天（或者说第101天）所有蓝眼睛的就会全部自杀掉，蓝眼睛消失后，剩下的棕色眼睛接着就会立即意识到自己是什么颜色，1000人同时自杀，何等悲惨！整个过程无须等到外来者来设置一个蓝眼睛至少有一个的初始条件。换句话，外来者并非始作俑者，外来者的话不构成触发事件，没有任何新的信息，这点昌海兄一开始是对的，后来不知为何又自我否定了。我认为最终的结局是，部落灭绝。
|
||
|
卢昌海 |
欢迎lgy737网友。你所引微软面试题中的那句＂黑的至少有一顶＂所起的作用跟蓝眼睛岛问题中外来者带来的信息是一样的，难道不是恰恰说明这一信息是需要的吗？怎么反而由那道面试题得到了＂整个过程无须等到外来者来设置一个蓝眼睛至少有一个的初始条件＂的结论呢？
宠辱不惊，看庭前花开花落
|
||
|
冠臻 发表文章数: 2 |
lgy737 是对的。无论那个人来不来，只要有三个或三个以上同样颜色（比如蓝色）眼睛的岛居民，他们就会意识到至少有一个蓝色眼睛的人，那么结果就是种族灭亡。
|
||
|
zhangqq 发表文章数: 549 |
lgy737不对。
在只有一个人带黑帽的情形，若果事前不知道至少有一顶黑帽子这个先决条件，带黑帽的那个人永远不会知道自己带的是黑帽。
|
||
|
zhangqq 发表文章数: 549 |
补充一下：应该是没有一个人知道自己戴什么颜色的帽子。
|
||
|
卢昌海 |
冠臻网友是本站旧友吧？欢迎旧地重游。
劳驾哪位主张＂外来信息无用论＂的网友把三个人的推理步骤写全吧，这样＂快刀＂门的弟兄好有地方下刀。 宠辱不惊，看庭前花开花落
|
||
|
lgy737 发表文章数: 45 |
回昌海兄：是的，‘黑的至少有一顶’必须作为前提告诉所有人，但和微软试题不同，‘蓝眼睛岛的困惑’已经明确告知蓝棕色人数，岛上任何1人，以及局外人的我们，可以判断出，至少99蓝，899棕，无须另外告知。注意到，所有人都必须要知道‘蓝眼睛至少有一个’和‘棕眼睛至少有一个’，这是前提，不能缺少。但不是快刀说的要知道“每个人都知道每个人都知道......最少有一个蓝眼睛”
|
||
|
快刀浪子 发表文章数: 216 |
举个最简单的例子吧。岛上只有两个人，都是蓝眼睛。显然他们都知道最少有一个蓝眼睛。
然后往下怎么推？
|
||
|
lgy737 发表文章数: 45 |
回复zhangqq
请看我前贴的老话“答案是3人。具体推理见网上，请大家先弄明白这个推理，然后，回到这里”
|
||
|
卢昌海 |
To lgy737网友：
按照你的推理，如果屋子里有三个人，全都是黑帽子（当然，三人并未被告知这一点），那么‘黑的至少有一顶’这一条应该不再必要了。如果是这样，麻烦你把这种情况下的推理过程写一写，看是否有人能推出自己帽子的颜色。 宠辱不惊，看庭前花开花落
|
||
|
lgy737 发表文章数: 45 |
回复快刀
“岛上只有两个人，都是蓝眼睛”，当然无法推啊，请仔细看清楚我的上一贴
|
||
|
卢昌海 |
好家伙，贴子增加这么快，别把俺的上一贴子淹没。
宠辱不惊，看庭前花开花落
|
||
|
快刀浪子 发表文章数: 216 |
看不到推理过程，无从下刀
昌海兄说出了我的心声:-)
|
||
|
zhangqq 发表文章数: 549 |
岛上的居民的眼睛有两种颜色，棕色和蓝色，其中有900个人为棕色眼睛，另外100个为蓝色眼睛。但是每一个居民都并不知道这一点，
请注意这一句： 但是每一个居民都并不知道这一点， 就是说眼睛颜色的人数对居民而言是未知的。
|
||
|
wizard 发表文章数: 7 |
想了半天，才意识到还是快刀兄的说法正确。
昨天发了个回复，吃完饭后就意识到问题了。因为归纳法可以反推。 n=100 如果我是棕眼睛，n=99 会看到98个蓝眼睛，也可以假设 n=99 如果我是棕眼睛 . . . n=2 如果我是棕眼睛, n=1 看到全是棕眼睛. n=1 在多重假设后便无法判断,是不是有任何蓝眼睛存在.外来信息是却可以给这个一个答案.所以是新的信息. 其实,至于网友说法规起作用起,就会启动这一推理. 如果法规说,岛上的可能都是蓝眼睛,可能都是棕眼睛,也可能一些人是棕眼睛,另一些人是蓝眼睛.就可以避免启动这一推理. 所以说有两种颜色是不严谨的,因为这就已经暗示了每中颜色都至少有一个. '至少有一个蓝眼睛'确实带来新的信息.
|
||
|
陈一海 发表文章数: 18 |
快倒兄聪明
深山相送罢，日暮掩材扉；春草明年绿，王孙归不归。
|
||
|
zgg___ 发表文章数: 3 |
我同意灭族的结果。
但是，如果岛上有一个居民是聋子、或者耳背（耳背的定义是存在大于0的几率听不到人的话）、或者是有一个居民怀疑另一个居民是耳背、或者是有一个居民怀疑另一居民有怀疑别人耳背的想法等情况的话，那么他们就都得救了。 呵呵。
|
||
|
lifubo 发表文章数: 522 |
首先，答案1（没有变化）和答案2（归纳法，全死）确实是不同的，不相容的，即不可能二者都成立。也就是说，如果没有外来者，小岛居民对于任意初始状态（即棕色眼睛、蓝色眼睛的人数），都是稳定的，他们的知识不随时间而变化。
答案2，归纳法。第一步依赖于外来者说的话，而第二步则不依赖于外来者的话。这说明，如果答案2正确的话，外来者的话的确是一个诱因。 如果答案2正确，那么答案1的错误就是：外来者的话给至少某一个人带来了新的信息。那么，这个新的信息是什么？ 对于答案2归纳法的一个质疑：首先，归纳法的第一步，假定岛上只有一个蓝色眼睛的人，这是不可能的，因为每个人都知道岛上至少有99个蓝色眼睛的人。归纳法的第二步有同样的问题。也就是说归纳法的第一步根本不成立，由错误的前提当然可以推出任何想要的结论，所以得到“所有人都自杀”的结论不足为奇。 要想回答这个质疑，如果想仍然用归纳法来证明，就需要将归纳法中的“假定只有一个蓝色眼睛的人”改变一下，使得归纳法仍然可以进行下去同时并不包含上述类似话语。 注意，“每个人都知道岛上至少有99个蓝色眼睛的人”，并不能推出“岛上的每个人都知道岛上的其他人都知道岛上至少有99个蓝色眼睛的人”，但是“我们这些考虑这个问题的每个人都知道岛上的每个人都知道至少有99个蓝色眼睛的人”。
|
||
|
lifubo 发表文章数: 522 |
为方便起见，将这1000个人依次编号，其中100个蓝眼睛依次记作B1，...，B100，棕色眼睛记作R1，...，R900.
B1知道：若他自己（B1）为蓝眼睛，则岛上有100个蓝眼睛；若B1为蓝眼睛，则岛上有99个蓝眼睛。 B1知道至少有99个蓝眼睛。显然，数字99不能提高为100，否则B1就知道自己为蓝眼睛了。 --- B1知道： B2知道：B3，…，B100都是蓝眼睛，共98个；R1，...，R900为棕色，共900个。（B1知道B2知道。） [故B1知道B2知道至少有98个蓝眼睛。] 若B1为蓝眼睛，则B2知道：若B2为蓝眼睛，则岛上有100个蓝眼睛；若B2不是蓝眼睛，则岛上有99个蓝眼睛。 若B1不是蓝眼睛，则B2知道：若B2为蓝眼睛，则岛上有99个蓝眼睛；若B2不是蓝眼睛，则岛上有98个蓝眼睛。 --- 注1：这句话不等价于B1，B2都知道至少有98个蓝眼睛。事实上，B1，B2都知道至少有99个蓝眼睛。B2知道B3是蓝眼睛，B1也知道B3是蓝眼睛，B1也知道B2看到了B3为蓝眼睛，因而B1知道B2知道B3为蓝眼睛。B2知道B1是蓝眼睛，但B1自己不知道B1是否为蓝眼睛。 注2：98这个数字不能提高了。B1，B2都知道的蓝眼睛是B3，……，B100，一共98个。 准确地说：B1知道B2知道至少有最多98个蓝眼睛。
|
||
|
lifubo 发表文章数: 522 |
为方便思考和分析，我们引入如下符号。
知识：是一些命题，记作p,q,r,s,等等。 第j个人知道知识p，用记号Kj(p)来表示。 那么，B1知道（若B1蓝，则B2知道至少有99蓝），就可以表示为K1(If B1蓝，then B2(至少99蓝))。 我们看到需要考虑的一个基本形式为：K1(If p，then B2(q)).
|
||
|
lifubo 发表文章数: 522 |
B1知道一些B2知道的东西。例如B1知道：
若B1不是蓝眼睛，此时将有99个蓝眼睛，但B2不知道B2的颜色，故B2看来最少有98个蓝眼睛，而且B2不能提高这个数字。同时B2知道：若B2不是蓝眼睛，那么B3知道至少有97个蓝眼睛。而且B2断定B3也不能提高这个数字。 因而B1知道（B2知道（B3知道至少有97个蓝眼睛））。同时数字97 不能提高了。于是我们得到下述命题。 命题：max min K1（K2（K3（有x个蓝眼睛）））=97. 其中：max是对x来取的。min是对于K1，K2，K3的知识来取的。上述命题也就是前面提到过类似的“B1知道B2知道最多有至少98个蓝眼睛”。 对这个命题进行推广，可以得到“蓝眼睛岛民困惑”这一问题的答案。
|
||
|
lifubo 发表文章数: 522 |
http://terrytao.wordpress.com/2011/05/19/epistemic-logic-temporal-epistemic-logic-and-the-blue-eyed-islander-puzzle-lower-bound/
陶哲轩给出了完全的分析，以一种完全形式化（或数学化）的方式给出了一个严格的证明。很有点长。一个主要方面是“知道”满足的性质。该文最后还讨论了意外的绞刑（即意外的老虎）。
|
||
|
卢昌海 |
有意思，要打印出来看看。前面讨论时我就有些好奇，我们所说的信息的阶等概念在信息理论中是如何处理的。
宠辱不惊，看庭前花开花落
|
||
|
lifubo 发表文章数: 522 |
蓝眼睛岛上的居民具有高度的逻辑推理能力，一切逻辑上可能的结果对于他们来说都是已知的。
八卦一下。 岛民都已经知道了黎曼猜想的证明。这个岛在我们的东方，只是东的程度不同而已。所以这印证了站长的猜想：东方人解决了黎曼猜想。 另。假设这岛上有一个蠢人，这人推不出那些结论，于是侥幸存活。后来这个人独自在岛上呆腻了，离开了小岛来到凡间。这个故事及问题就是从这个蠢货那里流传出来的。 这里有一个悖论。 显然，蓝眼睛岛问题，绝不是一个简单的问题，于是，这么蠢的一个人怎么可能清楚讲述这么一个复杂的需要较高智力的问题呢？ 明眼人都能看出来上面的叙述有缺陷。 二十二条军规，也有类似的漏洞。其实二十二条军规严格的说来并不导致矛盾。似乎人们没有注意到这个缺陷。
|
||
|
卢昌海 |
呵呵，fubo兄这个帖子让我想起自己似乎在某个旧贴中开过东方人解决黎曼猜想之类的玩笑。为避免此玩笑被当成认真的预测流传出去，在这里澄清一下，那只是玩笑，站长对中国学术界（包括数学界）的能力不象陈省身先生那样有信心（陈老先生1985曾为中国数学界提笔写下“二十一世纪数学大国”的预言，被称为“陈省身猜想”，1989年则宣布“中华民族的数学能力不再需要证明”）。
宠辱不惊，看庭前花开花落
|
| :: 新用户注册 | 用户登陆 | 回复 | 刷新 :: |