囚犯点灯

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

给每个犯人编号，1-100，然后让大家用二进位模式显示自己的号。例如，25 = 11001 = 开开关关开。等到每个号都进去过了，大家也就都知道了。

好像只有在外面放风的囚犯可以看到灯啊，像公主提议的这样开开关关的不是消遣自己么......

我有个方法，不过运气不好应该需要几百年时间吧，哈哈哈:titter:

假定初始灯是关的。

指定一名囚犯A，负责关灯：

如果他放风时，if 看见灯是亮的，then 关掉;并且计数加1；

其他人出来放风，if 以前没有开过灯&灯是关闭的  then 开灯 else 不做任何动作。

当A计数到99时，肯定所有人都放过风。

[[i] 本帖最后由 asky 于 2007-6-28 05:33 编辑 [/i]]

那不如每人都负责关灯。
也就是每个人第一次见到灯的时候保持灯打开，以后每次都保持灯熄灭。
那么当某个人看到99－100次灯开着的时候，就全放过风了。（之所以有100是因为有可能他的第一次放风和第二次放风挨着，如果这种情况不出现就是99次）
不过我没算出来所需要时间的数学期望。最少应该是198天，最大就无穷大了。

你那个方法有漏洞，有可能这个人看到的某次开着的灯是被开了又关了又开过又关了.....又开了的，中间夹杂的次数不一定，这样就无法准确计数到99。

[quote]原帖由 [i]天宫公主[/i] 于 2007-6-28 01:54 发表
给每个犯人编号，1-100，然后让大家用二进位模式显示自己的号。例如，25 = 11001 = 开开关关开。等到每个号都进去过了，大家也就都知道了。 [/quote]
注意:囚犯间不能联系
       囚房内看不见灯!


别人怎么能知道操作灯的人是几号呢?


所以对此答案表示怀疑!

asky的方法我觉得可行，但效率太低了。sunnybill的方法不对吧，从1号到100号这样放，没人能够看到100次亮灯啊，前100天每人看到1次，以后大家都看不到了

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

我觉得这句话有问题，是不是说有的人很可能一直没有机会被抽中:blink:

再次重申:用计算机语言思考问题.这是关键!!!!!!!

我们所求的是最优解,当然是要考虑概率的,但是某些极端的情况可不用考虑的.
比如有的人出去了10次以上,而有的人1次也没出去过.
如果总是这样想,那么这题就没有意义了.

四楼的答案难道不对？

四楼自己也说了,运气不好的话要几百年时间啊!

这肯定不是最优解!

如果运气不好的话什么解都白搭。
想想真正运气不好了，最后一个人就是不叫了，怎么都在前99个中叫，你的解再好他们都是永远出不来。

[quote]原帖由 [i]sunnybill[/i] 于 2007-7-1 17:34 发表
如果运气不好的话什么解都白搭。
想想真正运气不好了，最后一个人就是不叫了，怎么都在前99个中叫，你的解再好他们都是永远出不来。 [/quote]
  
再次重申,这是一个概率问题!
叫囚犯出去是随即的,不可能点名不让谁出去!

杀死所有没有摸过灯的囚徒

似乎4楼的答案是唯一的，期盼中......

看来要公布答案了!

先将天数分段,每100天分一段,即每100天的囚犯负责记数.
假设最开始时灯是开的.
在第1个100天内,如果每个囚犯是第一次被叫出去,那么他不对灯进行操作,如果他是第2次被叫出去,那么他就操作灯,如果他是2次以上被叫出去,那么他也不操作灯.
则如果第100个囚犯发现灯是亮的,则表示每个囚犯都出去了.当然更大的可能性是他看到灯是灭的.
然后再以100天为1段区间,此时灯是灭的.
在第2个100天内,如果每个囚犯是第一次被叫出去,那么他不对灯进行操作,如果他是第2次被叫出去,那么他就操作灯,如果他是2次以上被叫出去,那么他也不操作灯.
则如果第100个囚犯发现灯是灭的,则表示每个囚犯都出去了.当然更大的可能性是他看到灯是亮的.
此后的过程是上述过程的循环.

解题思路:计算机语言中的循环和归零.

没看懂~~你这么弄还是没得出答案来~~

