UC知道一个监狱长把所有囚徒招来，对他们说，
来源：百度知道 编辑：UC知道 时间：2024/09/23 10:23:00
一个监狱长把所有囚徒招来，对他们说，
1。这次会议结束之后，你们将被隔离，互相之间再也不能交流任何信息，除了2。
2。你们唯一可以交流信息的是我桌子上的一枚硬币。因为我会经常的随机的叫你们中的一个到我的办公桌来。被叫来的人可以决定硬币哪面朝上，然后离开。接着我会叫下一个。
3。硬币的初始面由我来定。我也可以改变它在桌子上的位置。自从你们中的第一个人被叫进来，我便不会再翻硬币了。
4。如果有一天你们中的一个声称所有人都曾经被单独叫到我的办公室。如果说对了，你们就都被释放，如果说错了，你们就都将被处决。
5。现在给你们10分钟时间。
注意：除了硬币的正反面朝上，没有其他信息。也就是信息只有一位二进制。另外初始状态是不知道的。
请给出一个安全的策略，让这些囚犯有机会被全部释放，而被处决的可能为0
1。这次会议结束之后，你们将被隔离，互相之间再也不能交流任何信息，除了2。
2。你们唯一可以交流信息的是我桌子上的一枚硬币。因为我会经常的随机的叫你们中的一个到我的办公桌来。被叫来的人可以决定硬币哪面朝上，然后离开。接着我会叫下一个。
3。硬币的初始面由我来定。我也可以改变它在桌子上的位置。自从你们中的第一个人被叫进来，我便不会再翻硬币了。
4。如果有一天你们中的一个声称所有人都曾经被单独叫到我的办公室。如果说对了，你们就都被释放，如果说错了，你们就都将被处决。
5。现在给你们10分钟时间。
注意：除了硬币的正反面朝上，没有其他信息。也就是信息只有一位二进制。另外初始状态是不知道的。
请给出一个安全的策略，让这些囚犯有机会被全部释放，而被处决的可能为0
需要第一个进入办公室的人做标识和记录人才行。
第一个进入办公室的人，随便选择硬币一面朝上（A面）
其他人：
如果第一次进入办公室，且硬币A朝上，则翻转一次，让B朝上；
如果第一次进入办公室，且硬币B朝上，则不变，让B朝上；
如果不是第一次进入办公室，且A朝上，且自己以前曾经翻转过硬币，则不改变硬币状态，让A朝上；
如果不是第一次进入办公室，且A朝上，且自己以前没有翻转过硬币，则改变一次硬币状态，让B朝上；
如果不是第一次进入办公室，且B朝上，且自己以前曾经翻转过硬币，则不改变硬币状态，让B朝上。
如果不是第一次进入办公室，且B朝上，且自己以前没有翻转过硬币，则不改变硬币状态，让B朝上。
这样一来，只有进入到办公室的其他犯人有权力让硬币变为A-B，且只有第一个进入办公室的标识人有权力让硬币变为B-A。而其他犯人而言，只有一次行使硬币变A-B的机会。也就是说，当其他每个犯人都至少进入了一次办公室且翻转过唯一一次硬币之后，标识人翻转硬币的总次数=N-1，N为犯人数，这个时候说明大家都进去过了。