【6月征答】造币厂问题及海岛分金问题

Newton1983 · 发表于 2004-5-27 19:28:00

<

>ApSimon 的造币厂问题
<

> 艾波西蒙(ApSimon)于1984年在他所写的一本书中,介绍了下面的造币厂问题:
<

> n 个造币厂生产同一种硬币, 但其中某些厂由于材料问题造出了非标准的硬币。设标准的硬币重c克(已知),非标准的硬币只有一种重量,重c(1+e)克,其中e是个不为0的未知数,可以取正数或负数。为了查出哪些厂生产的硬币是非标准的,从各厂中抽出一些样品(个数不限)放在一起进行称重,只能称2次.设ai,bi(i=1,...,n)分别为第一次、第二次称重从第i个厂中取得的样品个数。每个厂提供的样品或者都是标准的,或者都是非标准的.设pn=∑max(ai,bi)为某一称重方案的样品总数,求一种使pn尽量小的称重方案。其中∑表示对于i从1到n求和,即∑i=1,…,n(以下同).

Newton1983 · 发表于 2004-5-27 19:39:51

<

>海盗分金问题<

>海盗，大家听说过吧。这是一帮亡命之徒，在海上抢人钱财，夺人性命，干的是刀头上舔血的营生。在我们的印象中，他们一般都瞎一只眼，用条黑布或者讲究点的用个黑皮眼罩把坏眼遮上。他们还有在地下埋宝的好习惯，而且总要画上一张藏宝图，以方便后人掘取。不过大家是否知道，他们是世界上最民主的团体。参加海盗的都是桀骜不驯的汉子，是不愿听人命令的，船上平时一切事都由投票解决。船长的唯一特权，是有自己的一套餐具--可是在他不用时，其他海盗是可以借来用的。船上的唯一惩罚，就是被丢到海里去喂鱼。<

>
　　现在船上有若干个海盗，要分抢来的若干枚金币。自然，这样的问题他们是由投票来解决的。投票的规则如下：先由最凶猛的海盗来提出分配方案，然后大家一人一票表决，如果有50%或以上的海盗同意这个方案，那么就以此方案分配，如果少于50%的海盗同意，那么这个提出方案的海盗就将被丢到海里去喂鱼，然后由剩下的海盗中最凶猛的那个海盗提出方案，依此类推。
　　我们先要对海盗们作一些假设。
　　1)　每个海盗的凶猛性都不同，而且所有海盗都知道别人的凶猛性，也就是说，每个海盗都知道自己和别人在这个提出方案的序列中的位置。另外，每个海盗的数学和逻辑都很好，而且很理智。最后，海盗间私底下的交易是不存在的，因为海盗除了自己谁都不相信。
　　2)　一枚金币是不能被分割的，不可以你半枚我半枚。
　　3)　每个海盗当然不愿意自己被丢到海里去喂鱼，这是最重要的。
　　4)　每个海盗当然希望自己能得到尽可能多的金币。
　　5)　每个海盗都是现实主义者，如果在一个方案中他得到了1枚金币，而下一个方案中，他有两种可能，一种得到许多金币，一种得不到金币，他会同意目前这个方案，而不会有侥幸心理。总而言之，他们相信二鸟在林，不如一鸟在手。
　　6)　最后，每个海盗都很喜欢其他海盗被丢到海里去喂鱼。在不损害自己利益的前提下，他会尽可能投票让自己的同伴喂鱼。
　　现在，如果有10个海盗要分100枚金币，将会怎样？

Newton1983 · 发表于 2004-5-27 19:45:35

<

>上面两题作为6月征答，也希望广大网友把你们的东东拿来一起分享，会有奖励的哦！！！！

heyi · 发表于 2004-5-28 00:15:25

我建议将第一个问题作为征答，第二个问题最好不要再讨论了。有人分析过（问题2）条件无论如何严密都是无法得标准答案，这个问题逆推过程有问题的。

b · 发表于 2004-5-28 03:49:17