[quote]原帖由 [i]沈沉沦[/i] 于 2007-7-4 10:29 发表
在第1个100天内,如果每个囚犯是第一次被叫出去,那么他不对灯进行操作,如果他是第2次被叫出去,那么他就操作灯,如果他是2次以上被叫出去,那么他也不操作灯.
则如果第100个囚犯发现灯是亮的,则表示每个囚犯都出去了[/quote]

不对啊，假设前99天有2个人被叫2次，另外95人叫一次，那么灯是不是亮的？

[quote]原帖由 [i]沈沉沦[/i] 于 2007-7-4 10:29 发表
看来要公布答案了!

先将天数分段,每100天分一段,即每100天的囚犯负责记数.
假设最开始时灯是开的.
在第1个100天内,如果每个囚犯是第一次被叫出去,那么他不对灯进行操作,如果他是第2次被叫出去,那么他就操作 ... [/quote]

晕倒，那来的小毛孩糊弄咱大爷？

我觉得4楼已经是天才。至少是个具备了计算机思维的人。期待更伟大的天才出现。

楼主的答案明显错了啊，前100天内如果只出去过2个人，一个奇数天出，一个偶数天出，灯也是亮的，可是只有两个囚犯出去过

我晕，出差了一端时间，就被误解成这样啊！
可能是我前面的表述有问题，现在从新解释一下：
前面大家争论的关键是偶数个人被重复叫出去放风并且对灯进行操作就会导致错误，那么我们可以锁定一下，在每100天中第一个被重复叫出的人（既第一个被叫出2次的人）才进行操作，其余的人都不对灯操作（包括被叫出去2+次的人和第N个被叫出去2次的人）。
接下来就是要判断每100天中谁是第一个被叫出去2次的人了：
假设第N个100天开始灯是灭的（囚犯可以通过计算判断第N个100天开始灯的状态），第M个人被叫出去，如果他看见灯是亮的，显然他可以知道在他之前有1个人被叫出去2次了，那他旧可以不对灯进行操作，如果他看见等是灭的，那么他就知道自己是第一个被叫出2次的人，他就可以对灯进行操作。
此解法的弊端在于：第N个100天结束时的囚犯运气是否够好，能看到他期望看到的灯的状态。这就需要他拼人品了。。。。

囚犯之间又不能联系，谁告诉他们这么统一的操作和不操作呢？

回复 #26 沈沉沦 的帖子

按楼主的解法,哪个囚犯去报告每个人都出去过?他要看到怎样的灯的状态?:qoo+
希望楼主回答

我认为楼主可以把人数减少(比如10个)然后做个程序验证比较好

[quote]原帖由 [i]沈沉沦[/i] 于 2007-7-24 12:10 发表
我晕，出差了一端时间，就被误解成这样啊！
可能是我前面的表述有问题，现在从新解释一下：
前面大家争论的关键是偶数个人被重复叫出去放风并且对灯进行操作就会导致错误，那么我们可以锁定一下，在每100天中 ... [/quote]

看到楼主的这个贴，我再次晕倒，我原来以为楼主是读历史或者文学相关专业的，但我现在感觉到我错了，楼主一定一定是政治专业毕业的，对吧？

请让我将楼主的解法简单讲一下：只要从第一百个人开始，连续一百个人不重复地被放出，那么灯就没有被操作，最后一人可以判断所有人都已被放出过一次以上。

建议楼主再看看4楼的解法，如果看不懂的话请和你的老公或者BF讨论讨论。

也，这个帖子还在讨论:titter:

我那个方法数学期望是10000，10000/365约等于27.4，大概按照正常概率有生之年可以出结果。

楼主你那个方法糟糕就糟糕在归零上面，期望大概是100的100次方，大概在一个零头的时候，太阳系已经毁灭:wacko:

然后再以100天为1段区间,此时灯是灭的.
在第2个100天内,如果每个囚犯是第一次被叫出去,那么他不对灯进行操作,如果他是第2次被叫出去,那么他就操作灯,如果他是2次以上被叫出去,那么他也不操作灯.
则如果第100个囚犯发现灯是灭的,则表示每个囚犯都出去了.当然更大的可能性是他看到灯是亮的.


