每周一题 by 万精油: 囚犯问题

fzy

Professor 万精油 posted many interesting problems at 灵机一动. Some are relatively easy, and some are very difficult. But all are very interesting. I will selectively post some here. They are mainly for people who have not seen the problems. So if you have visited the forum and seen the solutions, please step back. For each problem, I will give it a difficulty rating, ranging from 1 to 5. Here is the first one. It is one of the most interesting and one of the most difficult.

 

囚犯问题

 

Difficulty: +++++

 www.ddhw.com

一个监狱长对他面前的46个犯人说，从今天晚上起所有人都要被隔离起来，也就是说没有任何办法交流信息。其中一半（２３人）当晚会被转到另一个监狱去。而且没有人知道哪２３人会被转监。从明天开始我会不定期的随机地叫你们中间的一个人到我的办工室来。办工室里有一个房间里有上下两个开关，我不知道它们现在是开还是关。当你被叫到开关室时，你可以改变其中任何一个开关的状态（由开到关，或由关到开），也可以选择不动任何开关。虽然我叫人的方法是随机的，但任何人被叫到的机会均等，也就是说，给定任何一个Ｎ，一定时间以后每个人都会被叫到Ｎ次以上。除此之外，没有任何人会动这些开关。任何时候，如果你们中间有人能肯定地说所有的人都来过这个开关室了，而且他说对了，那你们所有的人将马上获得自由。如果他说错了，也就是说还有人没有来过，所有的人将马上被处决。你们现在可以讨论一个方法，晚上以后就再也没有机会见面。

你能想出一个办法来保证所有23人都获得自由吗？

 

www.ddhw.com

 

husonghu

