101囚问题
100张纸条分别写着1-100，乱序放入100个箱子。101个人，分别编号0-100。0号可以看到每个箱子里的纸条，并公开一个1到M的整数。随后1-100号分别可以依次打开50个箱子，试图找到自己的编号。确定策略后除了一个整数就没有其他交流形式，也不能看到别人开了什么箱子。问：要使得必然每个人能找到自己的编号，M至少要是多少？ 小白解法：用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
高手解法、大师解法、大神解法、上帝解法 会是怎样的？请回贴告知。 如果允许开箱人根据箱中数字调整策略的话，有一个思路是，第k个人首先打开第k个箱子，如果箱子里写着n，则下一步打开第n个箱子，以此类推直到用完次数。如果每个链路的圈长不超过50的话，指挥员无需做任何事。但是最坏情况下指挥员发现链路长为100，如果用这个方法，需要告知每个人进入链路的位置（50成功50失败），每人分配1个bit信息的话，M高达2^100。期待楼下改进:lol 新手解法：用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大概有多大呢？占比是百分之几？
还能继续优化吗？ 小白解法：用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,.....。 大师解法：用M传递一个交换，可证前51个箱子里必存在1个交换，使得交换后，所有的循环节长度都<=50，M=C(51,2)=1275 一个非构造的nlogn做法：
发送1表示不做任意交换就没有大循环节。这种情况占比略大于1/e[来源请求]。
去掉一些状态后，由于叠加一个随机排列后，没有大循环节的占比大于1/e，因此存在一个排列使得占比大于1/e。发生2表示这种情况。
以此类推，每个数字可以排除常数比例的排列。由于一共有n!种排列，最多需要log(n!)=nlogn个数字来表达
（这里log表示底数不确定的对数） 附：测试库。#include <stdio.h>
#include <algorithm>
int openchest(int);
int getM(const int* A) {
// TODO
// states stored in A
return 1;
}
void findself(int id, int M) {
// TODO
// Call `openchest`
openchest(1);
}
// lib
int A;
int cnt, curId;
int openchest(int x) {
if (cnt++ == 5) {
throw "Overcall";
}
int ret = A;
if (ret == curId) {
throw true;
}
return ret;
}
int main() {
for (int i=1; i<=10; ++i) A = i;
do {
int M = getM(A);
for (curId=1; curId<=10; ++curId) {
cnt = 0;
try {
findself(curId, M);
throw "No answer";
} catch (const char* desc) {
for (int i=1; i<=10; ++i)
printf("%x ", A);
printf("Person %x %s (M=%d)\n", curId, desc, M);
} catch (bool) {}
}
} while (std::next_permutation(A+1, A+11));
}我拿着这个库给AI，它们有不用openchest读数组的，有改cnt的，有单纯出错的，好像没一个填对（可能因为回答指数级的我就不追问了）。有一个答出n(n-1)/2+1我也没追了 我把人数2n开箱数n改成了n=2，给中学生做了一下。按本贴讨论最优是M=3，显然M=1不可能，问题就是M=2能否证明或证伪。学生目前最好的结果是M=6.
页:
[1]