| ||
| ||
| ||
| ||
| ||
|
监狱的管理者一天告诉监狱里的 23名犯人：今天你们所有的人可以在一起碰一次面(交流，讨论)。从明天起，你们将被分开关在各自的房间里，你们将没有机会交流，没有机会碰面。
那边有一间电器控制室，里面有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;">
从明天起，我每隔几天会随机的从你们23人中，选一个人去那间电器控制室，他可以挑选一个开关，改变状态。比如说，挑选了开关 A ( 如果 A 是 开的状态，他可以让 A 转到 关的状态；如果 A 是关的状态，它可以让 A 转到 开的状态）。然后，他将回到自己的房间。除了这里的犯人之外，没有任何其他人能碰到电器控制室里的 A,B 开关。所以最终你们所有的犯人，将有机会改变电器控制室里的开关。
在任何时候，如果你们当中有人向我宣布“我们所有的人都至少有一次改变了电器控制室里的开关”，如果这句话是正确的，那我将让你们所有的人重获自由；如果不对（那就是，只要有人未曾去过电器控制室），你们所有的人将被处死。
现在，请你为犯人们设计一个好的方案，让他们尽早释放。
|
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). |
"more time needed for them to get free" is a big issue here. We want to get free in shortest time possible  |
|
4，如果开关在01或10时就要耽误一下，因为他动一下只能变成00，然后出去等到他下一次进来，来改变为01开始 第一个人如果进来看到是01，就扳到11，这样在他下次回来之前还可以多算两个人 问题是，怎样才知道自己是不是第一个人呢？？？？？ |
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. 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) . |
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'. |
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, 不管是我们说的第一种策略, 还是你的第二种策略. 我叫大家想改进方案, 关键就是要尽量减少"非利用期". 如果我没理解错的话, 你的第二种方案里, K个junior counters是要一个接着一个工作的(要等第一个junior counter做完, 第二个junior counter才能工作. 不能同时工作), 而且每个junior counter的一个记数周期只能pass一个犯人. "非利用期"太多了. 而且在一个counter 和 non-counters 之间设置K个junior counters, "非利用期"更是增加了. 我觉得好象还是第一种策略好些, 不管N大还是小. 本贴由[husonghu]最后编辑于：2008-5-10 3:54:18 |
怎样知道自己是否第一人, HF已回答了你的问题. 先说明一下, 上面的匿名网友是以00为始点, 阿虎是以01为始点. 当然两者都可(只要如此约定好). 你是接阿虎之下, 故我们现在谈的是以01为 始点. (根据方案, 只有领导者, 即第一人才能动成01, 故可把它称之为"领头人的点") 对你改进法的评论: 若第一人进去时已见01, 最好, 就不要动(他最希望动成的结果就是01嘛). 阿虎说要耽搁一下, 其实并无耽搁. 若第一人进去时见到的是10, 是动的好呢? 还是不动的好呢? 若要动, 动成怎样好呢? (注意: 他只动一个开关, 是不能动成01的). |
如果我没理解错的话, 你的第二种方案里, K个junior counters是要一个接着一个工作的(要等第一个junior counter做完, 第二个junior counter才能工作. 不能同时工作), 而且每个junior counter的一个记数周期只能pass一个犯人. "非利用期"太多了. 而且在一个counter 和 non-counters 之间设置K个junior counters, "非利用期"更是增加了. 我觉得好象还是第一种策略好些, 不管N大还是小. 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. |
You're the pro. |
如果开关在01 As hosonghu mentioned, in the case of 01, you should leave it unchanged. |
非注册网友和阿虎答的方法符合本坛老网友以前讨论出的方法, 只需一点小改进即可. 我们把这叫做方法一.
另外, HF讨论了另一个有趣的方法. 我们把它叫做方法二. 至于哪种方法在什么情况下比另一种更好(即哪种更快), 分界线在哪, 我觉得很说不准. 蛮复杂的, 也蛮有趣的. 有兴趣的朋友可继续讨论.
现在我把以前的讨论结果(方法一)摆一下:
基本方案 -----
明天第1人(也是自然头领)去后把两开关放到一个初始位置,比如00，若原来就是如此，就不动(他今后有的是动的机会)；接着其他第一次去的人去时，依次，比如01à11à10, 每人向前变一个开关的状态. 这期间若是已动过开关的人去,就不动. 当变成10之后，其他人都不能动，大家一致等头领去动回00的位置，然后重复这样的周期。始点00始终是头领的点,其他人绝对不能把开关动成00. 这方案中，除头领之外，其他人只能动一次开关，之后再去就再也不能动了。如下:
00(by头领)— 01(by其他人1)— 11(by其他人2)-- 10(by其他人3)— 00(by头领.一个周期完.头领记数pass三人)
如此重复直到头领记数除自己外的22人全pass为止.
改进方案 -----
头领第一次进去,不一定都能把开关放到00. 即便如此,也能有所作为. 总之,第一次的动法是: 若看到00,最好,就不动; 若看到10或01,就动成00; 关键是若看到11怎办? 最好是倒退到01(不是前进到10,也不是留在11不动).
同理,头领以后每次进去都可有所作为,不一定要等到一个周期完结(即,不一定要等看到10)再复原到00，只要他进去时见到开关已不在00的位置, 都可动一下开关. 动法如上述一样: 若看到10,当然是前进到00; 若看到01,变回到(即,倒退到)00; 若看到11,倒退到01.
总之, 头领每次的有所作为, 比之于他干等01的到来, 会使过程加快一点(在头领两次进去之间尽量多pass人,只要他记数记清楚就行). (这里是定00为始点. 阿虎定01为始点也同理) 本贴由[husonghu]最后编辑于：2008-5-16 1:1:33 |
| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |