Blue-Eyed Island: A bunch of people are living on an island, when a visitor comes with a strange order: all blue-eyed people must leave the island as soon as possible. There will be a flight out at 8:00 pm every evening. Each person can see everyone else’s eye color, but they do not know their own (nor is anyone allowed to tell them). Additionally, they do not know how many people have blue eyes, although they do know that at least one person does. How many days will it take the blue-eyed people to leave?
Hints: #218, #282, #341, #370
解法
这道题的意思是，岛上有一群人，其中有些人是蓝眼睛，现在有一个命令说所有蓝眼睛的都必须离开小岛。现在的情况是：
- 岛上蓝眼睛人数 >= 1
- 每个人知道其他人是不是蓝眼睛
- 每个人不知道自己是不是蓝眼睛
- 每天有一班飞机离开小岛
问多少天之后所有蓝眼睛的会离开小岛？
问题的关键是，蓝眼睛的人何时会知道自己是蓝眼睛的（没有人会告诉他）？
下面方便起见把蓝眼睛简称为B，白眼睛简称为W。下面举几个例子来说明：
如果岛上只有一个蓝眼睛
B1脑中：看到其他人都是W，因为知道岛上至少有一个B，那么B1就知道自己是B。
W脑中：B1可以走了。
结果：B1走了
因此：
f(1) = 1
如果岛上有两个蓝眼睛
B1、B2视角：看到1个B
W视角：看到2个B
Day 1：
B1、B2脑中：因为f(1) = 1，所以他应该在Day 1走
W脑中：你们走吧
结果：没人走
Day 2：
B1、B2脑中：Day 1没人走，那说明这里还有一个B，但是其他人都是W，那么说明自己也是B
W脑中：。。。。。。
结果：B1、B2走了
因此：
f(2) = 2
如果岛上有3个蓝眼睛
B1视角：看到2个B
B2视角：看到2个B
B3视角：看到2个B
W视角：看到3个B
Day 1：
B1、B2、B3脑中：因为f(2) = 2，所以他应该在Day 2走，我先观察两天再说
W脑中：。。。。。。
结果：没人走
Day 2：
B1、B2、B3脑中：那两个B今天应该走了
W脑中：。。。。。。
结果：没人走
Day 3：
B1、B2、B3脑中：说明还有一个B，那个B就是自己
W脑中：。。。。。。
结果：B1、B2、B3都走了
因此：
f(3) = 3
总结
- 任何人看到其他人是B的时候，首先不会认为自己是蓝眼睛。
- 但是当这个人发现B没有离开小岛的时候，他就会知道B不止一个，而这个人就是自己。
- 没有B会提前离开，要走都是一起走的，因为它们是同时意识到自己是B的。
所以 f(b) = b （b=蓝眼睛数量）
评论