| 职老:囚徒问题的第三个解释--LUCKY囚徒机制 |
| 送交者: 职老 2009年12月20日12:32:06 于 [五 味 斋] 发送悄悄话 |
|
我在前两次解释中首先探讨了囚徒问题的数学模型和可行性分析,当然,我们其实是假设这是一个纯数学模型的,也就是说,不考虑囚徒的年龄和健康状况的纯数学模型,所以假设其玄正性存在。 那么,如果我们亲手解决这个问题的关键是什么内? 其实问题的关键有两个。关键A,让囚徒能够向下一位表达自己是第一次放风,还是第N次放风,这里N>=2; 关键B,任何一个囚徒每次放风能知道上面X位囚徒被放过风的次数,也就是说第M次放风的X囚徒能知道M次以内被第一次放风囚徒的数目A,当这个数目A累积到100的时候,他就可以宣布了。当然这个X囚徒本身就是随机的,可能是100个囚徒中的任何一位。 这样,我们就不难看出,这个囚徒问题其实包括了两个不同的分布概率,一个叫做:被抽概率,或者说放风概率;另外一个叫做:信号传递概率,也就是说,囚徒必须想办法知道别的囚徒放风的情况,而且不只知道上一位囚徒的,而且还要知道上S位囚徒的。 这样我们会发现一个难点,第M次放风的囚徒从条件上很难知道他被第M放风前S位囚徒的情况,虽然似乎他们可以开会约定一些所谓的组织分布,但其实很难座到有笑的信号传递,因为他们手里面的可作为信号传第的条件只有那盏灯。而这盏灯似乎首先要做到关键A的作用,然后能部分完成关键B的功能。 所以,如果按照不打破游戏规则的条件,囚徒只能遵循一种叫做:LUCKY囚徒的机制完成这项任务。 1)灯是关键A的主要功能。囚徒必须假设灯开为第一次放风,灯关为第N次放风,N>=2。 具体操作如下:囚徒只要是第一次放风,如果看到灯开着,就维持该灯开着;如果看到灯关着,就开灯。 如果囚徒是第N次放风,就保持关着或者把开着的关上。 这样灯本身就只传递唯一一个信息:前面一位是第一次或者第N次。 2)每位囚徒在牢房里面建立一个记录系统,比如用指甲在钢墙上划道道,记录每次被第N次放风后,看到灯开着--前面一位肯定是第一次被放风的。当这个记录数目n(包括该囚徒自己第一次被放风的)=100的时候,就宣布可以了。当然,任何一个囚徒都可以宣布,只要他墙上的n=100的时候,别人的墙上的可能是1-99任何一个数目。 这样我们看到,国王的游戏规则,不但提供了放风机会,而且提供了所谓的信号传递机会,也就是说第N次被抽到提供了一种传递记录前面被第一次抽风的机会,当然,N=2是最佳的结果。 这样,囚徒们就存在两个相关却独自存在的分布: 1)被抽放风分布,简称:抽风分布,这个机率是不变的,第一次和第N次都是一样,为1/100 2)传递分布,这个机率是改变的,可以是100%,也可以是零蛋。 那么,让我来首先先简单的分析一下前10轮被抽和囚徒记录的结果吧(只分析部分) (1)10个囚徒都被第一次抽中,这个分布可以说是最佳被抽分布,但同时也是最差传递分布之一,因为囚徒只知道自己被抽和上一个被抽的情况,墙上最多记录2道(第一个囚徒一道) (2)一个囚徒被抽10次,这个分布可以说是最差被抽和被分布情况; (3)10个囚徒中有个最LUCKY的家伙,他被第2,4,6,8,10反复被抽放风5次,这样,他就可以记录6个道道了。这个是最佳的抽风和传递分布 (4)其他的情况介于这些分布之间 这样我们看来,如果囚徒按照一般的规律进行,当某个囚徒发现自己墙上的道道是100而宣布游戏结束的时候,其它的囚徒应该是1-99的正态分布,也就是大约一共记录了5500次的第一次被抽。如果按照10%幸运程度计算的话,总体被抽次数就是这个数目的10倍,大约55000天,也就是150年以上;如果按照5%可信度计算,就是110000天,也就是300年。 当然,如果存在一个LUCKY的囚徒,也就是这个囚徒被反复的交叉被抽中,比如刚才说的2,4,6,8,10,12,。。。。。,大约201天,他的墙上就是100个道道了,这样大家就粗去了,嘿嘿。 这个机制就叫做:LUCKY囚徒机制。 所以,按照抽风机率和传递机率以外的第三个总体分布而言,囚徒的被放出的机率可能是201天到大约300年,估计是T分布,嘿嘿。 其实,按照不破坏游戏规则和不让国王怀疑的前蹄下,可以内定一个LUCKY囚徒,让他画累积的道道,其它的囚徒画道道记录开始后的天数。单数1,3,5,7。。。的时候,抽到自己自己就粗去,双数天的时候,被抽到就对监狱长说:俺不想粗去,让LUCKY囚徒出去(比如说他身体不好,需要爱心什么什么的,嘿嘿),这样,虽然不能201天就粗去(因为非LUCKY囚徒有可能被N次抽到)。 当然,也可以把100个囚徒分成10组,每组构建一个LUCKY囚徒,以防止国王生气,但必须规定好每组只负责10天,轮流交替,当其中一组LUCKY囚徒墙上的道道为100的时候,宣布解放,嘿嘿。当然,冒险的话也可以是N=30左右的时候就宣布,嘿嘿。 这样的办法肯定更有笑,但如何找到最佳的分组和负责天数,下次再谈。 |
|
![]() |
![]() |
| 实用资讯 | |
|
|
| 一周点击热帖 | 更多>> |
| 一周回复热帖 |
| 历史上的今天:回复热帖 |
| 2008: | 【FLASH动画涂鸦】铅笔模仿国画——聆 | |
| 2008: | 西西里柠檬: 太古遗音--孔子和《文王操 | |
| 2007: | 古文翻译,嘿嘿,准备打印出来教育下一 | |
| 2007: | 华人音乐家系列: 李云迪 | |
| 2006: | 我国白酒的起源 | |
| 2006: | 想说爱你;并不是件容易的事 | |
| 2005: | 塗香天女 | |
| 2005: | 放松心情的方法 | |
| 2004: | 【海外片段】流水- 祝各位节日快乐 | |
| 2004: | 背对生活 | |




