百囚困境

22568

老问题了,而且还有很多升级版..

22568

前边人表述比较复杂,我简单说下标准答案吧..

先说下基础版本的题目..比lz多一个条件:已知初始时灯是灭的.
记总共n人,其中一个是A.
除A外其他所有人的策略是:第一次在出去后看到灯灭时开灯,否则不变.
A的策略是:出去时若灯开着则关灯,否则不变.当关过(n-1)次灯后确定所有人出去过.

升级版I:去掉"已知初始时灯灭"的条件.
前边好像没人考虑过,我先等等再说吧..
你们先想想吧,至少照搬刚才的方法是行不通的.

153776

因为在开完会以后给足够的时间，所以可以分配成100个序号，然后每次是几号就开关灯几下

153930

如果永远只抽一个人，那就没办法。有个办法是，在大会那天提出：我们所有人都出来放风过了

81845

一开始不确定的话，我们就需要三种状态了。把灯灭记为0，做一个什么记号记为0.5，灯亮记为1，但是后两种都算是1分，灭的记为0分。这样那个负责统计的人需要计算分数。
对于其他的人来说，每个人最多进行两次操作。如果当前分值是0分，那么他最多各进行1次1分的操作。其他时候不动。统计的人只负责归零。当统计的人统计到200分的时候，就算是所有人都来过了。
就是不知道该怎么表示这个标记。

22568

好吧,既然lz认为表述足够清楚了,那我就来直接回答lz的题吧.幸运的是,完全可以尽量避开之前提到的一些题意理解有分歧的地方.

引用

每天会有一个囚徒被随机地抽出来放风,随机就是说可能被抽到多次。

引用

如果某一天,某个囚徒能够明确表示,所有的囚徒都已经被放过风了,而且的确如此,那么所有囚徒释放;如果仍有未被放过风,那么所有的囚徒一起处死。

引用

囚徒们能找到方法么?方法要求不会有被处死的危险且早晚会被释放

正确答案是不能.
因为题目要求使囚徒们早晚能被释放的策略.
而囚徒释放需要某囚犯正确判断所有囚徒都出去过.
然而题目没有任何条件保证所有囚徒都必定会出去.

综上,只要选人方式保证至少有一人永远选不到,囚徒们就没有成功的策略.

没错,严格按照lz的表述的话就会变成这样的问题和答案.

135087

见图

153930

有答案了吗

22568

顺手搜了几个典狱长囚徒开关灯的递进版本..先贴下..
这帖出现的是前两个.
这两个的答案是挺简单.
后边版本我好像没看过答案,但我倾向于有解.

3.(1)有100个囚犯分别关在100间牢房里。牢房外有一个空荡荡的房间，房间里有一个由开关控制的灯泡。初始时，灯是关着的。看守每次随便选择一名囚犯进入房间，但保证每个囚犯都会被选中无穷多次。如果在某一时刻，有囚犯成功断定出所有人都进过这个房间了，所有囚犯都能释放。游戏开始前，所有囚犯可以聚在一起商量对策，但在此之后它们唯一可用来交流的工具就只有那个灯泡。他们应该设计一个怎样的协议呢？
(2)大家都知道房间里的灯泡一开始是不亮的。如果灯泡的初始状态并不确定，问题有解吗？
(3)在以上协议中，只有一个人能知道所有人都来过房间。是否存在一个协议，使得最终可以产生两个人，他们都知道所有人都进过房间？如果存在这样的协议，给出一个来；如果不存在，证明之。为了方便思考，你可以暂时假设初始时房间的灯泡不亮。
(4)还是100个囚犯，还是一个空房间，还是要求所有囚犯事先构造一个协议，能保证有人可以断定出所有人都来过房间。不过，这次不同的是，房间里有两个灯泡，分别由两个开关来控制（不妨假设初始时他们都是不亮的）。大家估计要说了，一个灯泡都能解决的事儿，用两个灯泡还不容易？嘿嘿，这次有一个附加的要求：所有人都必须遵循同一套策略。

106005

假定有N个人还未放过风。假定所有人都不确定此时灯的开闭。规定：
第一天被抽到放风的如果是已经放过的，保证离开时关灯。如果第一天的防风人是以前没有放过的，保证离开时灯开启。
所有未放过风的人从第一天起到被释放只有开一次灯的权利，无关灯的权利。也就是只有看到灯是灭的时候才能开灯，而且开过一次灯以后就不能再开灯。而大会之前已经放过风的人，从第一天起到被释放（除了第一天的那个人）无开关灯权利。
从已经放过风的人中指定一人A，A负责关灯，只要看到灯是开的就必须关灯。只要A的关灯次数达到N，就可以报告。