101囚问题

l4m2

100张纸条分别写着1-100，乱序放入100个箱子。101个人，分别编号0-100。0号可以看到每个箱子里的纸条，并公开一个1到M的整数。随后1-100号分别可以依次打开50个箱子，试图找到自己的编号。确定策略后除了一个整数就没有其他交流形式，也不能看到别人开了什么箱子。问：要使得必然每个人能找到自己的编号，M至少要是多少？

KeyTo9_Fans

小白解法：用M传递100比特信息：第i号开前50个箱子还是后50个箱子，i=1,2,3,...,100，M=2^100≈1.27*10^30

新手解法：用M传递一个组合数C(100,50)，告诉他们第1-50号在哪些箱子里，1-50号就开这些箱子，51-100号开另外50个箱子，M≈1.01*10^29

高手解法、大师解法、大神解法、上帝解法 会是怎样的？请回贴告知。

magicstrawberry

如果允许开箱人根据箱中数字调整策略的话，有一个思路是，第k个人首先打开第k个箱子，如果箱子里写着n，则下一步打开第n个箱子，以此类推直到用完次数。如果每个链路的圈长不超过50的话，指挥员无需做任何事。但是最坏情况下指挥员发现链路长为100，如果用这个方法，需要告知每个人进入链路的位置（50成功50失败），每人分配1个bit信息的话，M高达2^100。期待楼下改进

KeyTo9_Fans

新手解法：用M传递一个组合数C(100,50)，告诉他们第1-50号在哪些箱子里，1-50号就开这些箱子，51-100号开另外50个箱子，M≈1.01*10^29

经过循环节优化的新手解法：当循环节长度<=50时，令M=1，否则令M=【第1-50号所在的那些箱子在循环节长度>50的那些组合里的序号】+1

M的最大值≈1.01*10^29-s+1，s=C(100,50)里使得循环节长度<=50的组合方案数

这个s大概有多大呢？占比是百分之几？

还能继续优化吗？

l4m2

小白解法：用M传递100比特信息：第i号开前50个箱子还是后50个箱子，i=1,2,3,...,100，M=2^100≈1.27*10^30

新手解法：用M传递一个组合数C(100,50)，告诉他们第1-50号在哪些箱子里，1-50号就开这些箱子，51-100号开另外50个箱子，M≈1.01*10^29

高手解法：用M传递一个交换100×99÷2，保证箱子不存在长度大于50的环，每个人打开整个环

大师解法、大神解法、上帝解法 会是怎样的？请回贴告知。

王守恩

100张纸条分别写着1-100，乱序放入100个箱子。101个人，分别编号0-100。0号可以看到每个箱子里的纸条，并公开一个1到M的整数。随后1-100号分别可以依次打开50个箱子，试图找到自己的编号。
确定策略后除了一个整数就没有其他交流形式，也不能看到别人开了什么箱子。
问：要使得必然每个人能找到自己的编号，M至少要是多少？
答：0可以看到纸条A(任意,1个就够)——策略：0告诉A,A去取纸条B(任意,不是A),  0告诉B,B去取纸条C,  .....。

KeyTo9_Fans

大师解法：用M传递一个交换，可证前51个箱子里必存在1个交换，使得交换后，所有的循环节长度都<=50，M=C(51,2)=1275

l4m2

一个非构造的nlogn做法：
发送1表示不做任意交换就没有大循环节。这种情况占比略大于1/e^{[来源请求]}。
去掉一些状态后，由于叠加一个随机排列后，没有大循环节的占比大于1/e，因此存在一个排列使得占比大于1/e。发生2表示这种情况。
以此类推，每个数字可以排除常数比例的排列。由于一共有n!种排列，最多需要log(n!)=nlogn个数字来表达

（这里log表示底数不确定的对数）

l4m2

附：测试库。

1. #include <stdio.h>
   
2. #include <algorithm>
   
3. int openchest(int);
   
4. 
   
5. int getM(const int* A) {
   
6.     // TODO
   
7.     // states stored in A[1..10]
   
8.     return 1;
   
9. }
   
10. 
    
11. void findself(int id, int M) {
    
12.     // TODO
    
13.     // Call `openchest`
    
14.     openchest(1);
    
15. }
    
16. 
    
17. // lib
    
18. int A[11];
    
19. int cnt, curId;
    
20. int openchest(int x) {
    
21.     if (cnt++ == 5) {
    
22.         throw "Overcall";
    
23.     }
    
24.     int ret = A[x];
    
25.     if (ret == curId) {
    
26.         throw true;
    
27.     }
    
28.     return ret;
    
29. }
    
30. int main() {
    
31.     for (int i=1; i<=10; ++i) A[i] = i;
    
32.     do {
    
33.         int M = getM(A);
    
34.         for (curId=1; curId<=10; ++curId) {
    
35.             cnt = 0;
    
36.             try {
    
37.                 findself(curId, M);
    
38.                 throw "No answer";
    
39.             } catch (const char* desc) {
    
40.                 for (int i=1; i<=10; ++i)
    
41.                     printf("%x ", A[i]);
    
42.                 printf("Person %x %s (M=%d)\n", curId, desc, M);
    
43.             } catch (bool) {}
    
44.         }
    
45.     } while (std::next_permutation(A+1, A+11));
    
46. }

复制代码

我拿着这个库给AI，它们有不用openchest读数组的，有改cnt的，有单纯出错的，好像没一个填对（可能因为回答指数级的我就不追问了）。有一个答出n(n-1)/2+1我也没追了

magicstrawberry

我把人数2n开箱数n改成了n=2，给中学生做了一下。按本贴讨论最优是M=3，显然M=1不可能，问题就是M=2能否证明或证伪。学生目前最好的结果是M=6.