若第2个100天内，只有俩个人被叫出去（以前的出场次数少于2），那这俩人就都会操做一次。即由原先的灯灭 会被开关各一次，最后灯是灭的。不知我写的能否证明楼主的算法有问题。

[quote]原帖由 [i]asky[/i] 于 2007-7-25 23:58 发表
也，这个帖子还在讨论:titter:

我那个方法数学期望是10000，10000/365约等于27.4，大概按照正常概率有生之年可以出结果。

楼主你那个方法糟糕就糟糕在归零上面，期望大概是100的100次方，大概在一个零头的 ... [/quote]

我们可以做一个最简单的假设：每个单位循环时间内（100天）就是没有人被重复叫出。
那么4楼的方法判断囚犯全部被叫出需要10000天，而我的方法判断囚犯全部被叫出只需要200天。孰优孰劣，一目了然。

楼上是怎么算出我的方法的数学期望的？100的100次方？很不解:doubt:

很明显囚犯全部被叫出大概只需要2到3年，我们需要的只是最快的判断方法而已。

真不知道lz的逻辑，如果200天灯是亮的，是否说明所有都出去过？
                           如果200天灯是暗的，是否说明所有都出去过？
是不是无法判断啊，lz你想清楚些啊

你的解法一定要[color=Red][size=6]说明“何人在看到什么样的状况下可以报告所有囚犯都出去过”，[/size][/color]
这是重点，不然你说再多有什么意义？

实践,请用实践检验.当然需要楼主先检验自己的解法十分正确再来公布.

好的那么我来估计一下楼主的方法的期望吧
只有在100k+1到100k+100天之内所有人各被放出去一次才能大赦对吧

100!/100^100=9.33*10^(-43)计作q

也就是说每个100天能大赦的概率是这么些

好我们再算期望到底是多少

应该是100q+200q(1-q)+300q(1-q)^2+...是吧

也就是100/q=1.07*10^44天

恩不错不错，似乎还没有到100^100那么夸张:P

没算错把

然后再来算下四楼答案的期望吧

其实四楼的答案就是剩下99人中第一个人放出来，然后观察者放出来，然后第二个人放出来，观察者放出来，依此类推，第99人放出来，观察者放出来

期望是100/99+100/1+100/98+100/1+...+100/3+100/1+100/2+100/1+100/1+100/1

算了一下是10417.7天

哪个大哪个小啊我糊涂了....

[quote]原帖由 [i]reynolds_wwy[/i] 于 2007-7-26 19:06 发表
好的那么我来估计一下楼主的方法的期望吧
只有在100k+1到100k+100天之内所有人各被放出去一次才能大赦对吧

100!/100^100=9.33*10^(-43)计作q

也就是说每个100天能大赦的概率是这么些

好我们再算期望到 ... [/quote]

终于碰到学过概率的兄弟了，握手!

