论文部分内容阅读
许多读者朋友可能会对前面提到的谜题感兴趣。它的答案是什么？如果回答这种策略并不存在（事实上，一般人不经过仔细思考的话，很可能就会否定这种策略的存在），那么应聘者就在一个重要的面试问题上失败了。但要想找到这个策略，当然也不容易。实际上，这道“100顶帽子”谜题是结合了运筹学、逻辑学和数学相关知识的一道中等难度的谜题。为了帮助读者理解它的解答思路，我们先来看它的简化版：警察抓来4个囚犯，但监狱已经满员，于是典狱长想出了一个解决办法，他给囚犯们出了一道谜题。他让其中3个囚犯站成一列，第4个囚犯则被一扇屏风挡住。典狱长给每个囚犯各戴一顶帽子，并且对囚犯们说，其中两顶帽子是黑色的，另外两顶是白色的。每个囚犯都只能看见他前面的囚犯戴的帽子，但看不见他自己或他后面的囚犯戴的帽子。屏风背后的囚犯看不见自己的帽子，另外3个囚犯也看不见他。此外，囚犯之间不得有任何交流。如果任何一个囚犯能以100%的准确度（而不是靠猜测）报告典狱长他自己戴的帽子是什么颜色，那么4个囚犯均获释;但如果任何一个囚犯答错，则4个囚犯都会被立即处死。谜题就是：不管典狱长怎样分配帽子，找到让所有囚犯逃生的策略。
为了方便解释答案，我们对排成列的囚犯从前到后分别给予代号D、C和B（如上图）。也就是说，C能看见B的帽子，D能看见B和C的帽子。囚犯们知道每种颜色的帽子只有两顶，因此，如果D观察到B、C的帽子同色，D就能推断出他自己的帽子为另一种颜色。然而，如果B、C的帽子不同色，D就无法判断自己帽子的颜色，也就只能不说话。其实这时候的关键在于C。从D的不说话，C就能判断出他和B的帽子颜色不同。因为C能看见B的帽子是什么颜色，所以他就能断定自己的帽子是与B不同的颜色。
与许多这类谜题一样，上述答案依赖于一种假设：所有参与者都是理性的和足够聪明的，因此足以作出合适的推断。否则，上述逃生策略就行不通。在解决这道谜题后，我们可以对交流的本质进行一些思考：囚犯D有意的沉默是否违反了“不能交流”的规则？交流经常被定义为“信息传递”，而D不说话（不传递信息）恰恰提醒了C（或者说向C传递了一种无声信息）。为了澄清这一点，谜题中“囚犯之间不得有任何交流”可改为“囚犯之间不得有任何语言交流”。
把上述谜题稍作改动：囚犯们知道黑色帽子有3顶，白色帽子只有1顶，并且屏风同一侧的3个囚犯能相互看见（但A依然看不到自己所戴帽子的颜色），即B看得见C和D，C看得见B和D，D看得见B和C。但B、C和D都看不见A，而A也看不见他们。那么，逃生策略是什么？
答案要分两种情况。第一种，3个囚犯中有1个戴的正是白色帽子，那么其余两个自然一下就能判断自己的帽子是黑色的。第二种，囚犯BCD戴的都是黑色帽子，A戴的是白色帽子。由于他们每个人都看到其他两人戴的都是黑帽子，所以他们3人中无人敢断言自己的帽子是什么颜色。通过都不发言，他们就能推断他们3人戴的都是黑色帽子，而A戴的帽子是白色的。
再对上述谜题作改动：只有3个囚犯，帽子却有5顶，其中2黑3白。3个囚犯被命令头朝前站成一列，其中A在最前面，C在最后。他们被告知有2黑3白共5顶帽子。每个囚犯都被戴上1顶帽子，且他们都只能看见自己前面的人所戴的帽子，但看不见自己和后面的人所戴的帽子。谁能第一个准确说出自己的帽子是什么颜色，谁就获释。但是，囚犯之间不得进行语言交流。
答案要分两种情况。首先，假设A戴的是黑帽子。如果B戴的也是黑帽子，C立即能判断自己戴的是白帽子。如果A戴的是黑帽子，B戴的是白帽子，C就无法判断自己戴的帽子是什么颜色。从A戴的黑帽子和C的不发声，B就能知道自己和A戴的帽子颜色不同，因此自己戴的必定是白帽子。总结前述，如果A戴的是黑帽子，B或C将立即判明自己所戴帽子的颜色。
第二种情况，假设A戴的是白帽子。此时，C看不到两顶黑帽子，因此无法判断自己的帽子颜色。B只看见1顶白帽子，所以也无法断定自己的帽子颜色。这样一来，A、B和C都会保持短暂沉默，直到A最终判断出自己一定戴的是白帽子，原因是C和B都不发声。
在这个谜题中，依然要假定3个囚犯都很聪明。另外需要假定，C囚犯无法判断自己的帽子颜色，就是因为看见其他两个囚犯戴的帽子都不是黑色的，或者黑白各1顶。如果他看见了两顶黑帽子，那么他就能断定自己戴的是白帽子。还需要假定，其他两个囚犯能理解第一个囚犯的反应，利用这一信息并结合自己亲眼所见，推断出自己的帽子颜色。
再来看3个囚犯和3顶帽子的情况：每个囚犯被随机戴一顶帽子，要么红色，要么蓝色。每个囚犯都能看见其他两个囚犯的帽子，但看不见自己的帽子。每个囚犯要么猜测自己的帽子颜色，要么保持沉默。3名囚犯必须同时作答或不答，因此就不可能根据他人的猜测来作出自己的猜测。如果至少有一个人答对，其他人不回答，那么他们全部获释。否则，他们都会被处决。在此之前，3名囚犯可以商量对策。这个谜题（对策）没有100%的胜算策略，问题是：最佳策略是什么？什么策略能保证最高胜算？
答案其实并不难。3个囚犯在同时猜的时候，最佳策略是这样的：如果看到另外两人帽子颜色不一样，就保持沉默;如果看到另外两人的帽子都是红色，就说蓝色;如果看到另外两人的帽子颜色都是蓝色，就说红色。
为什么这样呢？3个囚犯，两种帽子颜色，则其排列组合只有8种：红红红，红红蓝，红蓝红，红蓝蓝，蓝红红，蓝红蓝，蓝蓝红，蓝蓝蓝。也就是说，在所有8种情况下，只有两种情况是三人的帽子同色，而有6种情况是有一人的帽子和另两人不同色。即依照上述对策，回答正确的概率为75%，可以说是最佳策略。
为了方便解释答案，我们对排成列的囚犯从前到后分别给予代号D、C和B（如上图）。也就是说，C能看见B的帽子，D能看见B和C的帽子。囚犯们知道每种颜色的帽子只有两顶，因此，如果D观察到B、C的帽子同色，D就能推断出他自己的帽子为另一种颜色。然而，如果B、C的帽子不同色，D就无法判断自己帽子的颜色，也就只能不说话。其实这时候的关键在于C。从D的不说话，C就能判断出他和B的帽子颜色不同。因为C能看见B的帽子是什么颜色，所以他就能断定自己的帽子是与B不同的颜色。
与许多这类谜题一样，上述答案依赖于一种假设：所有参与者都是理性的和足够聪明的，因此足以作出合适的推断。否则，上述逃生策略就行不通。在解决这道谜题后，我们可以对交流的本质进行一些思考：囚犯D有意的沉默是否违反了“不能交流”的规则？交流经常被定义为“信息传递”，而D不说话（不传递信息）恰恰提醒了C（或者说向C传递了一种无声信息）。为了澄清这一点，谜题中“囚犯之间不得有任何交流”可改为“囚犯之间不得有任何语言交流”。
把上述谜题稍作改动：囚犯们知道黑色帽子有3顶，白色帽子只有1顶，并且屏风同一侧的3个囚犯能相互看见（但A依然看不到自己所戴帽子的颜色），即B看得见C和D，C看得见B和D，D看得见B和C。但B、C和D都看不见A，而A也看不见他们。那么，逃生策略是什么？
答案要分两种情况。第一种，3个囚犯中有1个戴的正是白色帽子，那么其余两个自然一下就能判断自己的帽子是黑色的。第二种，囚犯BCD戴的都是黑色帽子，A戴的是白色帽子。由于他们每个人都看到其他两人戴的都是黑帽子，所以他们3人中无人敢断言自己的帽子是什么颜色。通过都不发言，他们就能推断他们3人戴的都是黑色帽子，而A戴的帽子是白色的。
再对上述谜题作改动：只有3个囚犯，帽子却有5顶，其中2黑3白。3个囚犯被命令头朝前站成一列，其中A在最前面，C在最后。他们被告知有2黑3白共5顶帽子。每个囚犯都被戴上1顶帽子，且他们都只能看见自己前面的人所戴的帽子，但看不见自己和后面的人所戴的帽子。谁能第一个准确说出自己的帽子是什么颜色，谁就获释。但是，囚犯之间不得进行语言交流。
答案要分两种情况。首先，假设A戴的是黑帽子。如果B戴的也是黑帽子，C立即能判断自己戴的是白帽子。如果A戴的是黑帽子，B戴的是白帽子，C就无法判断自己戴的帽子是什么颜色。从A戴的黑帽子和C的不发声，B就能知道自己和A戴的帽子颜色不同，因此自己戴的必定是白帽子。总结前述，如果A戴的是黑帽子，B或C将立即判明自己所戴帽子的颜色。
第二种情况，假设A戴的是白帽子。此时，C看不到两顶黑帽子，因此无法判断自己的帽子颜色。B只看见1顶白帽子，所以也无法断定自己的帽子颜色。这样一来，A、B和C都会保持短暂沉默，直到A最终判断出自己一定戴的是白帽子，原因是C和B都不发声。
在这个谜题中，依然要假定3个囚犯都很聪明。另外需要假定，C囚犯无法判断自己的帽子颜色，就是因为看见其他两个囚犯戴的帽子都不是黑色的，或者黑白各1顶。如果他看见了两顶黑帽子，那么他就能断定自己戴的是白帽子。还需要假定，其他两个囚犯能理解第一个囚犯的反应，利用这一信息并结合自己亲眼所见，推断出自己的帽子颜色。
再来看3个囚犯和3顶帽子的情况：每个囚犯被随机戴一顶帽子，要么红色，要么蓝色。每个囚犯都能看见其他两个囚犯的帽子，但看不见自己的帽子。每个囚犯要么猜测自己的帽子颜色，要么保持沉默。3名囚犯必须同时作答或不答，因此就不可能根据他人的猜测来作出自己的猜测。如果至少有一个人答对，其他人不回答，那么他们全部获释。否则，他们都会被处决。在此之前，3名囚犯可以商量对策。这个谜题（对策）没有100%的胜算策略，问题是：最佳策略是什么？什么策略能保证最高胜算？
答案其实并不难。3个囚犯在同时猜的时候，最佳策略是这样的：如果看到另外两人帽子颜色不一样，就保持沉默;如果看到另外两人的帽子都是红色，就说蓝色;如果看到另外两人的帽子颜色都是蓝色，就说红色。
为什么这样呢？3个囚犯，两种帽子颜色，则其排列组合只有8种：红红红，红红蓝，红蓝红，红蓝蓝，蓝红红，蓝红蓝，蓝蓝红，蓝蓝蓝。也就是说，在所有8种情况下，只有两种情况是三人的帽子同色，而有6种情况是有一人的帽子和另两人不同色。即依照上述对策，回答正确的概率为75%，可以说是最佳策略。