100囚徒难题

6212380

难啊。。。。。。。。。

noski

这个赌博的想法很赞！三年都放过风的概率相当大。。
PS：国王奸笑道：嘿嘿，100号签就在我手里，他没放过风...玩笑

Zeon.C

206楼的好强大。。。居然能这么想。。。210也好强。。

lulijie

我还有一个方案的思路：
囚徒之间无法相互传递信息，只能通过灯的状态来传递。
我们假设每个囚徒自己心中都有一个计数器，每个人初始的计数都是1，那么所有囚徒的计数和就是100，我们现在让囚徒通过灯的状态把自己的计数传递给别人，别人通过把灯状态的改变，把它加到自己的计数中，只要囚徒的计数是0，那么他就不参加计数的传递。这样 ，所有囚徒的计数和都是100，保存不变。随着时间的推移，当所有的计数都转移到1个人手中，那么它的计数就是100，也就是说，其他囚徒的计数都为0，就是说所有人都放过风，所以游戏就结束了。
关键是设定灯的一个状态（比如关）传递信息，另一个状态只能表示过渡，不能再传递信息了。灯的一个状态（比如关）只能传递一个信息，那么别人看到灯关着，那么它到底代表传递多少的计数呢。为了让它能传递不同的信息，只能通过时间段的设置，来达到。比如第一个时间段，灯关着表示传递计数1，第二个时间段表示传递计数2，等等。为了不让一个时间段的关灯信息延续到下一个时间段造无法判断它代表的真实信息，必须在交界处对它进行处理，处于这个交界处的囚徒必须把这个信息处理掉，把它传递的计数加到自己计数上，让灯不带信息进入下一时间段。
第一个时间段，关灯代表传递计数1，很多计数是1的囚徒把计数传递到了总计数员中或其他技术员中，这样，这个时间段结束时，囚徒的计数就可能变成0或1或2，甚至更大。到了第二时间段，计数大于等于2的囚徒通过关灯把自己的计数传递给总计数员中。这样就大大加快了总计数员心中计数的增加速度，使它尽快达到100，早日结束这漫长的牢房生涯。

lulijie

我让前100天同206楼的方案，100天以后分两个时间段，不断重复进行，每个时间段为200天，第一时间段传递计数1，第二时间段传递计数2。设定程序让电脑模拟1000次。平均获取成功所需天数为7760，约21年余。以下是部分模拟的成功天数：
7136，7484，8194，7696，5381，6620，6967，10183，9149，6547，
8789，8628，8149，8600，9790，6688，7430，6608，7374，8584，
7882，6661，5448，9130，7175，8954，7050，7759，9886，8156，
11719，8635，7860，9804，7754，8184，6539，8154，6901，9073，
6577，8700，7059，8298，9485，7951，9078，7851，8069，5546，
9307，9063，9053，8535，7876，7843，8632，7599，7792，8501，
6932，7857，7839，6429，8214，6034，7094，7735，5539，7970，
8096，6569，8281，7143，7460，8074，8937，6229，7873，7343，
7842，7049，9041，6171，7408，6441，8073，7842，7410，6292，
--------------------
比以前的方案缩短了大约4年。

lulijie

具体方案如下：初始灯关着，每个囚徒的个人计数都为1。
放风第1至99天   
    第一次放风，看见灯关着，个人计数清零。
    第二次放风，看见灯关着，个人计数变为天数减1，开灯。他作为总计数员。
    其他情况，不做动作。
第100天
    看见灯关着，个人计数为1，报告皇帝。
    看见灯关着，个人计数为0，即 第二次放风，个人计数变为99，开灯。他作为总计数员。
    ------------------------------
    看见灯开着，总计数员，不做动作。
                         个人计数为1，个人计数清零，关灯。
                         其他，不做动作。
