【谜题】XKCD谜题系列：100个囚徒+100个海盗

1. 100个囚徒

100个囚徒被关在监狱里。他们被告知，一小时后他们会被分别带入没有窗子、隔音的小房间。接着，一个一个，顺序随机，他们会从小房间中被带出来审问，再送回小房间。所有的审讯都会在同一个房间进行，哪个房间里有一个电灯，还有一个可以控制电灯的开关。最开始时，灯是关着的。当处于审讯室时，囚徒可以自由地将电灯打开或关上，无论几次都可以，而看守不会碰开关。小房间里看不到审讯室灯的状态。每次只审讯一个人，但同一个人可以被审讯多次。除了那个电灯开关以外，囚徒之间没有互相沟通的方法；且审讯时间随机，所以无法从中获得信息。在任何时候，任何一个囚徒都可以在审讯中宣称：“所有人都已至少被审讯了一次。”如果说对了，所有人都会被释放；如果说错了，所有人都会被处决。现在开始，囚徒们有一个小时的时间商量策略，之后就会被互相隔离。怎样能让他们被成功释放？

100 prisoners are being held in a prison. They are told that in one hour, they will all be taken to separate windowless, soundproof rooms. One at a time, and in a random order, they will be taken from their rooms, interrogated, and then sent back to their rooms. All interrogations will take place in the same room, which contains one light bulb and the switch that operates it. The light is initially off, but the inmates are free to toggle the switch as often as they want, whenever they are in the interrogation room, and the guards will not toggle the switch at all. No person can see the light from his room. Only one person is interrogated at a time, each person can be interrogated multiple times, and they have no way of communicating besides the light switch. The length and amount of time between interrogations is random, so no help there. At any time, any person under interrogation may state, “Everyone has been interrogated at least once.” If this statement is true, everyone will be released. If it is false, all of the people will be executed. The people have one hour to work out their strategy before they’re isolated for good. How do they get released?

1.2 100个囚徒（续）

(1) 加分项，如果囚徒们不知道最开始电灯是开着还是关着，他们有什么策略吗？

(2) 另外，假设每天一次审讯。在这种情况下有更有效率的解。

For bonus points, what is their strategy if they don’t know the initial state of the light switch?

Alternative: suppose there is one interrogation per day. In this case there exist different more efficient solutions.

2. 100个海盗

100个海盗（p1,p2,…p100）在分50个金币。海盗有等级顺序，也就是说，p1是海盗头目，p2比他低一级，p3比p2低一级，等等。分金币的过程是这样的：由仍然活着的、具有最高等级的海盗提出一个分金币的方案，所有仍然存活的海盗（包括提出方案者）对此方案投票。如果至少一半投票的海盗投赞成票，方案通过；否则提出方案的海盗会被处决，由下一等级海盗继续这个过程。每个海盗都非常聪明、理智、逻辑满分。每个海盗的优先级为：首先活着，然后得到尽可能多的金币，最后希望尽可能多的其他海盗被杀。所以如果两种方案他都能存活，他会选择他拿到金币更多的方案；如果两种方案他都能存活且获得同样数额的金币，他会选择让更多其他海盗死亡的方案。在这些条件下，金币会怎样分割呢？

100 pirates (p1, p2, … p100) are dividing up a treasure consisting of 50 indivisible gold coins of equal worth. The pirates have a total-order hierarchy, i.e. pirate p1 is the head pirate, p2 is a rank lower in the order, p3 lower still, … The process works like this: The highest ranking pirate who is still alive proposes how he would like to divide the treasure. Then all living pirates (including him) vote on the proposal. If at least half of the pirates alive vote for the proposal, then it is accepted, otherwise the pirate who made the proposal is killed and the process is repeated. The pirates are perfectly intelligent, logical and rational (see Blue Eyed Puzzle). Each pirate’s priorities are, in this order: Survival, wealth (getting the highest number of coins possible), bloodthirstiness (seeing as many pirates killed as possible, other than himself). In other words a pirate will always choose an outcome in which he lives over one in which he dies. Given two outcomes in which he lives, he will choose the one where he gets more coins. And given two outcomes in which he lives and gets the same number of coins he will choose the one in which the highest number of other pirates die. How will the gold coins be divided?

2.2 100个海盗（续）

加分项：如果有200个海盗，金币会怎么分割呢？

Note: For bonus points, how will the gold coins be divided if there are 200 pirates?

谜题, 100, XKCD, 囚徒, 海盗