百囚问题之【你是最后一个出来的吗？】

KeyTo9_Fans

国王招来100个囚犯，对他们说：你们犯了死罪，理应判处死刑。但我今天决定开恩，给你们一次逃生的机会。你们稍后将会被分开地关在100个房间里——1个房间只关1个人。这些房间都是密闭的，在里面无法获得任何外界的信息，直到房间门被打开——我会按照某种顺序【注1】，一个一个地打开你们的房间。

每打开一个房间，该囚犯都会被带到一个特殊的房间——这个房间里有6盏灯。最初的时候，6盏灯都是灭的。看了这6盏灯之后，该囚犯必须回答该问题：“你是最后一个出来的吗？”如果答错了，那么逃生失败，全体杀头。如果答对了，那么该囚犯可以改变若干盏灯的状态——点亮或者熄灭，然后回到自己的房间。除了灯的状态之外，该囚犯在该房间里留下的任何痕迹都会被清除。如果100个人均回答正确，那么逃生成功，全体无罪释放。现在你们可以商量如何尽可能地全体答对问题。若干小时过后，你们将会被完全分开，接受生死考验。

注1：一共有 100*99*98*...*1 = 100! 种顺序，国王按照任何1种顺序打开房间的概率都是相等的，均为 1/100! 。

这100个囚犯希望活命的概率尽可能大。

问：最佳策略是什么？最大的活命概率是多少？

hujunhua

如果6盏灯是理想的冷光源灯，不能利用灯的热度来揣度顺序，就纯粹靠编码方法了。 记灭为0，明为1，  6灯之明灭可表64个6位二进制编码。第1人进去后看到的是000000，他改成000001，第2个人看到000001后改成000010，依此类推，第64个人看到的是111111，他改回000000，然后第65至99号重复1~35号的作法，结果第36人和第100人面临相同的状态100011，他们答对的概率都是50%，所以按照这种方法，活命的概率是25%。

还有改进余地吗？似乎有，因为假使增加至128个囚犯，使得每个编码恰管2人，活命的概率也能达到25%。 现在人数减少了28人，可以只用50个编码就能达到25%的活命概率，如何充分利用14个冗余码来提高活命概率呢？

hujunhua

如果恰好64个囚犯，那么按照上述编码方法可以100%成功。现在先考虑极端情况：把100人改成65人，最佳策略能创造多大的活命概率？

KeyTo9_Fans

百度数学吧虽然水资源丰富，但水里却隐藏着不少大神牛级别的人物。

已有大牛在这个贴子里给出了逃生率为$64%$的方案：

http://tieba.baidu.com/p/2300149695

虽然如此，我们还是有机会比数吧的神牛们做得更好：

要么给出逃生率更高的方案，要么证明所有的方案逃生率都不大于$64%$。

dianyancao

猜测64%为最高逃生率。
尝试寻找0-64之间的某些自然数做连乘积，使得连乘积为一个确定常数，
并且任意破坏其中的若干自然数为1，都会使得结果常数发生变化。
可能是我没做好，没有找到这个组合。

尝试取若干0-64之间的素数组合做连乘，取模映射为小于64的自然数，其中把0当1用
用素数做模时，得到的余数分布较均匀，其他0-64非素数中的模，得到的余数分布不平衡
我测试的结果不太理想。

——————————————————————————————————
还是用加法求和得到的逃生率高，根据数吧的神牛的方法，测试得到
逃生率在64%左右。
C++测试代码：

1. #include <cstdlib>
   
2. #include <iostream>
   
3. #include <time.h>
   
4. #include <stdio.h>
   
5. 
   
6. using namespace std;
   
7. 
   
8. int main(int argc, char *argv[])
   
