100 prisoners problem(zt)

zyang131

There are 100 prisoners in solitary cells. There's a central living room with one light bulb; this bulb is initially off. No prisoner can see the light bulb from his or her own cell. Everyday, the warden picks a prisoner equally at random, and that prisoner visits the living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting that all 100 prisoners have been to the living room by now. If this assertion is false, all 100 prisoners are shot. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world could always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity. The prisoners are allowed to get together one night in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion?

www.ddhw.com

 

husonghu

答在那了，也不知是否一定对. www.ddhw.com

新用户

一道类似的题目很久以前这里讨论过。   zyang131®的题有一点点不同：如果犯人知道那盏灯炮的起始状态（OFF），那么该题就容易些；如果犯人不知道那盏灯炮的起始状态，那么该题就跟以前讨论的那题难度一样了。   因为这里有许多新来的朋友，为了方便起见，我把那道中文版本的题目转过来，没有做过的朋友们可以讨论。这道题目非常好。   ————————————————————————————   监狱的管理者一天告诉监狱里的 23名犯人： 今天你们所有的人可以在一起碰一次面（交流，讨论）。从明天起，你们将被分开关在各自的房间里，你们将没有机会交流，没有机会碰面。www.ddhw.com 那边有一间电器控制室，里面有2个开关 A 和 B ( 象正常的电灯开关一样，A 和 B 都有 “开”和“关”的位置以及“开”和“关”的标签）。我不告诉你们现在 A,B 开关的状态（开或关）。 开关 A 和 B 纯粹是一个开关，他们不控制任何电器。 从明天起，我每隔一段时间会随机的从你们23人中，选一个人去那间电器控制室，他可以挑选一个开关，改变状态。比如说，挑选了开关 A ( 如果 A 是 开的状态，他可以让 A 转到 关的状态；如果 A 是关的状态，它可以让 A 转到 开的状态） 然后，他将回到自己的房间。除了这里的犯人之外，没有任何其他人能碰到电器控制室里的 A,B 开关。 所以最终你们所有的犯人，将有机会改变电器控制室里的开关。 在任何时候，如果你们当中有人向我宣布“我们所有的人都至少有一次改变了电器控制室里的开关” 如果，这句话是正确的，那我将让你们所有的人重获自由； 如果不对（那就是，只要有人未曾去过电器控制室），你们所有的人将被处死。 现在，你为犯人们设计一个好的方案，让他们尽早释放。 www.ddhw.com