本人思路：其实这个题目能做文章的只有灯，天数和人数。天数和人数这个在每个囚犯心里都是有数，而灯只有两种状态，最主要的是把这三个结合起来碰出一个绝对情况。
误区：所谓的什么1个人被反复的叫上n次，或者始终有一个人没被叫出来，或者每次大家机会平等的被叫出来的的时候总是有人被叫两次。
asky思路：拿一个人做记数器。记上自己关灯的次数。来推算大家有没有都被放出来，显然只利用了灯的状态而没有用到过了多少天和人数的关系。但确实这个方法可以让大家出来。而且我认为很高明。
我的思路：就是每一百天做为一个单位。如果在一百天里有任何一个人被重复，或者n个人被重复，就放弃这一百天。拿下一个一百天来计算。
我的思路和asky的思路比较：
假设1：运气非常好，每个人都只被叫出来1次。而且大家都知道第一天的灯的状态（进去前大家可以商量灯的原始状态）那么100天时候只要灯的状态和第1天一样，大家都可以出来了。（说了运气好大家就不要在什么什么的了，），只要100天大家都可以出来了。而这个时候似乎，asky记数只记了0吧。
假设2：如果运气不好，第一个100天里面有人被叫出来两次或者两次以上或者n个人被叫出来n次（反正是乱七八糟的情况出现）那大家都放弃这100天，怎么放弃呢？就是第一个被叫出来两次的人对灯的初始状态做一下改变。其余的同志你们大概都知道第一天灯的状态是什么把，如果你们在这100天里看到灯与第一天的状态不同，请你们不要手痒-----放弃对灯操作（第一个被叫出来两次的人你已经对灯操作了，就请你如果在这100天里被第三次叫出来的时候不要手痒了，让灯保持你看到的状态）。让所有的人都知道在101天的时候灯的状态（如果有人怀疑大家都不知道1，101，201，301，xx01；xx趋于无穷大时候灯的状态，请你想想或者仔细看看我的方法）这个时候同志们都没有出来。在101-200里asky状态有3种：1.巧合：1）你又被叫了99次，2）还要是隔天被叫，3）其余同志也是隔天被叫，且只被叫了一次。而asky要天时，地利，人和呀！ 2.3个巧合有任何一个不成立。 3.就是大家运气好又只被叫了一次，那么200我的人都可以出来了，但asky你才记了1。
在前两百天里，100天的时候拼人品，我出来了。asky只能有50个人（包括他自己）人品超级好（而且他的人品是其余49个人的总和），这样他可以记49次。
200天（前一天人我这边有人人品稍微好了点被叫出来2次以上）大家改邪归正，人品平均，那么200我出来了。asky人品超级好是其余99个人的总和，而其余人品都平均，且隔天爆发超过了asky。那么asky也出来了。
假设3：201-300.这个时候asky状态：1.人品好被叫出来99次（300天的任何1天），其余人不用隔天出来，但要看asky是那天出来99次的，如果是201那么asky有一次可以是隔两天出来。202可以是隔三天或者有两次隔2天出来。依次类推。那么asky你出来了，我还没有头，两百天我的人总有发扬雷风精神，被天谴责了。大家人品拉到同一个起跑线，300天我才出来。
假设4：301-400天，大家可以推算了。
比较：前200天，我优先。如果有人没看懂，那算了。如果有人就觉得asky人品超级好，那也算了。
201-300天，asky可以比我先出来，我输。但是这个取决于asky的人品了。
301-400天，asky可以比我先出来，我输。但是这个也取决于asky的人品了。
以后asky都可以比我先出来，我输。无穷的时候asky人品递减。
总的来说我的思路是希望大家都很平等，虽然有的时候有人出风头，但是总有那么xx01-x(x+1)00天里大家人品平等。当然你可以用数学期望值，也可以用极端法来反驳，就是总是在100天这个单位里，有人出风头。那么我承认我人品差。我不该相信人人平等或者趋向平等这个说法。当然其实如果有人能想到不用100作为单位而用更合理的一个单位，最好是无论什么时候只要100个人都出来那么就让这个人宣布大家都出来了。
asky的思路是有一个人人品超级好，那么他可以在大于200天后的某一天就能出来了。如果大家平均的人品的话，他只能到10000以后了。
总结：1.100个人人品平均那么我10000里可以出来100次;.asky人品超级好，10000可以出来50次;2.10000里，只要让我逮到一次100天为单位里面大家人品平均我就能出来了;.10000里随着asky人品的递减出来的次数减少。3.超过10000天asky你牛，你随时都能出来，而我机会永远是比你小。
27年呀，1个人呆着说话能力都没了。能不能数到99呀。
还有我的那个方法，再解释一下：100里reynolds_wwy 你被第2次叫出来，你就对灯操作一下。墨叶 你虽然也是第2次被叫出来，就委屈你不要对灯操作，其余的人也是。reynolds_wwy 你第3次被叫出来，也不要对灯再操作了。即使你被叫了99次你也不要再对灯操作了。这样100天的时候只要看到等和第1天状态1样，就能宣布了。因为100里灯只能由亮变暗或者由暗变亮。不会出现亮变暗再变亮。要是还在对我的方法怀疑，我要发飚了。
但和asky的方法比较的话，同志们拼运气比人品及题目的合理性综合考虑一下。

PS：
对ASKY思路：我所谓的你是把你当作了记数的人。
对我自己的思路：我所谓的我是把我当做第N个100天出来的人。

发飙也没用
事实摆在那里的
我只问你一句，如果100天以后你看到的灯不是你希望的样子是不是这100天就白过？

