囚犯问题集

1.聪明的囚犯抓豆子问题

5个囚犯，分别按1-5号在装有100颗绿豆的麻袋抓绿豆

规定

   1. 他们之间不能交流
   2. 每人至少抓一颗，抓得最多和最少的人将被处死
   3. 抓的时候，可以摸出剩下的豆子数
   4. 他们都是很聪明的人，其原则是先求保命，再去多杀人
   5. 100颗不必都分完
   6. 若有重复的情况，则也算最大或最小，一并处死

问：他们中谁的存活机率最大？

2.100个囚犯的脱狱问题(1)

国王招来100个囚犯，对他们说：你们犯的是死罪，本应该将你们统统杀掉，但我慈悲为怀，给你们一次求生的机会。15分钟以后，你们将被关进一个有100间隔离牢房的监狱里，每人一间牢房，都与外界隔绝，什么也听不见、看不到，连时间都没法计算，更别说获得外界的任何信息。（送饭除外，但也是不规律的送）

这所监狱有一个院子，每天会随机（注意是完全随机）打开一间牢房的门，让那个囚犯到院子里来放风。院子里有一盏路灯，放风的囚犯可以控制它的开关，将它打开或是关闭。除囚犯之外，其他人都不会去碰开关。这盏灯会永远有充足的能源供应，如果灯泡坏了或是电路出了故障会马上修好，当然修理人员不会改变灯的状态（开或关）。

除了开关这盏灯，放风的囚犯放风时留下的任何其它痕迹都会在夜晚被清除干净（包括在灯上作的任何记号）。

牢房是完全封闭的，院子里的灯光在牢房里看不到。只有放风出到院子里的人才能看到。

好了现在我向你们提出一个要求，只要你们做到了，就可以全部获得释放：

若干天以后，你们中只要有任何一个人能够向我证明所有的人都曾到院子里去过，你们就全体释放。当然要有证据！因为我只会给你们一次机会，如果向我证明的那个人无法自圆其说，你们就全部砍头。所以，要珍惜这次机会。如果你们永远做不到我的要求，你们就全部囚禁到死。

现在给你们15分钟商量你们的方案。15分钟以后，你们将被关进我刚才说的那个监狱，永远无法再交流。

请你帮助囚犯给出一个方案


3.100个囚犯的脱狱问题(2)

话说有一国王找到100个囚犯，每个人都剃了光头。

国王对他们说：一会儿有人会在你们头上写上1-100之间的随机数。你们只要有一个人能说对大家头上所有数字的和，就都放了。否则统统赠送给芙蓉姐姐做宠物。给你们一炷香的时间好好商量一下对策。

这帮子囚犯都是学过基本算数的，加减乘除都没问题。

一炷香之后，国王的巫师屏蔽了他们之间的交流任何交流，包括肢体交流都不可行，每个人只能说一个数，说的时候其他人也听不到 - 结果每个囚犯都能看到别人头上写的啥，但没办法知道自己的数字。

囚犯们采用什么策略才能保证一定会被释放呢？

4.100个囚犯的脱狱问题(3)

100个囚犯，每人有一个从1到100的不重复不遗漏的号码，国王把这些号码收集起来，打乱放进100个箱子里，每个箱子里有且仅有一个号码。囚犯们一个一个地来到100个箱子面前，每人可以打开至多50个箱子来寻找自己的号码，可以一个一个打开（即可以根据之前箱子里看到的号码来决定后面要打开的箱子）。如果有一个囚犯没有找到自己的号码，那么这100个人一起被处死；只有当所有的囚犯都找到了自己的号码，他们才会被国王全部释放。

囚犯们可以在没开箱子前商量对策，但是一但打开了箱子，他就不能告诉别人箱子和号码的对应关系。问他们应该用什么样的策略以保证最大的存活概率？