恭喜一位非注册网友, 顶上征答的<犯人们如何能得到尽早释放?>基本答对了. 但还有改进余地...

husonghu

原贴链接在此:

http://www.ddhw.com/listo.aspx?level_string=0&topic_id=9&msg_id=7964

 

为方便继续讨论, 我把原题重贴在此:

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

那边有一间电器控制室，里面有2个开关 A 和 B ( 象正常的电灯开关一样，A 和 B 都有 “开”和“关”的位置以及“开”和“关”的标签）。我不告诉你们现在A,B 开关的状态（开或关）。 开关 A 和 B 纯粹是一个开关，他们不控制任何电器。0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">www.ddhw.com

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

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

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

(补充说明: 上述的意思是, 每个人进去可以改变一个开关的状态, 也可以不动. 但不能一下子改动两个开关)0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">

www.ddhw.com

 

husonghu

思路是可行的，可以进一步提高   上贴时间: 2008-5-4 1:12:52 (北京时间: 2008-5-4 13:12:52)   文章来源: 随机就没法保证时间了   [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] 第一个人要担负起计数的责任。他把两个开关都设为关，计为00；第二个首次进入拨动开关的人把开关B拨到开，计为01；第三个把开关拨到10；第四个把开关拨到11。这个计数周期结束，之后进入的人不能再动开关，直到第一个人再次进入看到11并把开关复位到00。这样每个周期可以确定有三个不同的人动过开关。  www.ddhw.com 这是一般性的方法。具体到本题的23个人，如果这样进行，除去计数人还有22个人，需要8个周期。可以再优化一下：第一个人首次进入时设为11，第二天到第五天如果有另一个人进入看到11帮他复位为00，开始第一个周期。如果还是他反复被选中，前四天保持11，到第五天必须复位为00。这样，有1-1/23^5的概率在7个周期内结束。   0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;"> www.ddhw.com 很好, 基本上对了. 这样快许多了, 有活着出来的希望了. 但有的地方要修正....   上贴时间: 2008-5-6 3:3:12 (北京时间: 2008-5-6 15:3:12)   文章来源: husonghu®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 3451    现金: 347元 （更多个人信息） [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] 因为每次只能动一个开关, 所以一个人是不能将开关从01变为10, 或从11变为00的. 故你的第三与第四个状态(即10与11)要调换一下, 换成00, 01, 11, 10, 然后再能回到00.   www.ddhw.com 还有, 你的第二段的优化方案(第一人设10状态, 指望第二人帮他设00), 不一定可行: 因为除了第一个人第一次进去的时间是确定的之外(即监狱长说的"明天"), 之后所有人次进去的时间都是不确定的 --- 也许第二次的情况是: 过了许多天之后, 又是第一个人进去, 那他就搞不清见到的10是他初始设的, 还是一周期后的10; 另外, 也由于进去时间的无规性, 真正的第二人也不清楚他自己是否第二人, 他看到10也不敢改成00.    但是, 确实可以将你的方案再改进一点, 可能又可再提早一两年出狱哦.

212808

  回复：恭喜一位非注册网友, 顶上征答的<犯人们如何能得到尽早释放?>基本答对了. 但还有改进余地..

HF:

I think 1 switch is enough, and you don't have to assume that 'tomorrow' there must be a prisoner called. (although more time needed for them to get free). www.ddhw.com

husonghu

"more time needed for them to get free" is a big issue here.  We want to get free in shortest time possible www.ddhw.com

husonghu

这回该对了吧，楼主?   上贴时间: 2008-5-8 3:2:47 (北京时间: 2008-5-8 15:2:47)   文章来源: 阿虎®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 35    现金: 85元 （更多个人信息）   用户博客地址: http://ahu.ddhw.cn （222 篇） [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加入博客 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ] 1，首先制定一个顺序例如；从00开始01，11，10，00.要严格按此顺序动开关。 2，另外00这个位子时除了第一个人以外别人不得开始，以便第一人准确掌握。 3，第一次开关位子在00或11时就好办了，第一人变动一个开关就可以从01开始直到00由他来开始第二轮 4，如果开关在01或10时就要耽误一下，因为他动一下只能变成00，然后出去等到他下一次进来，来改变为01开始 5，每一个新来的进来看见开关位子除了在00位子以外严格按照01-11-10-00这个顺序动一次。 6.  重复进来的人严禁动开关，这样一轮可以确定3个人。 www.ddhw.com

husonghu

很不错. 你的第4点可改得更好一点. 想想还有其它的改进吗? 你若愿意, 我们最好移到新贴去继续讨论   上贴时间: 2008-5-9 3:45:11 (北京时间: 2008-5-9 15:45:11)   文章来源: husonghu®   （给该用户: 发私人信件   赠送礼物）   用户信息: 积分: 3461    现金: 367元 （更多个人信息） [ 脑筋一动 首页 ] [ 回复此贴 ] [ 回 顶顶华闻 主页 ] [ 编辑修改 ] [ 删除此贴 ]   很不错. 你的第4点可改得更好一点. 想想还有其它的改进吗? 你若愿意, 我们最好移到新贴去继续讨论

动脑筋

4，如果开关在01或10时就要耽误一下，因为他动一下只能变成00，然后出去等到他下一次进来，来改变为01开始 第一个人如果进来看到是01，就扳到11，这样在他下次回来之前还可以多算两个人 第一个人如果进来看到是10，就不要动，这样在他下次回来之前还可以多算一个人 问题是，怎样才知道自己是不是第一个人呢？？？？？ www.ddhw.com

HF:

For N = 23, this might be the optimal method with shortest expected time. For N large, say N = 10000 (long live the prisoners. ), there are more efficient methods.    The current method need approximately N/3 rounds (by a 'round', I mean the number of times the "First Person" being called), so the total number of days needed is about N^2/3 -- of cause, these are just rough estimations. The real expectation need some careful calculation, which does not seems to be very trivial.www.ddhw.com  www.ddhw.com Now, for large N, consider another approach: before the games starts, the prisoners pick a 'senior counter' and K 'junior counters'. The Junior counters control switch A, only they can set A from 1 to 0 (multiple times), other prisioners (the non-counters) can only set A from 0 to 1 once. Once a junior counter i collects M_i counts, he will stop collecting more counts and stop changing the state of switch A. He then `report' this to the 'senior counter' through switch B by using similar method, where only the senior counter can set B from 1 to 0...   Once the senior counter collects K counts, he can annouce the end of the game. K should be chosen to a number close to sqrt(N), so is every M_i. The M_i's should add up to N-K-1;  The expected number of days needed approximately  2 * N^2/sqrt(N) . www.ddhw.com

HF:

The assumption was that: the games starts from 'tomorrow' -- there will be a person called tomorrow, and whoever that guy is, he is the 'first person'. www.ddhw.com

husonghu

Some comments:   由于每个人被叫到开关房间去的随机性和无规性, 不管用哪种策略, 过程中间都会碰到许多"非利用期" --- i.e., 某些新人(即还从来没动过开关的人)在某些次进去时, 既不能动开关也不能传递信息, 进去的机会白白浪费了. 象第一种策略, N=23时, 共要大约7个"周期"完成. 前1, 2个周期会快一些: 假设所有的人进去的机会均等, 大约进23人次能完成一个周期. 但越到后面的周期, "非利用期"会越来越多(阴差阳错, 要么是许多以前还没动过开关的non-counters 白进去了, 要么是counter白进去了), 结果是, 完成一个周期需要的时间会越来越长: 可能会远远大于23人次. 最后1,2个周期, 可能要几百天完成一个周期也说不定.   Therefore, I guess "the total number of days needed", may be much longer than your estimate, 不管是我们说的第一种策略, 还是你的第二种策略. 我叫大家想改进方案, 关键就是要尽量减少"非利用期".  www.ddhw.com 如果我没理解错的话, 你的第二种方案里,  K个junior counters是要一个接着一个工作的(要等第一个junior counter做完, 第二个junior counter才能工作. 不能同时工作), 而且每个junior counter的一个记数周期只能pass一个犯人.  "非利用期"太多了. 而且在一个counter 和 non-counters 之间设置K个junior counters, "非利用期"更是增加了. 我觉得好象还是第一种策略好些, 不管N大还是小.    www.ddhw.com     本贴由[husonghu]最后编辑于：2008-5-10 3:54:18

husonghu

怎样知道自己是否第一人, HF已回答了你的问题.   先说明一下, 上面的匿名网友是以00为始点, 阿虎是以01为始点. 当然两者都可(只要如此约定好). 你是接阿虎之下, 故我们现在谈的是以01为 始点. (根据方案, 只有领导者, 即第一人才能动成01, 故可把它称之为"领头人的点")    对你改进法的评论: 若第一人进去时已见01,  最好, 就不要动(他最希望动成的结果就是01嘛). 阿虎说要耽搁一下, 其实并无耽搁. 若第一人进去时见到的是10, 是动的好呢? 还是不动的好呢? 若要动, 动成怎样好呢? (注意: 他只动一个开关, 是不能动成01的). www.ddhw.com

HF:

如果我没理解错的话, 你的第二种方案里,  K个junior counters是要一个接着一个工作的(要等第一个junior counter做完, 第二个junior counter才能工作. 不能同时工作), 而且每个junior counter的一个记数周期只能pass一个犯人.  "非利用期"太多了. 而且在一个counter 和 non-counters 之间设置K个junior counters, "非利用期"更是增加了. 我觉得好象还是第一种策略好些, 不管N大还是小.    www.ddhw.com No, the junior counters work independently. Every time a junior i sees a 1 on A switch, he adds one to his own counts and changes A switch to 0 -- until his total counts reached the pre-determined value M_i.  The point is to avoid the waste in the early stage as proposed in the first method, where most prisioners have to wait for the "first person" to enter the room to reset the switches whenever a count of 3 is researched. In this second method, any one of the K junior counters can reset the A switch, so the average period a prisoner has to wait to `contribute' his count will be reduced a lot.  www.ddhw.com   www.ddhw.com

husonghu

  Oh, I see. Excellent

动脑筋

You're the pro.www.ddhw.com

HF:

如果开关在01   As hosonghu mentioned, in the case of 01, you should leave it unchanged. www.ddhw.com

husonghu

www.ddhw.com 非注册网友和阿虎答的方法符合本坛老网友以前讨论出的方法, 只需一点小改进即可.  我们把这叫做方法一.  www.ddhw.com 另外, HF讨论了另一个有趣的方法. 我们把它叫做方法二.  至于哪种方法在什么情况下比另一种更好(即哪种更快), 分界线在哪, 我觉得很说不准. 蛮复杂的, 也蛮有趣的. 有兴趣的朋友可继续讨论.  www.ddhw.com 现在我把以前的讨论结果(方法一)摆一下:  www.ddhw.com 基本方案 -----  www.ddhw.com 明天第1人(也是自然头领)去后把两开关放到一个初始位置,比如00，若原来就是如此，就不动(他今后有的是动的机会)；接着其他第一次去的人去时，依次，比如01à11à10, 每人向前变一个开关的状态. 这期间若是已动过开关的人去,就不动. 当变成10之后，其他人都不能动，大家一致等头领去动回00的位置，然后重复这样的周期。始点00始终是头领的点,其他人绝对不能把开关动成00. 这方案中，除头领之外，其他人只能动一次开关，之后再去就再也不能动了。如下:  www.ddhw.com 00(by头领)— 01(by其他人1)— 11(by其他人2)-- 10(by其他人3)— 00(by头领.一个周期完.头领记数pass三人)  www.ddhw.com 如此重复直到头领记数除自己外的22人全pass为止. www.ddhw.com   改进方案 ----- www.ddhw.com  www.ddhw.com 头领第一次进去,不一定都能把开关放到00. 即便如此,也能有所作为. 总之,第一次的动法是: 若看到00,最好,就不动; 若看到10或01,就动成00; 关键是若看到11怎办? 最好是倒退到01(不是前进到10,也不是留在11不动).www.ddhw.com  www.ddhw.com 同理,头领以后每次进去都可有所作为,不一定要等到一个周期完结(即,不一定要等看到10)再复原到00，只要他进去时见到开关已不在00的位置, 都可动一下开关. 动法如上述一样: 若看到10,当然是前进到00; 若看到01,变回到(即,倒退到)00; 若看到11,倒退到01.  www.ddhw.com 总之, 头领每次的有所作为, 比之于他干等01的到来, 会使过程加快一点(在头领两次进去之间尽量多pass人,只要他记数记清楚就行).  www.ddhw.com(这里是定00为始点. 阿虎定01为始点也同理)  www.ddhw.com     本贴由[husonghu]最后编辑于：2008-5-16 1:1:33