珍珠湾ART

标题: 每周一题 by 万精油: 囚犯问题 [打印本页]

作者: fzy 时间: 2005-2-14 19:10
标题: 每周一题 by 万精油: 囚犯问题

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: +++++

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

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

作者: husonghu 时间: 2005-2-14 22:03
标题: 新用户出过此题(类似)，在本坛有过extensive讨论. 详见内.

原题(by 新用户)：

监狱的管理者一天告诉监狱里的 23名犯人：今天你们所有的人可以在一起碰一次面
（交流，讨论）。从明天起，你们将被分开关在各自的房间里，你们将没有机会交
流，没有机会碰面。

那边有一间电器控制室，里面有2个开关 A 和 B ( 象正常的电灯开关一样，A 和
B 都有 “开”和“关”的位置以及“开”和“关”的标签）。我不告诉你们现在
A,B 开关的状态（开或关）。开关 A 和 B 纯粹是一个开关，他们不控制任何电器。

从明天起，我每隔几天会随机的从你们23人中，选一个人去那间电器控制室，他可
以挑选一个开关，改变状态。比如说，挑选了开关 A ( 如果 A 是开的状态，他可
以让 A 转到关的状态；如果 A 是关的状态，它可以让 A 转到开的状态）。然后，
他将回到自己的房间。除了这里的犯人之外，没有任何其他人能碰到电器控制室里
的 A,B 开关。所以最终你们所有的犯人，将有机会改变电器控制室里的开关。

在任何时候，如果你们当中有人向我宣布“我们所有的人都至少有一次改变了电器
控制室里的开关”，如果这句话是正确的，那我将让你们所有的人重获自由；如果
不对（那就是，只要有人未曾去过电器控制室），你们所有的人将被处死。

现在，你为犯人们设计一个好的方案，让他们尽早释放。
________________________________________________________________

最后一段讨论copy如下：
_________________________________________________________________
好题“23名犯人动开关”答案之质疑，及可能的改进。
文章来源: husonghu®于 2004-5-28 5:18:39 智力 IQ 竞赛知识 competition game

各位的答案很有启发性，我在大家思维的基础上，再拣点容易的拨拉拨拉，以抛砖
引出最佳的玉来。

So far，我觉得各位方案的一个缺点就是没有达到“尽早”的要求。首先，太依赖
于“头领”或“计数员”去控制室的频率和均匀性，他至少要有23次去的机会，而
且每次最多只能pass一个新人；其间会有很多“非利用期”：要么是许多以前没去
过的犯人白去了(因头领每去一次之后只能允许一个新人进入计数状态)；要么是头
领白去了(如果他去的两次之间所有其他去的人都是以前已经去过了的话)。这样阴
差阳错，真不知要多少年之后才能获自由呢！

改进方案：

首先，注意到“从明天起，我每隔几天会随机的 ....... ”，"明天"是第一次是可
以肯定的(虽然不知每隔多少天)。那么就让明天去的那人自然为头领(不要专门选头
领 -- 这选出的头领还不知他何时能第一次去呢！)。其次(更重要的)，就是充分利
用两个开关的不同状态的组合。按下列规则进行(最后一次开会时让大家记下，生死
悠关，大家决不能出错)：

明天第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) (头领见此之后宣告大家将获自由)

当然，这个方案里也有“非利用期”，也有阴差阳错，但会比原先的方案少许多。
也会是一个漫长的时间，但觉得至少会比原先的方案快3倍。我想如果原来要等15年
的话，这样最多5年就够了！大家可用概率论算算差别(假设两次去控制室之间“相
隔天数相同”)。

有疏漏处，请指教。若思路对的话，还可再改进吗？

_____________________________________________________________
还可再改进一点。
文章来源: husonghu®于 2004-5-28 6:0:29

就是头领不一定要等到一个周期完结再复原到“开开”，只要他有机会去，又见到
开关已不再“开开”的位置(无论是“开关”，“关关”，或是“关开”)，都使开
关复原到“开开”，(当然他同时要记数记清楚)，以便之后有3个新人可利用机会，
这样可进一步减少新人白白等头领的“非利用期”。

_____________________________________________________________
很有意思！
文章来源: 野菜花®于 2004-5-28 12:44:27

在 “第二天一定会抽人，另外进去的人可以不动开关 ” 的
条件下，这个方法的确加快了许多。

另外补充一点，头领不是每次都能把 SWITCHES 变成开开的状
态(如果是关关，因为只能动一个开关，只能变成 “开关”---
小一号)。但只要他自己记录下就行了。大家记住这个顺序
：开开(1)，开关(2)，关关(3)，关开(4)，第一次进去的人把 SWITCH
变大一号，如果不能再大了等下一次。

____________________________________________
Good soluation.
文章来源: ob®于 2004-5-28 13:26:56

野菜花'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

新问题

假设有 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):

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

