一、诚实人与说谎者
问题：
两个箱子，一个有财宝，另一个没有；
有一个诚实人和一个说谎者，他们都知道哪个箱子有财宝；
但你不知道哪个是诚实人哪个是说谎者
如何问他们两人问题，确定哪个箱子有财宝。
答案：
“如果问另一个人，哪个箱子有财宝，对方会怎么回答？”
分析：
可以把问题改为“如果问另一个人，箱子Ａ有财宝是对的吗”
“箱子Ａ有财宝"这是一个断言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)有多少种走法？只能向下或向右走一步
解法：
同上题
联想：
如果是在正方体表面行走，似乎递推方便点，用组合数比较麻烦。
网友评论