9. {
   
10.     int testcount=1000000;
    
11.    
    
12.     int *p=new int[100];
    
13.         int unpass_forecast=36;
    
14.         int module_forecast=64;
    
15.         int result,test_result;
    
16.     int pass=0,unpass=0;
    
17.    
    
18. 
    
19.     int n,i,j;
    
20.     int random,temp;
    
21.    
    
22.     for (n=0;n<testcount;n++)
    
23.     {
    
24.         srand(n);
    
25.         j=0;
    
26.                 result=0;
    
27.                 test_result=0;
    
28. 
    
29.         for (i=0;i<100-unpass_forecast;i++){
    
30.                         p[j++]=1;
    
31.                     result+=1;
    
32.                     result%=module_forecast;
    
33.         }
    
34.   
    
35.         for (i=0;i<unpass_forecast;i++){
    
36.             p[j++]=0;
    
37.         }
    
38. 
    
39.                 for (i=0;i<100;i++){
    
40.             random=rand()%100;
    
41.             temp=p[i];
    
42.             p[i]=p[random];
    
43.             p[random]=temp;
    
44.         }
    
45.    
    
46.         for (i=0;i<100;i++){
    
47.                         if (p[i]==0) continue;
    
48.             test_result+=p[i];
    
49.                         test_result%=module_forecast;
    
50.             if (test_result == result)
    
51.                 break;
    
52.         }
    
53.    
    
54.         if (i==99)
    
55.             pass++;
    
56.         else
    
57.             unpass++;
    
58.     }
    
59.     cout<<(int)(result)<<endl;
    
60.     cout<<pass/(double)(pass+unpass)<<endl;
    
61.    
    
62.     delete [] p;
    
63.     system("PAUSE");
    
64.     return EXIT_SUCCESS;
    
65. }
    

复制代码

无心人

考虑模某个素数的序列如何？

无心人

或者找个函数，
上个的输出当作这个的输入
n=1..100时候
当且仅当n=100时候，等于某个唯一不重复值

dianyancao

是啊，可以为每个人分配一个函数f(nth,protocol,last_input)
用nth标记每个人的ID，这个函数只和(nth,约定的协议,该人看到的灯的状态)有关

用每次将灯的状态+1的方法，最多可以标识出64个人
其他36人总是回答不是，那么逃生率为64%

协议约定每个人可以采取的策略是：
1.总是回答是
2.总是回答不是
3.是和不是都可以依据f的参数回答
显然若有一个人总是回答是（和看到的灯状态无关），那么逃生率将不大于1%
因此最后一个人参考灯的状态来回答，其逃生率的一个下界将是64%。

选择的函数f(.),需要满足：
1.函数f(.)乱序复合100次,得到的值c都相同
2.从函数f(.)乱序复合n次（0<=n<=99）后，得到的值不等于c
否则，逃生率将不大于50%。
因为不满足上述两个条件时，会有两个人遇到相同的灯状态c，这两个人的nth先后顺序无法区分
因为总是可以交换这两个人的nth。

还是没有证明逃生率不大于64%，是否存在满足上述条件的函数使得逃生率等于100%或大于64%呢？

无心人

昨晚想了一晚，不可能大于64%，但是不会证明
因为状态最多只可以有64个

平常心

6盏灯可以给出64个不同信息。这似乎是留给这100个囚犯的唯一联系方式。
“除了灯的状态之外，该囚犯在该房间里留下的任何痕迹都会被清除。”但有一个“痕迹”是无法清除的：时间。囚犯依次被带到同一个房间，这样每个囚犯将占去一定的时间，100个囚犯共占用的时间必然有一个下限，当然也有一个上限（不会超过决定开恩的当天）。
囚犯可以利用64个信息，给下一个囚犯一个有序信息，当64个信号用完之后再从头来。可以假定这64个信息依次代表0~63，那么给最后一个囚犯的信息必然是“35”。问题是35将出现两次，若能够确定这两个“35”的不同之处，囚犯就可以作出正确决定。此时“时间”痕迹就能够发挥它的作用了。若一个囚犯占用5—10分钟，第一个“35”信息应该在之后2小时45分钟到5小时30分钟出现，而最后一个“35”信息将在之后8小时15分——16小时30分个小时出现。这个差别比较大，囚犯也可以事先商量一个控制时间的原则，尽量将这个差别保持在某个较大的范围之内。这样后一个看到“35”信息的囚犯回答“是”，其余都回答“不是”，活命概率就可以得到百分之百。