是的话ok，那期望就是10^44数量级的，不开玩笑地说比四楼的方法花的时间多用了10^40左右倍，知道这是什么概念么？

如果不是白过的话那么sorry我理解错

刚刚仔细拜读了楼主的解释
发现楼主的概率学是按照人品什么都是1/2的
那么请问楼主
某天某人走在路上被飞机砸到的概率也是1/2么？

当然这是玩笑

建议楼主编个程序Monte Carlo法测试一下10个人按照楼主的做法平均要几天
100个人建议免了估计楼主会以为机器死了....10^44，不敢想象

提供点数据吧，asky的做法，10人的期望118.29天
楼主的做法27557.3天

这样是不是会直观一点

reynolds_wwy 万一100个人都只被叫出来一次，难道你还不让大家出来吗？
天数趋于无穷，记数的那个人当然才叫出来99次的可能性大了很多，而他关灯的概率也随着天数的增加而增加。我那个方法确实就是你理解的100天为一个单位。
我的方法随着天数的增加概率变的越来越少。因为放样的话，我的方法就一个情况100，每个人只出来一次。10000以后我的分子概率仍然不变，而分母增大。所以我的出来的概率会越来越小。
大姐你非要按无穷来想，那么大家都不要出来算了！我就死都不让一个人出来。其实让一个人20年在没有任何交流的情况下生活我令愿死了算了。如果我是囚犯我令愿相信大家运气都好，就100天或者200左右就被放出去。而不愿意到200天后才可能只被记数1。
什么东西都按公式，或者理论什么的而脱离了实际情况，我想是不是太极端了？

概率计算并不是指公式的问题，概率是这个世界上发生事件的一般规律的考虑。

reynolds_wwy的概率计算是基于事件分布统计的。

你的方法因为清零，使得数据的累积停留在100天以内，问题是100天内每个人被叫出来一次的概率太小了。

因为题目指明是随机叫人出来，每天叫出来的囚犯可能是100人中的任意一个，那么一百天累积就会得到一共100^100种的可能，这是指，会有这么种不同的情况。

而其中符合你要求的，正好一百人每人出来一次的可能性有多少呢？是100！

(100！/100^100)这就是在100天内每人被叫出来一次的概率啊，你自己用计算器算一下，太小了，这个概率比一个人一辈子去买彩票中一次500万的概率还小几个天文数量积，这种人品不值得拼啊。

回复 #43 沈沉沦 的帖子

orz........楼主原来是在胡闹啊，艾看来我掺和错了
哦对了刚刚的计算实在每天叫到任何一个人机会均等的情况下算的
其实作为囚犯你制定策略时也只能做一些合理的假设，毕竟你根本不知道那个选人的究竟会用何种策略，当然如果楼主说选人的是大善人就喜欢按顺序来叫那我也无语

纠正楼主几个小瑕疵...

万一：是10^44分之一不是万一
令愿：宁愿

还有我不是让楼主去随机模拟一下10个人的情况了么，您喜欢100多天出来还是10000多天啊？刚是谁说20多年不能交流死了算了的？

[quote]原帖由 [i]reynolds_wwy[/i] 于 2007-7-27 08:35 发表
orz........楼主原来是在胡闹啊，艾看来我掺和错了
哦对了刚刚的计算实在每天叫到任何一个人机会均等的情况下算的
其实作为囚犯你制定策略时也只能做一些合理的假设，毕竟你根本不知道那个选人的究竟会用何种 ... [/quote]

现在有2点需要说明：
1）有人表示我的方法不能判断囚犯被全部叫出，这个我已经解释过了，若有意见请多看看我的解法。

2）有人认为我的方法能判断囚犯被全部叫出，只是时间很长，大概10^44天，不如4楼的方法好，只要大概10000天。
reynolds_wwy你计算过的，大概100个人第一次全部被叫出大概只需要518天（见《囚犯点灯引出的问题》），也就是说大概2年时间囚犯可以被认为全部被叫出过，只是我们没有办法在2年时间内去很明确地判断出他们已经全部被叫出。
那么我们就说说我们的判断方法：
4楼的思路是记数
我的方思路是计算第N个100天的人能看见[color=Red]第N个100天的灯[/color]能够证明囚犯全部被叫出[color=Red]的状态（亮OR灭）[/color]，用我的方法需要计算的数学期望应该是这个才对，所以十分怀疑reynolds_wwy计算结果的正确性。
若还有意见，请继续拍砖吧！

