帽子谜题复杂版

现在来看“100顶帽子谜题”。囚犯们可以乱猜一通，最坏情况下所有人都猜错，平均而言则会有50个人猜对。但这道题有趣的地方就在于，100个囚犯可以事先商量一种策略，也就是说，站在后面的囚犯可以利用他的答案，给前面的囚犯提供有用的信息。显然，最后面的囚犯是不可能保证自己猜对的，他猜红或猜蓝，猜对的可能性都只有一半。但囚犯们可以事先约定一种暗号。比如，最后一个囚犯可根据他前面紧挨他的 （倒数第2个）囚犯所戴帽子颜色，报出自己所戴帽子的颜色。也就是说，通过他的答案可以告诉倒数第2个囚犯其所戴帽子的实际颜色，于是倒数第2个囚犯肯定能活下来。此时，倒数第3个囚犯面临与最后那个囚犯相同的处境，并且以同样方式保证倒数第4个囚犯存活。这样下去，可以保证至少50个（倒数偶数号）囚犯存活。而对另50个囚犯来说，答对答错的可能性是50%，或者说平均会有25人猜对。这样的话，平均总共有75个囚犯存活。但这不并是最佳策略。最佳策略能保证：除了站在最后面的囚犯之外，其余99个囚犯都能答对。这个最佳策略是什么？亲爱的读者，在你继续看下去之前，不妨先动动脑子。

前面那种策略的弱点在于，排在最后的那个囚犯透露的信息不多。其实，他完全可以透露出一些与全局相关的信息，让前面所有的囚犯都可利用这些信息。比如，他可以数一数前面99个人一共有多少顶红帽子，并约定他猜“红”表示他前面共有偶数顶红帽（当然也可作其他约定）。倒数第2个囚犯也数一数他前面98个人的红帽子数量，如果数出来是奇数，那么他戴的肯定是红帽子（因为必须加上他戴的红帽子，才能保证最后那个囚犯所看见的红帽子数量为偶数）;如果他数出来的是偶数，那么他自己戴的肯定是蓝帽子。这样，倒数第2个囚犯肯定就答对了。那倒数第3人呢？如果倒数第2人说自己戴的是红帽子（这当然是确切信息），而他（倒数第3人）数到自己前面的红帽子数为偶数，那如果他自己戴的是蓝帽子，就会造成倒数的前99人中红帽子数为奇数，这与倒数第1个囚犯的准确提示不符合，因此他戴的必定是红帽子。以此类推，只要记住了后面所有囚犯的答案，再加上对前面囚犯所戴不同颜色帽子数量的奇偶性进行统计，除了排在最后的那个囚犯之外，其他99个囚犯都能答对，也就是都能活下来。这就是最佳策略，不可能再有其他策略能保证所有人都存活。

再把问题变难一点：有10个囚犯和10顶帽子，每个囚犯被随机戴一顶帽子，要么红色要么蓝色，但囚犯们不知道每种颜色的帽子数量。囚犯们被安排进不同房间，以便让每个囚犯能看见其他囚犯的帽子，但看不见自己的帽子。他们必须同时说出一个词——红或蓝。如果说出的词与自己所戴帽子的颜色相同，这个囚犯就被释放。如果足够多的囚犯获释，他们就可能回来拯救还未获释的囚犯。这些囚犯被允许有1小时的商议时间，如果他们能找到一个合理的策略，则10名囚犯中有5人肯定会获释，然后他们就可以回来拯救其他人。那么，这个策略是什么？

答案是：把囚犯们分成对子。在对子AB中，A说出他看到的B的帽子颜色，B则同时说出与他所见A的帽子颜色相反的颜色。这样，如果AB所戴帽子颜色相同，A获释，B不能获释。如果AB所戴帽子颜色不同，B获释，A不能获释。这样，总共会有5人说对。也可把囚犯们分成5人一组，共两组。其中一组假定红帽数量为偶数，另一组则假定为奇数。与前面的100顶帽子情况相似，他们可以根据这一假定推断出自己所戴帽子的颜色，但只有一组能答对，因此肯定会有5人获释。（这后一种思路为什么可行，这里不详细解释。请有兴趣的读者自行思考。若想出了正确的推理过程，可发到本刊微信号dazirantansuo，答对者可免费获得本刊下期新杂志一册。）

这些谜题的答案看起来都不太复杂。然而，若非学过这方面的知识（大多数人都没学过），或者绝顶聪明，要想在应聘时一下子就想出这样的答案显然很难。其实，完全可以把这些谜题中的10个或100个囚犯换成无穷个，依然能找出最佳策略。不过，这要用到大学数学和逻辑学知识。