百囚问题之【你是最后一个出来的吗？】
国王招来100个囚犯，对他们说：你们犯了死罪，理应判处死刑。但我今天决定开恩，给你们一次逃生的机会。你们稍后将会被分开地关在100个房间里——1个房间只关1个人。这些房间都是密闭的，在里面无法获得任何外界的信息，直到房间门被打开——我会按照某种顺序【注1】，一个一个地打开你们的房间。有趣的智力题。每打开一个房间，该囚犯都会被带到一个特殊的房间——这个房间里有6盏灯。最初的时候，6盏灯都是灭的。看了这6盏灯之后，该囚犯必须回答该问题：“你是最后一个出来的吗？”如果答错了，那么逃生失败，全体杀头。如果答对了，那么该囚犯可以改变若干盏灯的状态——点亮或者熄灭，然后回到自己的房间。除了灯的状态之外，该囚犯在该房间里留下的任何痕迹都会被清除。如果100个人均回答正确，那么逃生成功，全体无罪释放。现在你们可以商量如何尽可能地全体答对问题。若干小时过后，你们将会被完全分开，接受生死考验。注1：一共有 100*99*98*...*1 = 100! 种顺序，国王按照任何1种顺序打开房间的概率都是相等的，均为 1/100! 。
这100个囚犯希望活命的概率尽可能大。
问：最佳策略是什么？最大的活命概率是多少？ 如果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个冗余码来提高活命概率呢？ 如果恰好64个囚犯，那么按照上述编码方法可以100%成功。现在先考虑极端情况：把100人改成65人，最佳策略能创造多大的活命概率？ 百度数学吧虽然水资源丰富，但水里却隐藏着不少大神牛级别的人物。
已有大牛在这个贴子里给出了逃生率为$64%$的方案：
http://tieba.baidu.com/p/2300149695
虽然如此，我们还是有机会比数吧的神牛们做得更好：
要么给出逃生率更高的方案，要么证明所有的方案逃生率都不大于$64%$。 猜测64%为最高逃生率。
尝试寻找0-64之间的某些自然数做连乘积，使得连乘积为一个确定常数，
并且任意破坏其中的若干自然数为1，都会使得结果常数发生变化。
可能是我没做好，没有找到这个组合。
尝试取若干0-64之间的素数组合做连乘，取模映射为小于64的自然数，其中把0当1用
用素数做模时，得到的余数分布较均匀，其他0-64非素数中的模，得到的余数分布不平衡
我测试的结果不太理想。
——————————————————————————————————
还是用加法求和得到的逃生率高，根据数吧的神牛的方法，测试得到
逃生率在64%左右。
C++测试代码：#include <cstdlib>
#include <iostream>
#include <time.h>
#include <stdio.h>
using namespace std;
int main(int argc, char *argv[])
{
int testcount=1000000;
int *p=new int;
int unpass_forecast=36;
int module_forecast=64;
int result,test_result;
int pass=0,unpass=0;
int n,i,j;
int random,temp;
for (n=0;n<testcount;n++)
{
srand(n);
j=0;
result=0;
test_result=0;
for (i=0;i<100-unpass_forecast;i++){
p=1;
result+=1;
result%=module_forecast;
}
for (i=0;i<unpass_forecast;i++){
p=0;
}
for (i=0;i<100;i++){
random=rand()%100;
temp=p;
p=p;
p=temp;
}
for (i=0;i<100;i++){
if (p==0) continue;
test_result+=p;
test_result%=module_forecast;
if (test_result == result)
break;
}
if (i==99)
pass++;
else
unpass++;
}
cout<<(int)(result)<<endl;
cout<<pass/(double)(pass+unpass)<<endl;
delete [] p;
system("PAUSE");
return EXIT_SUCCESS;
}
考虑模某个素数的序列如何？ 或者找个函数，
上个的输出当作这个的输入
n=1..100时候
当且仅当n=100时候，等于某个唯一不重复值 是啊，可以为每个人分配一个函数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”信息的囚犯回答“是”，其余都回答“不是”，活命概率就可以得到百分之百。