[quote]原帖由 [i]asky[/i] 于 2007-7-27 01:49 发表
概率计算并不是指公式的问题，概率是这个世界上发生事件的一般规律的考虑。

reynolds_wwy的概率计算是基于事件分布统计的。

你的方法因为清零，使得数据的累积停留在100天以内，问题是100天内每个人被叫出 ... [/quote]

我所谓的每个100天归零是说判断方法的改变，而不是将该100天进出的人数也忽略掉！
毕竟在2年到3年的时间内，囚犯应该都能被叫出，我完全没有必要认定所有人都在第N个100天全部被叫出。

楼主的语言，即然有那么多人有异意，那起嘛你在表述上的逻辑是有些不清晰的。至于算法上的逻辑，只要你写出来，我不会看，也会输入运行。不当机就行。

[quote]原帖由 [i]沈沉沦[/i] 于 2007-7-26 22:07 发表
我的思路：就是每一百天做为一个单位。如果在一百天里有任何一个人被重复，或者n个人被重复，就放弃这一百天。拿下一个一百天来计算。 [/quote]

[quote]原帖由 [i]沈沉沦[/i] 于 2007-7-27 09:27 发表
我所谓的每个100天归零是说判断方法的改变，而不是将该100天进出的人数也忽略掉！
毕竟在2年到3年的时间内，囚犯应该都能被叫出，我完全没有必要认定所有人都在第N个100天全部被叫出。 [/quote]

怎么能不将该100天进出的人数忽略掉啊？你这个方法在100天内得不到确数，无法遗传到下个100天。

[[i] 本帖最后由 asky 于 2007-7-27 10:07 编辑 [/i]]

[quote]原帖由 [i]an老忘密码[/i] 于 2007-7-27 09:45 发表
楼主的语言，即然有那么多人有异意，那起嘛你在表述上的逻辑是有些不清晰的。至于算法上的逻辑，只要你写出来，我不会看，也会输入运行。不当机就行。 [/quote]
我也感觉到表述有问题！居然没有人看的懂！:qDD+
看来要好好组织语言了。

好好组织吧

希望是我理解错了

其实比四楼好的办法还是有的，但是数量级相差不大似乎

建议参考
[url]www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf[/url]

对楼主的表达真是无语，

在[color=Red]每100天中第一个被重复叫出的人[/color]（既第一个被叫出2次的人）才进行操作，其余的人都不对灯操作（包括被叫出去2+次的人和第N个被叫出去2次的人）。

这句的意思难道是在第N个100天内，第一个被叫出两次的人，而不管他在第N-1个100天前是否被叫出过？
如果是这个意思，那要在100天内叫出100个不重复的囚犯，这种概率.........



我看楼主这个问题吸引人的地方就在于不能发生误判，即不是每个人都出去而去报告，而楼主刻意
把它解释为“不会出现有人叫了10+次，而其它人没叫到情况”，那有什么意思呢；1000天每个囚犯平均有被叫到10次的机会，
我看还不如ls的意见，大家约定4－5年后去报告，还省得看灯

[[i] 本帖最后由 zuziwuming 于 2007-7-27 22:06 编辑 [/i]]

楼主的表达真的有问题，枝端末节纠缠不放，关键问题含糊不清。
就我的理解能力，我总结一下楼主的做法，省得再有兄弟跟我似的白白丈二老半天。
其实，楼主说了一大堆，而且在细节的地方有反复，但总体思想就是把灯的状态变化作为一个flag，标识成败 。也就是说——100天里灯有变化就失败；没变化就是楼主所谓的人品超好，成功。楼主的思路应该就是这一句话吧。
那如果是这样的话，关键问题出来了——每个100天归不归零？也就是说，以前被随到的人，他被随的状态也就是被随过几次要不要带入下一个100天中？
大家的理解都是归零，没有什么可说，理论上绝对可行，实际上绝对不可行。楼主可以认真看大家的回复，不要急着否认。
不过看楼主又概率越来越小，又人数可以保留，大概是按不归零来算。可不归零的话，理论上是不是可行都是问题了。举个简单例子，第一个100天，情况：1－99号囚徒都被随到，1号被随到2次；理论：操作灯，灯变，失败。第二个100天，情况：只随到1号100次。理论：因为不归零，2次被随状态被带到这个100天里，这100天中1号每次被随到都是从大于2次开始计算，不操作灯，灯无变化，成功；实际：100号没有被放出，失败。矛盾！
所以，楼主如果说不归零，理论上都不可行。如果说归零，就不要再说什么概率越来越小，人数可以保留；N个100天，不管N是多少，都是一样重复一个过程，只是N++的拼彩票，就不要再和asky的方法比效率了。
还是那句话，我的语文肢解能力就只能解读楼主到这个水平，楼主不认同，大可推翻重来。不过，注意表达了，末节的东西如果不是为了要自己明白就不要砸来砸去，放心，如果真的能关键问题表达清楚，没有人会不明白。


