标题:
经典问题重温——帽子颜色问题！
[打印本页]
作者:
herrrabbit
时间:
2005-7-26 23:19
标题:
经典问题重温——帽子颜色问题！
兔子引言：帽子颜色问题是数学排列组合中一道经典的问题，也在现今的社会中经常作为一种常见的智利逻辑推导题目出现，他的经典问题提出是这样的。
“有3顶黑帽子，2顶白帽子。让三个人从前到后站成一排，给他
们每个人头上戴一顶帽子。每个人都看不见自己戴的帽子的颜色，却
只能看见站在前面那些人的帽子颜色。（所以最后一个人可以看见前
面两个人头上帽子的颜色，中间那个人看得见前面那个人的帽子颜色
但看不见在他后面那个人的帽子颜色，而最前面那个人谁的帽子都看
不见。现在从最后那个人开始，问他是不是知道自己戴的帽子颜色，
如果他回答说不知道，就继续问他前面那个人。事实上他们三个戴的
都是黑帽子，那么最前面那个人一定会知道自己戴的是黑帽子。为什
么？”
答案是，最前面的那个人听见后面两个人都说了“不知道”，他
假设自己戴的是白帽子，于是中间那个人就看见他戴的白帽子。那么
中间那个人会作如下推理：“假设我戴了白帽子，那么最后那个人就
会看见前面两顶白帽子，但总共只有两顶白帽子，他就应该明白他自
己戴的是黑帽子，现在他说不知道，就说明我戴了白帽子这个假定是
错的，所以我戴了黑帽子。”问题是中间那人也说不知道，所以最前
面那个人知道自己戴白帽子的假定是错的，所以他推断出自己戴了黑
帽子。
我们把这个问题推广成如下的形式：
“有若干种颜色的帽子，每种若干顶。假设有若干个人从前到后
站成一排，给他们每个人头上戴一顶帽子。每个人都看不见自己戴的
帽子的颜色，而且每个人都看得见在他前面所有人头上帽子的颜色，
却看不见在他后面任何人头上帽子的颜色。现在从最后那个人开始，
问他是不是知道自己戴的帽子颜色，如果他回答说不知道，就继续问
他前面那个人。一直往前问，那么一定有一个人知道自己所戴的帽子
颜色。”
当然要假设一些条件：
1)首先，帽子的总数一定要大于人数，否则帽子都不够戴。
2)“有若干种颜色的帽子，每种若干顶，有若干人”这个信息是队列
中所有人都事先知道的，而且所有人都知道所有人都知道此事，所有
人都知道所有人都知道所有人都知道此事，等等等等。但在这个条件
中的“若干”不一定非要具体一一给出数字来。这个信息具体地可以是
象上面经典的形式，列举出每种颜色帽子的数目
“有3顶黑帽子，2顶白帽子，3个人”，
也可以是
“有红黄绿三种颜色的帽子各1顶2顶3顶，但具体不
知道哪种颜色是几顶，有6个人”，
甚至连具体人数也可以不知道，
“有不知多少人排成一排，有黑白两种帽子，每种帽
子的数目都比人数少1”，
这时候那个排在最后的人并不知道自己排在最后——直到开始问他时
发现在他回答前没有别人被问到，他才知道他在最后。在这个帖子接
下去的部分当我出题的时候我将只写出“有若干种颜色的帽子，每种
若干顶，有若干人”这个预设条件，因为这部分确定了，题目也就确
定了。
3)剩下的没有戴在大家头上的帽子当然都被藏起来了，队伍里的人谁
都不知道都剩下些什么帽子。
4)所有人都不是色盲，不但不是，而且只要两种颜色不同，他们就能
分别出来。当然他们的视力也很好，能看到前方任意远的地方。他们
极其聪明，逻辑推理是极好的。总而言之，只要理论上根据逻辑推导
得出来，他们就一定推导得出来。相反地如果他们推不出自己头上帽
子的颜色，任何人都不会试图去猜或者作弊偷看——不知为不知。
5)后面的人不能和前面的人说悄悄话或者打暗号。
当然，不是所有的预设条件都能给出一个合理的题目。比如有99
顶黑帽子，99顶白帽子，2个人，无论怎么戴，都不可能有人知道自
己头上帽子的颜色。另外，只要不是只有一种颜色的帽子，在只由一
个人组成的队伍里，这个人也是不可能说出自己帽子的颜色的。
但是下面这几题是合理的题目：
1)3顶红帽子，4顶黑帽子，5顶白帽子，10个人。
2)3顶红帽子，4顶黑帽子，5顶白帽子，8个人。
3)n顶黑帽子，n-1顶白帽子，n个人（n>0）。
4)1顶颜色1的帽子，2顶颜色2的帽子，……，99顶颜色99的帽子，
100顶颜色100的帽子，共5000个人。
5)有红黄绿三种颜色的帽子各1顶2顶3顶，但具体不知道哪种颜色是
几顶，有6个人。
6)有不知多少人（至少两人）排成一排，有黑白两种帽子，每种帽子
的数目都比人数少1。
大家可以先不看我下面的分析，试着做做这几题。
如果按照上面3顶黑帽2顶白帽时的推理方法去做，那么10个人就
可以把我们累死，别说5000个人了。但是3)中的n是个抽象的数，考
虑一下怎么解决这个问题，对解决一般的问题大有好处。
假设现在n个人都已经戴好了帽子，问排在最后的那一个人他头
上的帽子是什么颜色，什么时候他会回答“知道”？很显然，只有在
他看见前面n-1个人都戴着白帽时才可能，因为这时所有的n-1顶白
帽都已用光，在他自己的脑袋上只能顶着黑帽子，只要前面有一顶黑
帽子，那么他就无法排除自己头上是黑帽子的可能——即使他看见前
面所有人都是黑帽，他还是有可能戴着第n顶黑帽。
现在假设最后那个人的回答是“不知道”，那么轮到问倒数第二
人。根据最后面那位的回答，他能推断出什么呢？如果他看见的都是
白帽，那么他立刻可以推断出自己戴的是黑帽——要是他也戴着白帽，
那么最后那人应该看见一片白帽，问到他时他就该回答“知道”了。
但是如果倒数第二人看见前面至少有一顶黑帽，他就无法作出判断
——他有可能戴着白帽，但是他前面的那些黑帽使得最后那人无法回
答“知道”；他自然也有可能戴着黑帽。
这样的推理可以继续下去，但是我们已经看出了苗头。最后那个
人可以回答“知道”当且仅当他看见的全是白帽，所以他回答“不知
道”当且仅当他至少看见了一顶黑帽。这就是所有帽子颜色问题的关
键！
如果最后一个人回答“不知道”，那么他至少看见了一顶黑帽，
所以如果倒数第二人看见的都是白帽，那么最后那个人看见的至少一
顶黑帽在哪里呢？不会在别处，只能在倒数第二人自己的头上。这样
的推理继续下去，对于队列中的每一个人来说就成了：
“在我后面的所有人都看见了至少一顶黑帽，否则的话他们
就会按照相同的判断断定自己戴的是黑帽，所以如果我看见
前面的人戴的全是白帽的话，我头上一定戴着我身后那个人
看见的那顶黑帽。”
我们知道最前面的那个人什么帽子都看不见，就不用说看见黑帽
了，所以如果他身后的所有人都回答说“不知道”，那么按照上面的
推理，他可以确定自己戴的是黑帽，因为他身后的人必定看见了一顶
黑帽——只能是第一个人他自己头上的那顶。事实上很明显，第一个
说出自己头上是什么颜色帽子的那个人，就是从队首数起的第一个戴
黑帽子的人，也就是那个从队尾数起第一个看见前面所有人都戴白帽
子的人。
这样的推理也许让人觉得有点循环论证的味道，因为上面那段推
理中包含了“如果别人也使用相同的推理”这样的意思，在逻辑上这
样的自指式命题有点危险。但是其实这里没有循环论证，这是类似数
学归纳法的推理，每个人的推理都建立在他后面那些人的推理上，而
对于最后一个人来说，他的身后没有人，所以他的推理不依赖于其他
人的推理就可以成立，是归纳中的第一个推理。稍微思考一下，我们
就可以把上面的论证改得适合于任何多种颜色的推论：
“如果我们可以从假设断定某种颜色的帽子一定会在队列中
出现，从队尾数起第一个看不见这种颜色的帽子的人就立刻
可以根据和此论证相同的论证来作出判断，他戴的是这种颜
色的帽子。现在所有我身后的人都回答不知道，所以我身后
的人也看见了此种颜色的帽子。如果在我前面我见不到此颜
色的帽子，那么一定是我戴着这种颜色的帽子。”
当然第一个人的初始推理相当简单：“队列中一定有人戴这种颜色的
帽子，现在我看不见前面有人戴这颜色的帽子，那它只能是戴在我的
头上了。”
对于题1)事情就变得很明显，3顶红帽子，4顶黑帽子，5顶白帽
子给10个人戴，队列中每种颜色至少都该有一顶，于是从队尾数起第
一个看不见某种颜色的帽子的人就能够断定他自己戴着这种颜色的帽
子，通过这点我们也可以看到，最多问到从队首数起的第三人时，就
应该有人回答“知道”了，因为从队首数起的第三人最多只能看见两
顶帽子，所以最多看见两种颜色，如果他后面的人都回答“不知道”，
那么他前面一定有两种颜色的帽子，而他头上戴的一定是他看不见的
那种颜色的帽子。
题2)也一样，3顶红帽子，4顶黑帽子，5顶白帽子给8个人戴，
那么队列中一定至少有一顶白帽子，因为其它颜色加起来一共才7顶，
所以队列中一定会有人回答“知道”。
题4)的规模大了一点，但是道理和2)完全一样。100种颜色的5050
顶帽子给5000人戴，前面99种颜色的帽子数量是1+……+99=4950，
所以队列中一定有第100种颜色的帽子（至少有50顶），所以如果自
己身后的人都回答“不知道”，那么那个看不见颜色100帽子的人就
可以断定自己戴着这种颜色的帽子。
至于5)、6)“有红黄绿三种颜色的帽子各1顶2顶3顶，但具体不
知道哪种颜色是几顶，有6个人”以及“有不知多少人排成一排，有
黑白两种帽子，每种帽子的数目都比人数少1”，原理完全相同，我
就不具体分析了。
最后要指出的一点是，上面我们只是论证了，如果我们可以根据
各种颜色帽子的数量和队列中的人数判断出在队列中至少有一顶某种
颜色的帽子，那么一定有一人可以判断出自己头上的帽子的颜色。因
为如果所有身后的人都回答“不知道”的话，那个从队尾数起第一个
看不见这种颜色的帽子的人就可以判断自己戴了此颜色的帽子。但是
这并不是说在询问中一定是由他来回答“知道”的，因为还可能有其
他的方法来判断自己头上帽子的颜色。比如说在题2)中，如果队列
如下：（箭头表示队列中人脸朝的方向）
白白黑黑黑黑红红红白→
那么在队尾第一人就立刻可以回答他头上的是白帽，因为他看见了所
有的3顶红帽子和4顶黑帽子，能留给他自己戴的只能是白帽子了
欢迎光临 人在德国 社区 (http://csuchen.de/bbs/)
Powered by Discuz! 7.2