原题(by 新用户)：www.ddhw.com 监狱的管理者一天告诉监狱里的 23名犯人：今天你们所有的人可以在一起碰一次面 （交流，讨论）。从明天起，你们将被分开关在各自的房间里，你们将没有机会交 流，没有机会碰面。 那边有一间电器控制室，里面有2个开关 A 和 B ( 象正常的电灯开关一样，A 和 B 都有 “开”和“关”的位置以及“开”和“关”的标签）。我不告诉你们现在 A,B 开关的状态（开或关）。 开关 A 和 B 纯粹是一个开关，他们不控制任何电器。 从明天起，我每隔几天会随机的从你们23人中，选一个人去那间电器控制室，他可 以挑选一个开关，改变状态。比如说，挑选了开关 A ( 如果 A 是 开的状态，他可 以让 A 转到 关的状态；如果 A 是关的状态，它可以让 A 转到 开的状态）。然后， 他将回到自己的房间。除了这里的犯人之外，没有任何其他人能碰到电器控制室里 的 A,B 开关。所以最终你们所有的犯人，将有机会改变电器控制室里的开关。 在任何时候，如果你们当中有人向我宣布“我们所有的人都至少有一次改变了电器 控制室里的开关”，如果这句话是正确的，那我将让你们所有的人重获自由；如果 不对（那就是，只要有人未曾去过电器控制室），你们所有的人将被处死。www.ddhw.com 现在，你为犯人们设计一个好的方案，让他们尽早释放。 ________________________________________________________________ 最后一段讨论copy如下： _________________________________________________________________ 好题“23名犯人动开关”答案之质疑，及可能的改进。 文章来源: husonghu®于 2004-5-28 5:18:39 智力 IQ 竞赛 知识 competition game 各位的答案很有启发性，我在大家思维的基础上，再拣点容易的拨拉拨拉，以抛砖 引出最佳的玉来。www.ddhw.com So far，我觉得各位方案的一个缺点就是没有达到“尽早”的要求。首先，太依赖 于“头领”或“计数员”去控制室的频率和均匀性，他至少要有23次去的机会，而 且每次最多只能pass一个新人；其间会有很多“非利用期”：要么是许多以前没去 过的犯人白去了(因头领每去一次之后只能允许一个新人进入计数状态)；要么是头 领白去了(如果他去的两次之间所有其他去的人都是以前已经去过了的话)。这样阴 差阳错，真不知要多少年之后才能获自由呢！ 改进方案： 首先，注意到“从明天起，我每隔几天会随机的 ....... ”，"明天"是第一次是可 以肯定的(虽然不知每隔多少天)。那么就让明天去的那人自然为头领(不要专门选头 领 -- 这选出的头领还不知他何时能第一次去呢！)。其次(更重要的)，就是充分利 用两个开关的不同状态的组合。按下列规则进行(最后一次开会时让大家记下，生死 悠关，大家决不能出错)：www.ddhw.com 明天第1人(也是自然头领)去后把AB都放到“开-开”的位置，若原来就是如此，就 不动(他今后有的是动的机会)；接着其他第一次去的人去时，依次，每人变一个开 关的状态，比如第2人动成“开-关”，第3人动成“关-关”，第4人动成“关-开” (这期间若是头领或已去过的人去, 就不动)；当变成“关-开”之后，其他人都不能 动，大家一致等头领去动回“开-开”的位置，然后重复这样的周期。这方案中，除 头领之外，其他人只能动一次开关，之后再去就再也不能动了。详见下： 开开(头领) 开关(2) 关关(3) 关开(4) 开开(头领，记1周期) 开关(5) 关关(6) 关开(7) 开开(头领，记2周期) 开关(8) 关关(9) 关开(10) 开开(头领，记3周期) 开关(11) 关关(12) 关开(13) 开开(头领，记4周期) 开关(14) 关关(15) 关开(16) 开开(头领，记5周期) 开关(17) 关关(18) 关开(19) 开开(头领，记6周期) 开关(20) 关关(21) 关开(22) 开开(头领，记7周期) 开关(23) (头领见此之后宣告大家将获自由) www.ddhw.com 当然，这个方案里也有“非利用期”，也有阴差阳错，但会比原先的方案少许多。 也会是一个漫长的时间，但觉得至少会比原先的方案快3倍。我想如果原来要等15年 的话，这样最多5年就够了！大家可用概率论算算差别(假设两次去控制室之间“相 隔天数相同”)。 有疏漏处，请指教。若思路对的话，还可再改进吗？ _____________________________________________________________ 还可再改进一点。 文章来源: husonghu®于 2004-5-28 6:0:29 就是头领不一定要等到一个周期完结再复原到“开开”，只要他有机会去，又见到 开关已不再“开开”的位置(无论是“开关”，“关关”，或是“关开”)，都使开 关复原到“开开”，(当然他同时要记数记清楚)，以便之后有3个新人可利用机会， 这样可进一步减少新人白白等头领的“非利用期”。www.ddhw.com _____________________________________________________________ 很 有 意 思 ！ 文章来源: 野 菜 花®于 2004-5-28 12:44:27 在 “第 二 天 一 定 会 抽 人 ， 另 外 进 去 的 人 可 以 不 动 开关 ” 的 条 件 下， 这 个 方 法 的 确 加 快 了 许 多 。 另外 补 充 一 点， 头 领 不 是 每 次 都 能 把 SWITCHES 变 成 开 开 的 状 态(如 果 是 关 关 ， 因 为 只 能动 一 个 开 关，只 能 变 成 “开 关”--- 小 一 号)。 但 只 要 他 自 己 记 录 下 就 行 了 。 大 家 记 住 这个 顺 序 ： 开开(1)， 开关(2)， 关关(3)， 关开(4)， 第 一 次 进 去 的 人 把 SWITCH 变 大 一 号， 如 果不 能 再 大 了 等 下 一 次。 ____________________________________________ Good soluation. 文章来源: ob®于 2004-5-28 13:26:56www.ddhw.com 野 菜 花's amendment is great too. Time is important. The first thing need to be made sure is that all prisoners are alive. If one prisoner is dead before he has a chance to change the switch, then all other prisoners have to pray the warden to die as early as possible ______________________________________________________________ 回复：好题“23名犯人动开关”答案之质疑，及可能的改进。 文章来源: 独木桥®于 2004-5-28 13:30:50 新问题www.ddhw.com 假设有 100 个犯人，控制室里有6个开关，每次只能动一个 开关，最初开关状态已知，最快的获释策略是什么？ 如果 最初开关状态未知，最快的获释策略是什么？ ______________________________________________________________ 回复：回复：好题“23名犯人动开关”答案之质疑，及可能的改进。 文章来源: ob®于 2004-5-28 14:10:0 最初开关状态已知，最快的获释策略是什么？ use 6bits to count the number of people。 Make it simple, assume the initial state for all the switch is 000000. Since one person can only change one switch, so they can apply the following strategy (similar to six bit input Karnaugh map, but the total number is different):www.ddhw.com 000001 1 000011 2 000010 3 000110 4 000100 5 000110 6 000111 7 ........ Six bits can count up to 64 people, once the number becomes 64, then they can start from bit one again. 如果最初开关状态未知，最快的获释策略是什么？ Choose the firsy guy as the chief. He knows the initial state and he will count how many people has changed the switch. _____________________________________________________ Good idea 文章来源: 独木桥®于 2004-5-28 14:52:51 www.ddhw.com

husonghu

一道好题，不知有没有做过，建议大家仔细思考（有陷阱） 新用户®(603 字, 点 击565次) 2004-5-26 16:1:0www.ddhw.com 回复：一道好题，不知有没有做过，建议大家仔细思考（有陷阱）－22次 tcpip004® (730 字, 点击60次) 2004-5-27 21:22:40www.ddhw.com

fzy

This problem is different from the old one, and much more difficult. (I would give the old one three stars.)   First, one half of the prisoners will be transfered to another prison after their discussion about a strategy. So the leader they elected maight be gone. Second, it may not start tomorrow. And the interval is not fixed either. So any natural way to produce a leader would fail.       www.ddhw.com

husonghu

the same method can be used here.www.ddhw.com 1. In the old answer, the leader is also not pre-elected. The first prisoner going to the room will automatically be the leader. (So, looks to me the split of 46 into 23-23 in the new problem does NOT really make the issue more complicated). 2. Looks to me, in the new problem, the procedure is also started from tomorrow (从明天开始), although we don't when will be the 2nd prisoner to be called --- At least the same wording is used in both the old problem and the new problem.www.ddhw.com 3. In the old answer, the interval does not need to be fixed also (actually, this is the key of the problem -- no body knows how long the interval is. Besides, the interval can be all different between different prisoners being called. So, I feel the new problem and old problem are essentially the same, and the old answer is also applicable to the new problem. But, I do believe that there may be better answers -- And I will be happy to see them. www.ddhw.com

fzy

You really did not get it. It does not necessarily start tomorrow, the only sure thing is that it does not start before tomorrow. And the interval might be just a few minutes.www.ddhw.com www.ddhw.com

husonghu

可用基本相同的方法。只要稍做变动即可 ------- 首先，定义两个开关的4个状态依次为(比如)：开开、开关、 关关、 关开；且周而 复始。这一点很重要，必须所有的囚徒在开会时记清楚这一点(状态顺序)。 新问题与老问题的关键差别在于：老问题中，明天被叫到的人清楚地知道自己是第 1人、充当自然的leader；新问题中，谁都不清楚自己是不是第1人。但这没关系， 这里不需要leader。 具体做法如下：www.ddhw.com 1) 不管是谁，第一次被叫去时，不管他见到的两个开关原来状态如何，他都把它们 变动到下一个状态； 2) 每个人都牢牢记住自己放的状态； 3) 每个人只是第一次被叫去时变动开关状态，之后再去就再也不能动了。 现举例说明，最后谁能“肯定地说所有的人都来过这个开关室了”： 假设两个开关初始状态是“ 关关”；第1个囚徒被叫去时，他把它们动到下一个状 态“关开”，(但当时他并不知道他是第1个被叫去的人！！)；然后第2个，第3个，。。。。。 最后，当23人都去过至少一次后，变化过程如下： 关关(初始)； 关开(1)； 开开(2)；开关(3)； 关关(4)； 关开(5)； 开开(6)；开关(7)； 关关(8)； 关开(9)； 开开(10)；开关(11)； 关关(12)； 关开(13)； 开开(14)；开关(15)； 关关(16)； 关开(17)； 开开(18)；开关(19)； 关关(20)； 关开(21)； 开开(22)；开关(23)www.ddhw.com 最后，两个开关就永远停留在“开关”状态上了。再等足够长的时间，当初被第1个 叫去的囚徒就可以figure out 所有的23人都被叫遍了。(只有到此时，他才知道他 当初是第1个被叫的)。他的根据是以下三点： 1)  监狱长说过：“虽然我叫人的方法是随机的，但任何人被叫到的机会均等，也 就是说，给定任何一个Ｎ，一定时间以后每个人都会被叫到Ｎ次以上” (这一点非 常重要，是关键)； 2)  两个开关停留在一个状态上不再变了，且等了足够长的时间了(只要不怕老死在 监狱里，为保险起见，尽量多等一点时间)； 3)  所停留的这个状态(“开关”)离他当初所置的状态(“关开”)从理论上恰好相 差23个变化(当然，他必须记住他当初放的状态是什么)。 其实，稍为冒险一点，其他囚徒也可宣布取胜(凭1、2两个根据)。但第1个囚徒宣布 更保险，因为他有1、2、3三个根据。 我觉得此法能work。不知有漏同否？请大家指教。等看fzy的标准答案。 www.ddhw.com

