12个人被关进6个屋子

l4m2

每次任意选一个人，让他看、操控一个灯泡。可以事先决定一种方法，之后留6人进去，6人隔开。要求在人交出齐之后报告。
1.给出一种成功概率1的方法（不能直接叫人统计，万一统计者不是一个人呢）
2.若n次后依然没有报告，则失败。此时成功概率最高为？（每个人不知道总体上是第几次）

BeerRabbit

问题似乎不完整（抑或是我的理解力有待提高……）

l4m2

蓝小墨云 发表于 2014-7-13 16:23
123456 依次给屋子编号、然后第一个操作闪1下。第二个闪2下。依次类推............出来就问看到闪几次灯就 ...

原题

有100个无期囚徒，被关在100个独立的小房间，互相无法通信。
每天会有一个囚徒被随机地抽出来放风，随机就是说可能被抽到多次。
放风的地方有一盏灯，囚徒可以打开或者关上，除囚徒外，没有别人会去动这个灯。每个人除非出来防风，是看不到这个灯的。
一天，全体囚徒大会，国王大赦，给大家一个机会：如果某一天，某个囚徒能够明确表示，所有的囚徒都已经被放过风了，而且的确如此，那么所有囚徒释放；如果仍有囚徒未被放过风，那么所有的囚徒一起处死！
囚徒大会后给大家20分钟时间讨论，囚徒们能找到方法么？

kastin

l4m2 发表于 2014-7-15 11:51
原题

有100个无期囚徒，被关在100个独立的小房间，互相无法通信。

有点类似帽子问题，原理是奇偶校验法。不过这个问题更加开放，难度更大。

设想一种方案：假设灯的初始状态为A，每个囚徒第一次放风的时候需要按一次开关（改变灯的状态），若已经被选中过一次，则不做任何改变；这样就能知道，如果每个囚犯至少被抽到一次，那么灯的状态仍然是A（因为囚犯数目是偶数个）。但是灯的状态是A并不能保证每个囚犯至少被抽到一次，因为是随机的，所以在不是足够长的时间内，有可能偶数个囚犯被放风了，而这偶数个囚犯又随机轮流再次被抽中，这样仍然能保证灯的状态是A.

由于题目说是“某一天”，那么这个某一天到底是小于100天，还是远远大于100天呢？如果是前者，那么显然不可能都被放风到；若是后者，那么只要灯的状态是A，那么很有可能都被放风过。所以问题的关键在于怎么破除随机的影响。

咻咻

如果只是要求正确率100%，而不关心效率的话，方法很多吧，比如下面的：

100个人中，选一个作为队长
1）第一天，不管是谁，如果灯开着，就把灯灭掉
2）除了队长之外，每个人只操作灯一次，就是当他第一次遇到灭着的灯的时候，打开灯。第二次或者再以后遇到则不操作。
3）队长每次看到开着的灯，则灭掉，并自己计算灭灯的总次数。
当队长第99次灭灯之后，他可以确定，所有人都放风过了