PS：楼上说的很对，楼主自己的题目自己要搞懂。题目要绝对肯定，不是可能肯定，或是火星人肯定。所以别说什么2，3年全放出来或是大家都出来过还不让人家走的话，概率期望也好，某种可能也好，和楼主要求的某人绝对肯定都是两嘛事。

[[i] 本帖最后由 龙剑止水 于 2007-7-29 04:09 编辑 [/i]]

不是说用计算机语言处理吗?
通过PASCAL等编程软件都是可以解决的啊:hug:

想清楚了，我的解法的确有问题！对不起了大家！
不过希望大家能继续思考，个人认为还有更优解！

看了半天才明白lz的意思 本来还以为是自己理解能力的问题
领悟后才发现lz的解法不是正常人会去考虑的 要知道在特定100天是否重复叫人的概率可不是       0.5 +0.5=1的问题。。

楼主，你的计算结果有问题

第一个100天，因为任何人都没去放过风，所以有人第一次去望风的机会是100%
N个100天以后，因为有M个人去放过分，所以有人第一次去望风的机会是1-M%
当有99个人去望过风以后，最后一个人在100天内出去望风的机会是1%
所以你的结果明显是偏小了，实际情况是为了在99个人都望过一次风以后要让最后一个人去望风，需要50*100天才能成功的可能性也不超过50%

[quote]原帖由 [i]asky[/i] 于 2007-6-28 05:18 发表
我有个方法，不过运气不好应该需要几百年时间吧，哈哈哈:titter:

假定初始灯是关的。

指定一名囚犯A，负责关灯：

如果他放风时，if 看见灯是亮的，then 关掉;并且计数加1；

其他人出来放风，if 以前 ... [/quote]

　
[Quote]
囚犯间不能联系
[/quote]

请问这个指定要如何指定法？

       　

[quote]原帖由 [i]岱瀛[/i] 于 2007-8-4 20:50 发表


　


请问这个指定要如何指定法？

       　 [/quote]

开始讨论的20分钟里指定吧
黛儿看题不仔细

:q(+确实没看到．

偶素在想，假如他们一直都没联系过，仅知道总共的人数，凭他们的聪明才智，解决这个问题．:titter:

p.s : 假设这１００人都绝顶聪明（哈哈，象强盗分金了）

思路：给所有的囚犯编号1-100，然后第一个放风的人在灯旁边的地上画一个10*10的方格。每一个被放风的人在方格中自己的位置做一个记号表明“我”已经出来放过风了。当最后一个第一次出来放风的人做记号的时候，就会发现所有的人都出来放过风了。

结论：这个题实际上跟开不开灯没关系，只要有办法证明所有的人都被放风就可以了。当然灯还是要的，否则看不见啊！

假如中途有人挂了...应该不计算在内吧

因为是随机状态下抽人,即1%几率,所以100个一定有一个会被抽出去的....废话
第一个出去的人看到的灯是OFF的,如果他开了则变成ON..........严重废话
第一个人如果不开,则灯为OFF,第二个人不开灯依旧OFF,第二个开灯,灯则为ON,若第二天的人还是第一个人的话,他则开灯,以梅花间式则到第100个时灯为OFF,若灯为ON,则一定还有人未放风!........这个应该没有异议吧

因为计算过分复杂,故建议到100天时,换个灯泡吧.................无意义!

就一张灯？