尽管这是很久以前的问题了,还是试着回答一下。 首先需要澄清一下帽子颜色的可能数:“可能都是红色,可能都是蓝色,也可能一部分红色一部分蓝色“,应该指帽子的颜色是3种。既然是3种,囚犯们讨论时可以共同约定以0、1、2分别表示三种颜色的帽子。同时我们不妨把问题简化成100个囚犯头上的帽子上都随机有0、1、2中一个数字,而要求是要他们分别报出自己帽子上的数字。 最后一人把自己前面所有人头上的数字相加,再把结果对3取模(就是除以3的余数),并报出这个结果。 从倒数第2人开始,轮到他报时都知道(自己的数字+前面所有人数字的和)对3取模的结果,同时他也知道前面所有人数字的和对3取模的结果,则他可以准确知道自己头上的数字。例如: (自己的数字+前面所有人数字的和)对3取模的结果是1,而前面所有人数字的和对3取模的结果是2,则自己头上的数字一定是2.其余同理。 也就是说最后一人有1/3的概率答对,其余人都一定可以答对。 推广开来,即使有任意n种颜色的帽子随机戴在m个人头上(即使n>>m),如果使用以上的方法和恰当的进制来计算,可以保证除最后一人有1/n的概率答对,其余人都一定可以答对。
|