第1章 引言
- 习题1.4：P个囚犯被分隔在不同房间，互相不能通信。有一个“开关房间”，里面有个灯，只能处于开关状态。每天监狱长随机选一个囚犯进去开关房间，囚犯可以改变灯的状态，也可以不变。当某天某个囚犯可以肯定地说：所有囚犯都至少到过开关房间一次，所有囚犯就会被释放；若他说错了，所有囚犯都处死。问囚犯在下列情况下该如何制定策略：
- 开关初始状态为关。对囚犯编号，囚犯0维持一个计数器初值为0，第一次进入房间将灯打开，之后每次进入房间看到如果灯是关的就将其打开并计数器加一，每次看到灯是开的不做任何事。其他囚犯如果进入房间看到灯是开的且之前没做过任何动作就将其灭掉，否则不做任何事。当囚犯0的计数器变成P-1时就能确定条件满足了
- 开关初始状态未知。此时囚犯0第一次如果看到灯是灭掉的就打开，如果是打开的就不动，之后他每次看到灭掉的灯计数器就加一。他的计数器要到2P-1才能确定条件满足，而所有其他囚犯在前两次看到灯打开时都要将其灭掉，之后不做任何事。
- 习题1.4：P个囚犯站成一排，每人头上带上一定红色或蓝色的帽子，每人只能看到前面的人的帽子颜色，不知道自己及自己身后的人的帽子颜色。监狱长从后面开始逐个询问囚犯，让每人猜自己头上帽子颜色，猜对释放猜错处死。每个囚犯都可以听到后面的人的回答但不知道对错。囚犯事前可以商定策略。求一个至少释放P-1个囚犯的策略。解：最后一个囚犯说出前面所有囚犯头上红色帽子的个数是奇数还是偶数（例如约定说红色表示奇数），之后每个囚犯根据后面囚犯的话和前面的奇偶情况判断自己的颜色。