数学的逻辑有时会导致看来十分怪异的结论。一般的规则是，如果逻辑推理没有漏洞，那么结论就必定站得住脚，即使它与你的直觉矛盾。 1998年9月，加利福尼亚州帕洛阿尔托的Stephen M. Omohundro寄给我一道难题，它恰好就属于这一类。这难题已经流传了至少十年，但是Omohundro对它作了改动，使它的逻辑问题变得分外复杂了。
先来看看此难题原先的形状。10名海盗抢得了窖藏的100块金子，并打算瓜分这些战利品。这是一些讲民主的海盗（当然是他们自己特有的民主），他们的习惯是按下面的方式进行分配：最厉害的一名海盗提出分配方案，然后所有的海盗（包括提出方案者本人）就此方案进行表决。如果50%或更多的海盗赞同此方案，此方案就获得通过并据此分配战利品。否则提出方案的海盗将被扔到海里，然后下提名最厉害的海盗又重复上述过程。
所有的海盗都乐于看到他们的一位同伙被扔进海里，不过，如果让他们选择的话，他们还是宁可得一笔现金。他们当然也不愿意自己被扔到海里。所有的海盗都是有理性的，而且知道其他的海盗也是有理性的。此外，没有两名海盗是同等厉害的——这些海盗按照完全由上到下的等级排好了座次，并且每个人都清楚自己和其他所有人的等级。这些金块不能再分，也不允许几名海盗共有金块，因为任何海盗都不相信他的同伙会遵守关于共享金块的安排。这是一伙每人都只为自己打算的海盗。最凶的一名海盗应当提出什么样的分配方案才能使他获得最多的金子呢？
为方便起见，我们按照这些海盗的怯懦程度来给他们编号。最怯懦的海盗为1号海盗，次怯懦的海盗为2号海盗，如此类推。这样最厉害的海盗就应当得到最大的编号，而方案的提出就将倒过来从上至下地进行。
分析所有这类策略游戏的奥妙就在于应当从结尾出发倒推回去。游戏结束时，你容易知道何种决策有利而何种决策不利。确定了这一点后，你就可以把它用到倒数第2次决策上，如此类推。如果从游戏的开头出发进行分析，那是走不了多远的。其原因在于，所有的战略决策都是要确定：“如果我这样做，那么下一个人会怎样做？”
因此在你以下海盗所做的决定对你来说是重要的，而在你之前的海盗所做的决定并不重要，因为你反正对这些决定也无能为力了。

记住了这一点，就可以知道我们的出发点应当是游戏进行到只剩两名海盗——即1号和2号——的时候。这时最厉害的海盗是2号，而他的最佳分配方案是一目了然的：100块金子全归他一人所有，1号海盗什么也得不到。由于他自己肯定为这个方案投赞成票，这样就占了总数的50%，因此方案获得通过。
现在加上3号海盗。1号海盗知道，如果3号的方案被否决，那么最后将只剩2个海盗，而1号将肯定一无所获——此外，3号也明白1号了解这一形势。因此，只要3号的分配方案给1号一点甜头使他不至于空手而归，那么不论3号提出什么样的分配方案，1号都将投赞成票。因此3号需要分出尽可能少的一点金子来贿赂1号海盗，这样就有了下面的分配方案： 3号海盗分得99块金子，2号海盗一无所获，1号海盗得1块金子。
4号海盗的策略也差不多。他需要有50%的支持票，因此同3号一样也需再找一人做同党。他可以给同党的最低贿赂是1块金子，而他可以用这块金子来收买2号海盗。因为如果4号被否决而3号得以通过，则2号将一文不名。因此，4号的分配方案应是：99块金子归自己，3号一块也得不到，2号得1块金子，1号也是一块也得不到。
5号海盗的策略稍有不同。他需要收买另两名海盗，因此至少得用2块金子来贿赂，才能使自己的方案得到采纳。他的分配方案应该是：98块金子归自己，1块金子给3号，1块金子给1号。
这一分析过程可以照着上述思路继续进行下去。每个分配方案都是唯一确定的，它可以使提出该方案的海盗获得尽可能多的金子，同时又保证该方案肯定能通过。照这一模式进行下去，10号海盗提出的方案将是96块金子归他所有，其他编号为偶数的海盗各得1块金子，而编号为奇数的海盗则什么也得不到。这就解决了10名海盗的分配难题。

b · 发表于 2004-5-28 03:49:36

