100囚徒难题

lulijie

总结：
目前解100囚徒题目的非赌博方法有以下几种方法：
第一种：囚徒只能发送信息给总计数员。方案见18#和206#，经优化后的方案，平均时间约9341天，约25年余。
第二种：囚徒既可发送信息给总计数员，也可与其他囚徒传递信息。方案见214# 、216# 和220#。此种方案要分时间段。经过电脑模拟，发现分三个时间段，第一个时间段200天，基数1，第二个时间段600天，基数2，第三个时间段600天，基数3。该方案所花时间最少，平均时间5836天，约16年。
第三种：囚徒既可发送信息给总计数员，也可与其他特定的囚徒（辅助计数员）传递信息。
      事先定好总计数员和辅助计数员，分两个时间段，统计阶段和汇报阶段，交替进行。
      在统计阶段，一般囚徒传递信息；总计数员或辅助计数员接收信息，直到达到统计的上限为止。
      在汇报阶段，由辅助计数员将达到上限的计数传递给总计数员。
      在交界处，所有的囚徒都负责处理信息。
     具体方案如下：100个囚徒随便编号（1-100），让100号囚徒当总计数员，1-9号囚徒为辅助计数员。每人初始个人计数都为1。辅助计数员的初始汇报次数为1，一般囚徒的初始汇报次数为0。初始灯关着。总计数员和辅助计数员的统计上限都为10。总计数员还有一个汇报总量，接收辅助计数员汇报来的信息，初始为0。汇报阶段400天，统计阶段200天。
   第1-1799天，2201-2399天，2801-2999天，……          统计阶段：
               一般囚徒在灯关着时开灯传递信息，个人计数减1。个人计数清零的不参与。
               总计数员和辅助计数员在灯开着时关灯接收信息，个人计数加1，当个人计数达到统计上限10时，不参与。当个人计数大于统计上限10时，在灯关着时开灯释放多余的计数。
    第1800天，2400天，3000天，……      从统计到汇报阶段的交界：
              所有囚徒在灯亮着时关灯，个人计数加1。
    第1801-2199天，2401-2799天，3001-3399天，……    汇报阶段：
              辅助计数员在灯关着且个人计数>=10时,开灯释放计数10，个人汇报次数减1。当个人汇报次数变为0时，就转变为一般囚徒。
              总计数员在灯开着时关灯接收信息，汇报总量加10。   
    第2200天 ,2800天，3400天，……      从汇报到统计阶段的交界：
              总计数员看见灯开着，关灯，汇报总量加10。
              辅助计数员和一般囚徒看见灯开着，关灯，个人计数加10，个人汇报次数加1。个人汇报次数大于0，就成为辅助计数员。

    结束条件：   在任何时候总计数员的个人计数加上汇报总量等于100，宣布结束，可向国王汇报。
------------------------------------------------------------
    按照该方案，让电脑模拟一万次，平均成功时间3770天，约10年。以下是部分的成功时间：
4501，3853，3233，3682，4550，3838，3081，3128，2759，3211，
3986，3193，3171，2769，3831，3694，4246，4845，3344，3294，
3182，5099，3347，3904，4317，4234，3397，3781，3805，4365，
4304，3188，3627，4393，4982，3740，3218，3317，3792，5041，
3326，3340，3750，3274，4969，3711，2767，3368，3377，3384，
2691，4829，3372，4444，3312，4552，5051，3308，3030，3946，
3616，3916，3245，3035，4467，2585，3044，3201，3816，3756，
3332，3303，5579，3826，3218，4360，4976，3815，4588，4213，

[ 本帖最后由 lulijie 于 2009-1-29 15:17 编辑 ]

獨①無②

没看明白 下班回去慢慢探究

金眼睛

这道题最近很火啊！关于这道题提一点个人看法 ：）

看了大家的答案，大家都倾向于制定一种100%成功的计划，计划都很精彩。
其实，每种计划都在一定概率条件下可能使囚犯们老死狱中。

我计算了一下，平均500多天，囚犯们基本上就都放过风了。

如果囚犯们想赌一下的话：
以千分之一的概率计算，囚犯提出要求时间为lg(10^(-3)/100)/lg(0.99)/365=3.14年(忽略小数量级概率)
以万分之一的概率计算，囚犯提出要求时间为lg(10^(-4)/100)/lg(0.99)/365=3.77年(忽略小数量级概率)
以百万分之一的概率计算，囚犯提出要求时间为lg(10^(-6)/100)/lg(0.99)/365=5.02年(忽略小数量级概率)

这么小的概率如果囚犯们都碰上了，那么同样的概率也可以使计划搁浅。

也就是说，对于某种计划不仅要计算平均时间，还要重视概率分布情况，因为计划过程中有可能使某
些小概率叠加，大大增加了出狱时间。

如果是这样，还不如“无为胜有为”，该吃吃该喝喝该放风放风了，呵呵！

lulijie

答223#：
按照电脑模拟放风过程，试验1000次，500天全部放过风，只出现500次左右，所以这时候赌博，这些玩命之徒是不会干的。

[ 本帖最后由 lulijie 于 2009-2-14 19:39 编辑 ]

lulijie

原话：平均500多天，囚犯们基本上就都放过风。
99个放过风，也算基本放过风。但这个时候宣布，全死。
所以不能用基本来判断，一定要用全部放过风的概率来算。（95%，99%，还是更高的概率）。
应该要用多少天后全部放过风的概率大于一个期望的值才可赌博。
楼主也是名士了，不该犯这样的错误。

dorothea

好晕啊,好自卑...

lulijie

从223#后面的计算公式上可以看出，楼主应该是考虑到了全部放过风的概率，可是计算500天的概率，不知为什么算错了，以致得出了错误结论。
500天全部放过风的精确概率=1-C(100,1)*0.99^500+C(100,2)*0.98^500-C(100,3)*0.97^500+C(100,4)*0.96^500-C(100,5)*0.95^500+……=1-0.65705+0.20307-0.03932+0.00536-0.00005+……≈51.2%
与电脑模拟算出的概率相近。

金眼睛

原帖由 lulijie 于 2009-2-14 22:14 发表
从223#后面的计算公式上可以看出，楼主应该是考虑到了全部放过风的概率，可是计算500天的概率，不知为什么算错了，以致得出了错误结论。
500天全部放过风的精确概率=1-C(100,1)*0.99^500+C(100,2)*0.98^500-C(100,3 ...

lulijie您好，请注意“平均500多天，囚犯们基本上就都放过风。”中的“平均”及“都”，平均当然是50%啦，呵呵!我说话有时候不是很标准，我本身不是学数学的，请关注这种想法本身。

我并不是说大家提出的方案不好，只是提出一种观点让大家注意，就是假设一种方案平均需要N天能够成功，其使囚犯老死狱中的概率为a，而犯人什么都不做到第N天提出请求被杀头的概率为b，如果a大于b，则说明这种方案并不很好。

如果这样的方案不存在，换个思路可以认为国王给犯人们设下了思维陷阱，没有灯大家可能还会赌一把，有了灯反而使大家陷入思维定势、犹豫不决，这个只是我的一点想法，如果方案存在另当别论。

工作比较忙，偶尔才能来一次，可能都有人能猜出我的工作，呵呵！希望lulijie等魔友积极活跃论坛，我也是通过学习魔方，慢慢开始痴迷于这个版块的，希望大家能在G老师的领导下将它越办越好。

lulijie

金眼睛看来是真的很忙，题目的本意当然不是让赌徒赌博。
若考虑到赌博方案的话，最早68楼就提出来了。

棉花糖three

顶！~~~~~~~~~~~~~~~~~~~~~~~~~