作者: husonghu 时间: 2005-2-14 22:09
标题: 之前的两段讨论可索查以下两标题：

一道好题，不知有没有做过，建议大家仔细思考（有陷阱）新用户®(603 字, 点
击565次) 2004-5-26 16:1:0

回复：一道好题，不知有没有做过，建议大家仔细思考（有陷阱）－22次 tcpip004®
(730 字, 点击60次) 2004-5-27 21:22:40

作者: fzy 时间: 2005-2-14 22:15
标题: It is different

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.

作者: husonghu 时间: 2005-2-15 01:42
标题: I feel there's no essential difference; & the same

the same method can be used here.

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.

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.

作者: fzy 时间: 2005-2-15 03:57
标题: You did not get it.

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.

作者: husonghu 时间: 2005-2-15 18:08
标题: 好，我懂你的意思了。但，不管是否明天开始，不管间隔长短，我觉得.....

可用基本相同的方法。只要稍做变动即可 -------

首先，定义两个开关的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的标准答案。

作者: fzy 时间: 2005-2-15 19:42
标题: That is not the point

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.

作者: 新用户 时间: 2005-2-15 21:46
标题: 回复：好，我懂你的意思了。但，不管是否明天开始，不管间隔长短，我觉得.....

这个有问题，足够长时间不可靠。足够长时间为多长？3年，5年？因为总有这样的可能，这3年或5年间，有一个囚犯从没有被叫到，而别的囚犯被叫了许多次。

题目中的“一定时间”应该从概率上来考虑，可以为任意数值，取决于是不是每个囚犯被叫了N次。www.ddhw.com

我认为，题目本身没有错，但是可能容易给人以误解。如果题目改成：监狱长会随机的叫每个人。可能就不会引起误解。

如果按照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 时间: 2005-2-15 23:01
标题: 看来此题有严密解。我放弃了。瞎猜一下思路(不是答题)。

大概要充分利用两开关4状态，事先定义好顺序。然后根据各人所见状态，用一定的
记数策略和变动状态的策略(比如，有的情况下往正向走；有的情况下往逆向走)。
最后使两开关达到某个的状态：凭这个状态，可使至少1个囚徒能唯一地判断所有的
23人都去过开关室了。

如何能做到这些？非我所及，我不想了。

(新用户说得对，此题大概没有用概率论的位置)

fzy, it's a good problem. Looking forward to seeing the answer.

作者: 新用户 时间: 2005-2-15 23:53
标题: 回复：看来此题有严密解。我放弃了。瞎猜一下思路(不是答题)。

Hey, 别这么早的轻易放弃。楼主已经说了是难题（Difficulty: +++++），我想不会那么容易解决。

解题的快乐在于过程，能否解出是另一回事。不到万不得已，绝不放弃。

take a break, when you are back, maybe you could suddenly get some ideas.

作者: QL 时间: 2005-2-16 17:42
标题: 回复：每周一题 by 万精油: 囚犯问题

任何时候都有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 时间: 2005-2-16 17:45
标题: 回复：回复：每周一题 by 万精油: 囚犯问题

(2)忘了一点：SWITCH 上灯

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

作者: QL 时间: 2005-2-16 17:55
标题: 回复：回复：每周一题 by 万精油: 囚犯问题

该为45
(4)如果A组人有人发现COUNT=45，就声称所有人到过。

看来漏洞还是挺多，请大家指正。

作者: fzy 时间: 2005-2-16 19:03
标题: 回复：回复：每周一题 by 万精油: 囚犯问题

It does not seem to work. You need to prove two things:

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.

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.

作者: QL 时间: 2005-2-16 19:43
标题: 回复：回复：回复：每周一题 by 万精油: 囚犯问题

Sorry, change the rule again: rule 4, declare 'every one has visited' when COUNT=46

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?

作者: fzy 时间: 2005-2-16 22:09
标题: You may try to prove it

and you will see whether it works.

作者: QL 时间: 2005-2-16 23:41
标题: 回复：You may try to prove it

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.

(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.

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.

(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.

(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)

作者: QL 时间: 2005-2-16 23:47
标题: 修改

任何时候都有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，就声称所有人到过。

作者: fzy 时间: 2005-2-17 20:56
标题: 回复：修改

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.

Congratulation! Job well done!

欢迎光临珍珠湾ART (http://zzwav.com/)