Omohundro的贡献是他把这一问题扩大到有500名海盗的情形，即500名海盗瓜分100块金子。显然，类似的规律依然成立——至少是在一定范围内成立。事实上，前面所述的规律直到第200号海盗都成立。 200号海盗的方案将是：从1到199号的所有奇数号的海盗都将一无所获，而从2到198号的所有偶数号海盗将各得1块金子，剩下的1块金子归200号海盗自己所有。
乍看起来，这一论证方法到200号之后将不再适用了，因为201号拿不出更多的金子来收买其他海盗。但是即使分不到金子，201号至少还希望自己不会被扔进海里，因此他可以这样分配：给1到199号的所有奇数号海盗每人1块金子，自己一块也不要。
202号海盗同样别无选择，只能一块金子都不要了——他必须把这100块金子全部用来收买100名海盗，而且这100名海盗还必须是那些按照201号方案将一无所获的人。由于这样的海盗有101名，因此202号的方案将不再是唯一的——贿赂方案有101种。
203号海盗必须获得102张赞成票，但他显然没有足够的金子去收买101名同伙。因此，无论提出什么样的分配方案，他都注定会被扔到海里去喂鱼。不过，尽管203号命中注定死路一条，但并不是说他在游戏进程中不起任何作用。相反，204号现在知道，203号为了能保住性命，就必须避免由他自己来提出分配方案这么一种局面，所以无论204号海盗提出什么样的方案，203号都一定会投赞成票。这样204号海盗总算侥幸拣到一条命：他可以得到他自己的1票、203号的1票、以及另外100名收买的海盗的赞成票，刚好达到保命所需的50%。获得金子的海盗，必属于根据202号方案肯定将一无所获的那101名海盗之列。
205号海盗的命运又如何呢？他可没有这样走运了。他不能指望203号和204号支持他的方案，因为如果他们投票反对205号方案，就可以幸灾乐祸地看到205号被扔到海里去喂鱼，而他们自己的性命却仍然能够保全。这样，无论205号海盗提出什么方案都必死无疑。206号海盗也是如此——他肯定可以得到205号的支持，但这不足以救他一命。类似地，207号海盗需要104张赞成票——除了他收买的100张赞成票以及他自己的1张赞成票之外，他还需3张赞成票才能免于一死。他可以获得205号和206号的支持，但还差一张票却是无论如何也弄不到了，因此207号海盗的命运也是下海喂鱼。
208号又时来运转了。他需要104张赞成票，而205、206、207号都会支持他，加上他自己一票及收买的100票，他得以过关保命。获得他贿赂的必属于那些根据204号方案肯定将一无所获的人（候选人包括2到200号中所有偶数号的海盗、以及201、203、204号）。

现在可以看出一条新的、此后将一直有效的规律：那些方案能过关的海盗（他们的分配方案全都是把金子用来收买100名同伙而自己一点都得不到）相隔的距离越来越远，而在他们之间的海盗则无论提什么样的方案都会被扔进海里——因此为了保命，他们必会投票支持比他们厉害的海盗提出的任何分配方案。得以避免葬身鱼腹的海盗包括201、202、204、208、216、232、264、328、456号，即其号码等于200加2的某一方幂的海盗。
现在我们来看看哪些海盗是获得贿赂的幸运儿。分配贿赂的方法是不唯一的，其中一种方法是让201号海盗把贿赂分给1到199号的所有奇数编号的海盗，让202号分给2到200号的所有偶数编号的海盗，然后是让204号贿赂奇数编号的海盗，208号贿赂偶数编号的海盗，如此类推，也就是轮流贿赂奇数编号和偶数编号的海盗。
结论是：当500名海盗运用最优策略来瓜分金子时，头44名海盗必死无疑，而456号海盗则给从1到199号中所有奇数编号的海盗每人分1块金子，问题就解决了。由于这些海盗所实行的那种民主制度，他们的事情就搞成了最厉害的一批海盗多半都是下海喂鱼，不过有时他们也会觉得自己很幸运——虽然分不到抢来的金子，但总可以免于一死。只有最怯懦的200名海盗有可能分得一份脏物，而他们之中又只有一半的人能真正得到一块金子，的确是怯懦者继承财富。

flyinsun · 发表于 2004-5-29 02:19:35

<

>和和，海盗的题是微软的应聘题吧。<

>我做过一千块金币，8个人的情形，总之就是递推，从3个人向上推。3个人的时侯，第一个提议的无论如何分，都会通过。再这样推到10个人就行了，有点烦，但想法很简单。我初二的时侯就搞出来了

Newton1983 · 发表于 2004-5-30 07:20:31

<

RE>6月征题海岛分金问题改为以下的帽子颜色问题：</PRE><

RE>“有若干种颜色的帽子，每种若干顶。假设有若干个人从前到后</PRE><

RE>站成一排，给他们每个人头上戴一顶帽子。每个人都看不见自己戴的</PRE><PRE>帽子的颜色，而且每个人都看得见在他前面所有人头上帽子的颜色，</PRE><PRE>却看不见在他后面任何人头上帽子的颜色。现在从最后那个人开始，</PRE><PRE>问他是不是知道自己戴的帽子颜色，如果他回答说不知道，就继续问</PRE><PRE>他前面那个人。一直往前问，那么一定有一个人知道自己所戴的帽子</PRE><PRE>颜色。”为什么？</PRE>

[此贴子已经被作者于2004-5-31 22:49:17编辑过]

Newton1983 · 发表于 2004-6-28 04:20:22

<

>问题参考答案：<

>A题：下载地址<

><a href="http://www.bossh.net/forums/index.php?showtopic=1562" target="_blank" >http://www.bossh.net/forums/index.php?showtopic=1562</A>

Newton1983 · 发表于 2004-6-28 04:29:47

<

>B题：<

RE 150%">当然要假设一些条件：</PRE><

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

		自动登录	找回密码
密码			注-册-帐-号