fzy

Treat it as a math problem, because it will never happen in real life. We need a way to guarantee it. If "waiting long enough" is an option, we really do not need the switches at all. Just sit there for a couple of years and there is 99% chance all have visited the room. www.ddhw.com

新用户

最后，两个开关就永远停留在“开关”状态上了。再等足够长的时间，当初被第1个 叫去的囚徒就可以figure out 所有的23人都被叫遍了。(只有到此时，他才知道他 当初是第1个被叫的)。他的根据是以下三点： 这个有问题，足够长时间不可靠。足够长时间为多长？3年，5年？因为总有这样的可能，这3年或5年间，有一个囚犯从没有被叫到，而别的囚犯被叫了许多次。 题目中的“一定时间”应该从概率上来考虑，可以为任意数值，取决于是不是每个囚犯被叫了N次。www.ddhw.com 1)  监狱长说过：“虽然我叫人的方法是随机的，但任何人被叫到的机会均等，也 就是说，给定任何一个Ｎ，一定时间以后每个人都会被叫到Ｎ次以上” (这一点非 常重要，是关键)； 我认为，题目本身没有错，但是可能容易给人以误解。如果题目改成：监狱长会随机的叫每个人。可能就不会引起误解。 如果按照husonghu的理解，此题的意义就不大，也不难解。   我认为，此题的关键在于，如果需要leader, 如何确定这个 leader. www.ddhw.com 原贴： 文章来源: husonghu® 于 2005-2-15 10:8:30 标题：好，我懂你的意思了。但，不管是否明天开始，不管间隔长短，我觉得.....www.ddhw.com 可用基本相同的方法。只要稍做变动即可 ------- 首先，定义两个开关的4个状态依次为(比如)：开开、开关、 关关、 关开；且周而 复始。这一点很重要，必须所有的囚徒在开会时记清楚这一点(状态顺序)。 新问题与老问题的关键差别在于：老问题中，明天被叫到的人清楚地知道自己是第 1人、充当自然的leader；新问题中，谁都不清楚自己是不是第1人。但这没关系， 这里不需要leader。 具体做法如下： 1) 不管是谁，第一次被叫去时，不管他见到的两个开关原来状态如何，他都把它们 变动到下一个状态； 2) 每个人都牢牢记住自己放的状态； 3) 每个人只是第一次被叫去时变动开关状态，之后再去就再也不能动了。 现举例说明，最后谁能“肯定地说所有的人都来过这个开关室了”： 假设两个开关初始状态是“ 关关”；第1个囚徒被叫去时，他把它们动到下一个状 态“关开”，(但当时他并不知道他是第1个被叫去的人！！)；然后第2个，第3个，。。。。。 最后，当23人都去过至少一次后，变化过程如下： 关关(初始)； 关开(1)； 开开(2)；开关(3)； 关关(4)； 关开(5)； 开开(6)；开关(7)； 关关(8)； 关开(9)； 开开(10)；开关(11)； 关关(12)； 关开(13)； 开开(14)；开关(15)； 关关(16)； 关开(17)； 开开(18)；开关(19)； 关关(20)； 关开(21)； 开开(22)；开关(23)www.ddhw.com 最后，两个开关就永远停留在“开关”状态上了。再等足够长的时间，当初被第1个 叫去的囚徒就可以figure out 所有的23人都被叫遍了。(只有到此时，他才知道他 当初是第1个被叫的)。他的根据是以下三点： 1)  监狱长说过：“虽然我叫人的方法是随机的，但任何人被叫到的机会均等，也 就是说，给定任何一个Ｎ，一定时间以后每个人都会被叫到Ｎ次以上” (这一点非 常重要，是关键)； 2)  两个开关停留在一个状态上不再变了，且等了足够长的时间了(只要不怕老死在 监狱里，为保险起见，尽量多等一点时间)； 3)  所停留的这个状态(“开关”)离他当初所置的状态(“关开”)从理论上恰好相 差23个变化(当然，他必须记住他当初放的状态是什么)。 其实，稍为冒险一点，其他囚徒也可宣布取胜(凭1、2两个根据)。但第1个囚徒宣布 更保险，因为他有1、2、3三个根据。 我觉得此法能work。不知有漏同否？请大家指教。等看fzy的标准答案。   www.ddhw.com

