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

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>
6. using namespace std;
8. int main(int argc, char *argv[])
9. {
10. int testcount=1000000;
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;
19. int n,i,j;
20. int random,temp;
22. for (n=0;n<testcount;n++)
23. {
24. srand(n);
25. j=0;
26. result=0;
27. test_result=0;
29. for (i=0;i<100-unpass_forecast;i++){
30. p[j++]=1;
31. result+=1;
32. result%=module_forecast;
33. }
35. for (i=0;i<unpass_forecast;i++){
36. p[j++]=0;
37. }
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. }
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. }
54. if (i==99)
55. pass++;
56. else
57. unpass++;
58. }
59. cout<<(int)(result)<<endl;
60. cout<<pass/(double)(pass+unpass)<<endl;
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”信息的囚犯回答“是”，其余都回答“不是”，活命概率就可以得到百分之百。