监狱的囚犯问题

呵呵呵

尽管这是很久以前的问题了，还是试着回答一下。 首先需要澄清一下帽子颜色的可能数：“可能都是红色，可能都是蓝色，也可能一部分红色一部分蓝色“，应该指帽子的颜色是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的概率答对，其余人都一定可以答对。