husonghu

大概要充分利用两开关4状态，事先定义好顺序。然后根据各人所见状态，用一定的 记数策略和变动状态的策略(比如，有的情况下往正向走；有的情况下往逆向走)。 最后使两开关达到某个的状态：凭这个状态，可使至少1个囚徒能唯一地判断所有的 23人都去过开关室了。www.ddhw.com 如何能做到这些？非我所及，我不想了。www.ddhw.com (新用户说得对，此题大概没有用概率论的位置)www.ddhw.com fzy, it's a good problem. Looking forward to seeing the answer.www.ddhw.com

新用户

Hey, 别这么早的轻易放弃。楼主已经说了是难题（Difficulty: +++++），我想不会那么容易解决。www.ddhw.com   解题的快乐在于过程，能否解出是另一回事。不到万不得已，绝不放弃。 take a break, when you are back, maybe you could suddenly get some ideas.www.ddhw.com     www.ddhw.com

QL

任何时候都有A，B两组人，按下列规则操作： (1)所有人第一次被叫到时，都人为自己是A组人，并记住一个数COUNT=2，SWITCH上灯，记住其状态(开或关)，如果下灯为开，关之，并将COUNT=COUNT+1 (2)如果一个A组人第二次以上被叫到，如果他发现上灯状态变了，他就把自己归为B组，但仍记住COUNT值。如果上灯没变，并发现下灯为开，关之，并将COUNT=COUNT+1 (3)如果一个B组人被叫到，并发现下灯为关且COUNT>0，开之，并将COUNT=COUNT-1 (4)如果A组人有人发现COUNT=43，就声称所有人到过。   有漏洞吗？www.ddhw.com