第101天以后，分两个时间段（每个时间段的计数基数分别为1和2），按顺序交替进行。用关灯传递计数，个人计数减去基数。开灯吸收计数，个人计数加上基数。总计数员的个人计数到达100，向国王报告。
    101至300天，502至700天，902至1100天，……    基数=1。
              总计数员，看见灯关着，开灯，个人计数加上1。看见灯开着，不做动作。
              一般囚徒，看见灯关着，个人计数=1，开灯，个人计数变为2。
              一般囚徒，看见灯开着，个人计数>=1，关灯，个人计数减1。
              其他情况，不做动作。
    302至500天，702至900天，1102至1300天，……    基数=2。
              总计数员，看见灯关着，开灯，个人计数加上2。看见灯开着，不做动作。
              一般囚徒，看见灯开着，个人计数>=2，关灯，个人计数减2。
              其他情况，不做动作。
    第301天，701天，1101天，……  
              总计数员，看见灯关着，开灯，个人计数加上1。看见灯开着，不做动作。
              一般囚徒，看见灯关着，个人计数=0，开灯，个人计数变为1，
                                                     个人计数>=1，不做动作，个人计数减1。
              一般囚徒， 看见灯开着，个人计数<=1，不做动作；个人计数>1，关灯，个人计数减2。
     第501天，901天，1301天，……  
              总计数员，看见灯关着，开灯，个人计数加上2。看见灯开着，不做动作。
              一般囚徒，看见灯关着， 不做动作，个人计数加1。
              一般囚徒， 看见灯开着，个人计数=0，不做动作；个人计数>0，关灯，个人计数减1。

lulijie

按216楼的方案，生还的时间平均为7760，约21年余。
但分两个时间段也有它的缺点，到总计数员计数快到100时，这时，其他囚徒的计数大部分为0，当还没清零的囚徒好不容易得到放风的机会，关灯传递计数时，由于没有给总计数员接受，在两个时间段的交界处，被收回，由于清零的囚徒特别多，所以基本上是给清零的囚徒接收，所以这样就浪费了很多时间。这时，只分一个时间段的好处就显示出来。还没清零的囚徒好不容易得到放风的机会，关灯传递计数，不会因时间段交界而被回收，而是直到被总计数员接收为止。
所以将216楼的方案再优化。6501天后不分时间段。
6501天后：
             总计数员，看见灯关着，开灯，个人计数加上1。看见灯开着，不做动作。
             一般囚徒，看见灯关着,不做动作。
             一般囚徒，看见灯开着，个人计数=0，不做动作。
             一般囚徒，看见灯开着，个人计数>=1，关灯，个人计数减1。
此优化后的方案，用电脑模拟1000次，平均时间为7500天。以下是部分时间：
6166，7507，6579，6079，7035，8027，6927，7472，8868，7962，
7688，7593，9081，7057，7179，6660，7780，7367，8197，6704，
8203，8793，7997，7303，7332，6807，8039，6957，7998，8094，
6709，6662，6784，7122，7267，6695，7519，6743，8010，10479，
5762，8818，7170，7834，6786，6936，8626，8288，7847，7246，
7681，7703，8322，6938，7462，6746，6425，6179，9126，7016，
刚才程序有错误，现已修正

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

lulijie

各模拟一万次。
方案：两个时间段，每段时间260天，6341天后不分时间段。
    平均时间7448天。
方案：两个时间段，每段时间360天，6581天后不分时间段。
    平均时间7401天。
方案：两个时间段，每段时间400天。
    平均时间7569天。


--------------------
目前红色的方案是所花时间最少的。

骰迷

LS是電腦編程高手啊，佩服

lulijie

模拟一万次。
方案：分三个时间段，第一个时间段200天，基数1，第二个时间段600天，基数2，第三个时间段600天，基数3。
    平均时间5836天，约16年。以下是部分的成功天数：
4269，5280，6217，5355，4702，5453，5758，4642，5954，3931，
6871，6712，5933，4248，5344，5666，6791，6302，4604，6142，
7487，5486，6054，6126，5207，5622，5478，7696，5365，5396，
5948，6320，4754，5642，7737，5261，4810，5358，5890，11384，
5960，4080，5437，4203，6143，7138，5488，5411，6256，4676，
4776，4419，5405，7503，5391，6107，6076，6076，4209，5032，
6472，6474，4270，6381，7512，5570，4582，7600，4019，4881，
7931，6181，7007，5199，7511，5152，8823，5322，5307，6037，
5251，5353，5439，5239，6859，6379，6537，3987，5982，6779，
6190，6602，4909，6784，5712，4649，5590，4846，5554，5316，
4850，5450，7985，4277，6832，5598，6239，6468，6222，6496，