监狱的囚犯问题

xyh · 发表于 2013-10-8 08:27:45

一座监狱专门用来关押死刑犯人。犯人进进出出，每天只能有一部分被处死刑，可是死刑的威慑力似乎不够大，不断有新的死刑犯进来。而且，常常进来的比出去的还多。 zzwave.com

这么一来，监狱的犯人不断积累，就存在了先处决哪些犯人的问题了。

监狱长xyh® 有权决定先处死谁。根据表现，表现好的，真心悔改的，往往可以得到推至处决。

随着时间的积累，出现了一批真心悔改的，不断得到推迟处决的罪犯。大约有100来人吧。在这里已经呆了好几十年了。由于表现得很好，即使释放出去也没有人认为他们会对社会造成危害了。

此时恰巧司法部长husonghu® 视察监狱，发现这一问题。于是叫来监狱长xyh® 严厉质问道: 这些杀人犯，为什么还没有被处死？不处死他们，死刑的威慑力如何体现？

监狱长说明了情况，司法部长表示理解。可是这个问题总要解决吧。于是，教育部长开开心心® 灵机一动，提出了一个解决方案。大家都交口称赞，认为该方案可行。这个方案就是用红帽子，蓝帽子解决100位死囚的生死。

1、随机的找来100顶帽子，这100顶帽子，可能都是红色，可能都是蓝色，也可能一部分红色一部分蓝色。

2、随机的把这些帽子戴在每位囚犯的头上

3、让这些犯人站成一列，后面的人可以看到其前面所有囚犯的帽子颜色；而站在前面的囚犯，可以听到其后面所有囚犯的说话

4、狱卒从最后一名囚犯问起，让他猜自己头上帽子的颜色。只允许说自己头上帽子的颜色，不允许说别的。说完后就把他拉出去。如此继续，一直到最前面。

5、拉出去后，这位囚犯要么被处决，要么被释放。如果是说对了，立即释放；说错了，立即处决。尽管站在前面的囚犯听到后面说的话，但是他们不知道这位囚犯是被处决还是被释放。

6、为表示人道，司法部长同意这100名囚犯事先有1分钟的时间在一起讨论。

请问，在这珍贵的1分钟时间内，你如何帮助这100名真心悔改的囚犯，让他们尽可能多的被释放？

1分钟，看谁能想出最佳放案。

学生 · 发表于 2013-10-9 21:32:37

好像以前在本坛见过这题。
商定最后一人用所见前方红色（或商定用蓝色）帽数的奇偶来猜自己头上帽子的红蓝。于是，只有最后一人有被处死的风险。

sean9991 · 发表于 2013-10-9 22:13:32

An interesting variation of this question is what if there are 101 prisoners.

same · 发表于 2013-11-1 23:26:54

The same way.

东北逍遥客 · 发表于 2013-11-5 07:29:12

每人简单报出前面犯人帽子颜色即可, 这样只有最后面的犯人(最先报数的)有50%的死亡可能.

冷眼看戏的Lili · 发表于 2013-11-6 17:37:01

不行吧。举个反例：红蓝交替地给这一百人戴上帽子，若按您的方案，只有最前面的一个活下来。

东北逍遥客 · 发表于 2013-11-8 04:34:55

你说得对, 我把题意给搞错了, 只是知道自己颜色没有用, 自己还得活呢:). 还得用上面说的奇偶法. 感谢指正!

sure · 发表于 2014-1-27 05:56:26

第一个人说第二个人帽子的颜色，只说一个字，如“红”。第二个人看下一个人的颜色如果于自己相同，只说一个“红”字，如果不同，说“红色”。依次类推，每个人可从前一个人说的是单字或双字来判断自己帽子的颜色，然后以单字或双字来告诉下一个人于自己的帽子颜色相同或不同。只有第一个人有50%的死亡可能，其余均可活。

呵呵呵 · 发表于 2014-3-9 11:19:02

尽管这是很久以前的问题了，还是试着回答一下。

首先需要澄清一下帽子颜色的可能数：“可能都是红色，可能都是蓝色，也可能一部分红色一部分蓝色“，应该指帽子的颜色是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的概率答对，其余人都一定可以答对。

bhg · 发表于 2014-6-30 19:09:17

test

		自动登录	找回密码
密码			立即注册

动态微博

监狱的囚犯问题

回复：监狱的囚犯问题

回复：回复：监狱的囚犯问题

回复：回复：回复：监狱的囚犯问题

回复：监狱的囚犯问题

回复：回复：监狱的囚犯问题

回复：回复：回复：监狱的囚犯问题

回复：监狱的囚犯问题

回复：监狱的囚犯问题

回复：监狱的囚犯问题