问题概述1
习题4：假设你是最近被捕的P个囚犯之一。监狱长是个疯狂的计算机科学家，他给出了以下启示：
- 你们今天可以在一起商定一个策略，但是从今天以后，你们将会被隔开关在不同的房间，相互间无法再进行交流。
- 我们建造了一种“开关房间”，里面有一个灯开关，这个开关只能为开和关，且没有和任何东西相连。
- 我将不时地从你们中间随机选择一位到“开关房间”里来。这名囚犯可以拨动开关（从开到关、或相反），也可保持开关的状态不变。其他人这时都不能进入房间。
- 每一名囚犯都将任意多次地进入开关房间。更确切地说，对于任意的N，你们中得每个人最终都至少进入这个房间N次。
- 任何时刻，任意一名囚犯都可以宣布：“我们所有的人都已经至少到过开关房间一次了。”如果该断言是对的，我将释放你们。如果错了，我就把你们全都送去喂鳄鱼。谨慎抉择吧！ 提示：所有的囚犯不必做相同的动作。
- 在开关初始状态为关的情况下，设计一个可以成功取胜的策略。
- 在不知道开关初始状态的情况下，设计一个可以成功取胜的策略。
问题分析1
首先，我们每个人之间不能通信，因此“开关房间”是我们获取信息的唯一方法。而且能获取的信息只有开关的状态。提示指出了，每个囚犯做出的动作可以是非对称的。这样如果有一个人专门负责计数，其他人有统一的搬动开关的协议，这个问题是不难解决的。
问题解答1
假设：依据条件4，每个囚犯有无穷多的机会进入房间，所以囚犯有无限长的寿命；每个囚犯呆在开关房中的时间有限；每个囚犯去开关房的间隔时间有限；计算机科学家寿命无限；囚犯只要没被喂鳄鱼就可以无限生存，不会生病等；开关房没有任何陷阱，不会出任何故障；开关不会损坏。
解答：
- 如果初始状态是关，对囚犯编号为1~N(N > 1, N是正整数)。
- 1号囚犯每次进入房间时先观察开关，如果是关，不做任何事，否则心中的计数器自加1(初始为0)，并且反转开关状态。
- 2到N号囚犯每次进入房间，先观察开关状态，如果是关则打开，并且只能打开一次。如果曾执行过此操作，以后一概不执行。如果是开，则不动。
- 当1号囚犯的计数器累计到(N - 1)时就可以对着计算机科学家大喊“我们所有的人都已经至少到过开关房间一次了”
- 如果初始状态不确定时
- 当初始状态为关时，使用第一种方案可行。
- 当初时状态为开时，使用第一种方案可能会漏数一个人，所有人可能会被喂鳄鱼。
- 如果已经数到了(N - 1)时，有两种可能：(a)所有人都到达过房间至少一次，有一人因为发现开关是开什么都没做就走了。(b)有一个人没到过房间，因为初始状态按照上述协议被计算了。
- 如果已经数到了(N - 1)时，假设还有一个始终未进入房间(初始的开状态被计数)。这个时候让负责计数的1号囚犯外所有囚犯重新获得一次搬动开关的机会，搬动协议如上述方案。而且可以得知此时开关状态一定是关闭状态。
- 上述假设始终未进入房间的人仍然未进入房间且其他人都进过时，1号所得总计数应当是 (N - 1) + (N - 2) = (2N - 3)，而这时如果此人进入一次则是 (2N - 2)。
- 所以，每个人有两次机会将开关由关改为开，并且计数器至少是(2N - 2)时才可断言“我们所有的人都已经至少到过开关房间一次了”。
问题概述2
习题5：上题中监狱长又有了另外一个想法。他命令囚犯们站成一排，每个人都戴着一顶红色或蓝色的帽子。没有人知道自己所戴帽子的颜色，也不知道他后面所有人帽子的颜色，但能看见前面所有人帽子的颜色。监狱长从队伍的后面开始询问每个囚犯，让他们猜测自己帽子的颜色。囚犯们自能回答“红色”或“蓝色”。如果他答错了，就会被送去喂鳄鱼。如果他答对了，则会被释放。每个囚犯都能听到后面所有人得回答，但不知道答案是否正确。
囚犯们在站队之前可以商讨一个策略（监狱长是听着的）。一旦站好队后，每个人除了能回答“红色”或“蓝色”以外，再也不能以其他任何方式进行交流。
设计一个能够保证P个囚犯中至少有(P - 1)个会被释放的策略。
问题分析2
这里可以根据题目要求“P个囚犯中至少有(P - 1)个会被释放”小小的Hack一下。也就是说有一个人可以不保证他的死活，那么这个人将是其他人获救的关键。显然，如果这个人起到了作用，很大概率他就是站在最后一个位置的人。
问题解答2
假设：那个不在乎生死的人的确大公无私，将自己的生死置之度外，并不会与其他人发生矛盾、背叛等。
解答：我们知道当前需要报出颜色的人的答案会全局广播，这是很重要的，也就是我们后面每个人都可以知道以前的人的帽子颜色。在当前的情境下，我们肯定能够得到的消息是：每个人眼前所有的囚犯的红色帽子数目及位置、蓝色帽子数目及位置、奇偶性。那么假设我能够解决这个问题，那么选择第一个人自我牺牲，从第二个人开始他们说的都会是对的。这样其实我也能得知从第二个到当前某个人身后的所有信息，因为说出红或蓝时会全局广播。这就够了。
第一个人首先要知道前面所有人中红色帽子的个数，如果红色帽子有奇数个就说“红色”，否则就说蓝色。
假设第一个人说了“红色”：
- 这时候，第2个人如果是红色帽子会看到前方有偶数个红色的帽子，他一定会说红色。反之肯定会说蓝色，因为除了自己外一共有有奇数个红色，自己要是红色，第一个人就一定不会说红色，会产生矛盾。
- 而从第3个人(假设有第3个人)开始，都会知道第2个开始到他自己之前的人头顶上是什么颜色的帽子，并且可以统计红色帽子的奇偶性，可以推出如下协议：
- 如果自己前面有偶数个红帽，自己之后也有偶数个红帽，自己就是红帽。
- 如果自己前面有奇数个红帽，自己之后也有奇数个红帽，自己就是红帽。
- 如果自己前面有奇数个红帽，自己之后也有偶数个红帽，自己就是蓝帽。
- 如果自己前面有偶数个红帽，自己之后也有奇数个红帽，自己就是蓝帽。
假设第一个人说了“蓝色”：
- 那么，规则全部与上述相反。第二个人如果看到有奇数个帽子才会说红色，反之就是蓝帽。
- 如果自己前面有偶数个红帽，自己之后也有偶数个红帽，自己就是蓝帽。
- 如果自己前面有奇数个红帽，自己之后也有奇数个红帽，自己就是蓝帽。
- 如果自己前面有奇数个红帽，自己之后也有偶数个红帽，自己就是红帽。
- 如果自己前面有偶数个红帽，自己之后也有奇数个红帽，自己就是红帽。
然而，第一个人则要碰碰运气，理论上他有50%的概率被喂鳄鱼或者50%的概率重获新生，人民会记住他的。(END)