网易公开课地址

一、诚实人与说谎者

问题：

两个箱子，一个有财宝，另一个没有；

有一个诚实人和一个说谎者，他们都知道哪个箱子有财宝；

但你不知道哪个是诚实人哪个是说谎者

如何问他们两人问题，确定哪个箱子有财宝。

答案：

“如果问另一个人，哪个箱子有财宝，对方会怎么回答？”

分析：

可以把问题改为“如果问另一个人，箱子Ａ有财宝是对的吗”

“箱子Ａ有财宝"这是一个断言A。断言A可能为真或假

假如有两个布尔函数F和G，存在2种情况：

1、F(x) = x，G(x) = not x  

2、F(x) = not x，G(x) = x 

要求用F和G构造一个函数H(x)=x

那么H(x)可以为H(x) = not F(G(x))

二、善变者

问题：

善变者----初始状态随机，可以为诚实人，也可以为说谎者。其每次回答一个问题后，就切换状态，从城市人转换为说谎者，或从说谎者转换为诚实人。

五个人，四个善变者，一个诚实人。

能问两个问题，可以对同一个人问两个问题，或找两个人分别问一个问题。

如何找到诚实人。

答案：

问题一：你是诚实人吗？

问题二：问题一回答“是”（这轮肯定是诚实人）　　　你们当中谁是诚实人？

　　　　问题一回答“不是”（这轮肯定不是诚实人）　　你们当中谁不是诚实人？

分析：

问题二的第二个问的问法很有技巧。不过找不到比较合适的“数学”表示法

三、外星人来袭！

问题：

100个人，排队，每人一顶帽子，帽子可能是紫色也可以是绿色。第i个人可以看见前i-1个人的帽子。

从第100个人开始至第1个人报帽子的颜色，如果他报错了，则咔擦掉，如果报对了，则平安。

问用什么样的策略报数，可以使得挂掉的人最少。

答案：

第100个人，如果前99个人紫色帽子的个数是奇数，则报紫色，否则报绿色。

对于1-99中的第i个人

1、他知道前i-1个人的紫色帽子个数是否是奇数；

2、如果第i+1至99报数的人都正确，那么他知道从i+1至99的紫色帽子个数是否是奇数；

3、根据第100个人，他知道前99个人中的帽子个数是否是奇数；

根据前面3个条件，第i个人可以计算出他头上帽子是什么颜色的。

（注意第99个人我们可以认为从i+1至99中没有人，也就是紫色帽子的个数是0，为偶数）

联想：

用布尔运算表示会显得更“准确”点，有点类似一个结构体用一个指针却要表示双向链表的方法。

四、蓝额头房间

问题：

100个逻辑学家参与游戏。

游戏规则：

1、100个逻辑学家蒙眼被带进房间，然后至少一个逻辑学家额头被涂成了蓝色。最后去掉蒙眼布。

2、然后不断的关灯，开灯；在关灯的时候，如果某个逻辑学家推断出他是蓝额头，那么他离开房间。

3、全部蓝额头的人离开房间后，游戏结束。

如果每个人都被涂了蓝额头，会发生什么？

答案：

在第100次关灯的时候，全部人同时离开房间。

分析：

假如只有一个人是蓝额头，那么第一轮他会离开房间；

假如有2个人是蓝额头，那么第一轮没有人离开房间。而这2个人只看到一个蓝额头，那么他会在这一轮离开房间。（他会这样推理，另外那个蓝额头的人除非看到了自己是蓝额头，否则他会在上一轮离开房间）

以此类推。。

扩展：

http://www.newsmth.net/bbscon.php?bid=51&id=155695

一个岛上有100个人，其中有5个红眼睛，95个蓝眼睛。这个岛有三个奇怪的规则。

1. 他们不能照镜子，不能看自己眼睛的颜色。

2. 他们不能告诉别人对方的眼睛是什么颜色。

3. 一旦有人知道了自己是红眼睛，他就必须在当天夜里自杀。

某天，有个旅行者到了这个岛上。由于不知道这里的规矩，所以他在和全岛人一起狂欢

的时候，不留神就说了一句话："你们这里有红眼睛的人。"

假设这个岛上的人足够聪明，每个人都可以做出缜密的逻辑推理。请问这个岛上将会发

生什么？

陶哲轩说，这个旅行者事实上讲了一句废话，没有带来任何新的信息。因为这岛上有95个蓝眼睛，5个红眼睛。每个人都知道这岛上有红眼睛的人。无非是蓝眼睛的人看到有5个红眼睛，红眼睛的人看到有4个红眼睛而已。旅行者说的那句"岛上有红眼睛的人"，没有输入任何新的信息，他说的就是岛上的人每天都看到的景象。所以哪怕岛上的人思维再缜密严谨，也不会有任何自杀的情况发生。

（神和人的区别太明显了。。）

五、占位符

课程上对应的第5节是“蓝额头房间”的分析

六、数字额头游戏

问题：

把3个逻辑学家放进房间里面，在3个逻辑学家头上写上3个不同的数字，其中某个数字是其他两个数字之和。

A看见了B额头上写了20， C额头上写了30

A：我不知道我头上写的是多少？

B：我也不知道

C：我也不知道

A：我知道了

问：A额头上写的是多少？

答案：

A看到20和30=>A知道他头上的数组不是10就是50

1、如果A头上的数是10

B看到10和30=>那么B会知道他头上的数字不是20就是40

C看到10和20=>C会知道他头上的数字不是10就是30；但由于3个数都不相同，那么C会知道他头上的数字就是30，那么C能确定他头上的数字是30

结论：A头上的数字不是10，那么就只会是50

联想：

如果复杂到一定程度，人脑容不下这么复杂状态，怎么写程序解？

七、灯亮or灯灭

问题：

100个灯泡，起始全是灭的。

执行100次步骤：第i次步骤，对i，2*i，3*i 。。的灯全部切换一下开关（灭的开等，亮的关灯）

最后有多少灯是亮的

答案：

对第n个灯，假如他有k个因子，那么他会被切换k次开关；但k为奇数时，这个灯会是亮的。而只有平方数是有奇数个因子，100里面有10个平方数，所以答案为10

八、路径计算

问题：

n*m网格，从(1,1)走到(n,m)有多少种走法？只能向下或向右走一步

答案：

组合数C(n+m-2, n - 1)。

视频里面居然先用二维递推解一遍，然后又用母函数解一遍

分析：

从(1,1)走到(n,m)需要n+m - 2步，其中有n-1步是向下的

联想：

用来了解下递推或母函数也是不错的

九、三维路径计算

问题：

x*y*z正方体，从(1,1)走到(x,y,z)有多少种走法？只能向下或向右走一步

解法：

同上题

联想：

如果是在正方体表面行走，似乎递推方便点，用组合数比较麻烦。