QL

(2)忘了一点：SWITCH 上灯 (2)如果一个A组人第二次以上被叫到，如果他发现上灯状态变了，他就把自己归为B组，但仍记住COUNT值。如果上灯没变，SWITCH 上灯，若发现下灯为开，关之，并将COUNT=COUNT+1 www.ddhw.com

QL

该为45 (4)如果A组人有人发现COUNT=45，就声称所有人到过。 看来漏洞还是挺多，请大家指正。 www.ddhw.com

fzy

It does not seem to work. You need to prove two things:www.ddhw.com   1) One prisoner's count will eventually reach the number you decided (43 or 45) 2) When that happens, all prisoners have visited the room.www.ddhw.com   I do not see how you can prove 1). But you are in the right direction. If you can resolve 1), the approach would work. www.ddhw.com

QL

Sorry, change the rule again: rule 4, declare 'every one has visited' when COUNT=46  www.ddhw.com Let me see whether you agree with me on the following: (1)After all prisoners have been called at least once, all the counts (A people and B people's) should add up to either 46 or 47 (2)All B people's counts will be redistributed to A people's counts-- except for the 'last' B person who may has count 1 wasted. (3)All but one person will join group B eventually. (4)The last A person will eventually collect at least 46 counts. Right? www.ddhw.com

fzy

and you will see whether it works. www.ddhw.com

QL

From other posts, I find you are a much more careful problem solver than I am, I guess there is something you see but I do not.  Let me give more details about my previous proof, and let me know if you think any of the following the statments may fail.  www.ddhw.com (1)After all prisoners have been called at least once, all the counts (A people and B people's) and the lower light state (1 if it is on, 0 if it is off) should either always add up to 46 or always add up to  47.   Since every one bring 2 points toward the total count into the game, and that every point given up by a B person will either show on the lower light state or be collected by a A person, so no extra points will be generated and no points will be thrown away.www.ddhw.com The total count could be 47, because the very first person being called may find the lower light was on,  but that was not set by any other prisoners, so in this case, he counts this extra point and make the total count to be: 2*23+1 = 47   instead of 46   (2)All B people's counts will be redistributed to A people's counts-- except for the 'last' B person who may has 1 count  wasted. This is clear from the procedure.www.ddhw.com   (3)All but one person will join group B eventually. Since every A person switchs the upper light each time he visits the room , sooner or later one of them will  find that the state of the upper light has been changed since last time he visited the room, and this person will be kicked out from group A, and eventually, only  one person left in  the A group.  www.ddhw.com (4)The last A person will eventually collect 46 counts. Since the total count is either 46 or 47, and when all the other prisoners are in group B, they will redistribute all the points they collected to this last A person, hence the last A person will eventually collect 46 points, and by then, he knows that all prisoners have visited the room.   2,3,4 should all be finished in finite number of times of calls. (with probability 1) www.ddhw.com

QL

任何时候都有A，B两组人，按下列规则操作： (1)所有人第一次被叫到时，都人为自己是A组人，并记住一个数COUNT=2，SWITCH上灯，记住其状态(开或关)，如果下灯为开，关之，并将COUNT=COUNT+1 (2)如果一个A组人第二次或第二次以后被叫到，如果他发现上灯状态变了，他就把自己归为B组，但仍记住COUNT值。如果上灯没变，SWITCH 上灯，若发现下灯为开，关之，并将COUNT=COUNT+1 (3)如果一个B组人被叫到，并发现下灯为关且COUNT>0，开之，并将COUNT=COUNT-1 (4)如果A组人有人发现COUNT=46，就声称所有人到过。 www.ddhw.com

fzy

Sorry for being late. I was working on the necklace problem. You probably need to add "and remember the new state" after "如果上灯没变，SWITCH 上灯" in the second step. It caused some misunderstanding. Also the total counts might be 45, 46, or 47. With these changes, your procedure works and the proof is valid. www.ddhw.com   Congratulation! Job well done!  www.ddhw.com