毒酒问题(加强版)

mathe · 发表于 2009-6-9 15:10:18

K6N37.zip (10.16 KB, 下载次数: 4)
得到一个N=37的解.现在的结果是37人解决2111桶酒问题.
附件中每行数字左边18比特,右边19比特.
本来以为还可以得到更好的结果,不过好像是由于我的概率估计公式不够准确,K更大时现在的我的概率公式就完全不准了,所以结果不对.

mathe · 发表于 2009-6-9 15:30:05

wine.zip (16.84 KB, 下载次数: 10)
现在找到了33个囚犯的方案.
附件中分别给出了33~35个囚犯的解决方案.
其中文件中每一行两个整数,前面整数18比特,后面的15~17比特.合起来是33~35比特的数

mathe · 发表于 2009-6-9 17:17:36

对的,第一列是构造值,第二列是随机的(所以看起来都不相同).唯一控制的是0,1产生的概率

mathe · 发表于 2009-6-9 17:40:50

每个第一个数字相同的数会产生14个第二个数(当然后面的程序会淘汰掉部分数据),所以实际上最终结果是对每个第一个数字,对应第二个数字小于14.
这个说的14仅仅对于39个囚徒的情况,而对于其它情况,这个数字可能不同.(这里这个数字对应程序中参数m)

mathe · 发表于 2009-6-10 08:00:06

发现前面的程序有个BUG.其中函数check3没有检查完所有情况,需要修改一下.
修改以后,通过K=7还是找到了33个囚犯的解.
附件中是修改以后的程序和33,34个囚犯的解

wine.zip (12.2 KB, 下载次数: 9)

mathe · 发表于 2009-6-10 09:42:53

这样判断过多了.
程序里面已经枚举了所有的a<=b,a<=c,c<=d的情况,而A,B,C,D枚举了所有的组合
也就是对于任何的(aA,bB),(cC,dD)组合已经穷举完了.
而如你那样修改,会在sa[a]|sa[b]) !=(sa[c]|sa[d])的情况下还要额外要求对应的la不等

mathe · 发表于 2009-6-10 17:40:52

现在将这个模型的期望数目重新推导了一下,得出一个比较准确的公式,然后用计算机计算
的确在N=32时无法超过1000了(只有824),而N=33时期望数目可以达到1262.
所以这个方法33已经是最好的结果了.

#define N 32
#define MAXR 800
double maxr;
double f(double r[4],double x,int n)
{
double rt=0.0;
int i;
for(i=0;i<n;i++){
rt*=x;
rt+=r[n-1-i];
}
return rt;
}
double round(double x)
{
return (double)(int)(x+0.5);
}
#define ERROR 0.0001
void solve3(double r[4],int m[])
{
double dr[3];
double r0=100.0;
double err;
int c;
int gc=0;
dr[0]=r[1];dr[1]=2*r[2];dr[2]=3*r[3];
start:
c=0;
do{
double t=f(r,r0,4);
err=t/f(dr,r0,3);
r0-=err;
c++;
}while(fabs(err)>ERROR&&c<100);
if(c>=100){
r0=(double)rand();
gc++;
if(gc>=100){
m[0]=m[1]=m[2]=-1;
return;
}
goto start;
}
m[0]=(int)round(r0);
dr[2]=r[3];
dr[1]=r[2]-r0*dr[2];
dr[0]=r[1]-r0*dr[1];
double dd=dr[1]*dr[1]-4*dr[0]*dr[2];
if(dd<0.0){
m[1]=m[2]=-1;
}else{
dd=sqrt(dd);
m[1]=(int)round((-dr[1]+dd)/(2*dr[2]));
m[2]=(int)round((-dr[1]-dd)/(2*dr[2]));
}
}
void get_m(int k,double q, int m[3])
{
int L=N-3*k;
double r[4];
double K=k*pow(3.0,(double)(k-2));
double H=1-2*q*q+2*q*q*q;
double Q=1-2*q*q+2*q*q*q*q;
double HL=pow(H,L);
double QL=pow(Q,L);
double S=pow(6.0,k-2);
double R=k*6*S+k*(k-1)/2.0*S*9.0;
r[0]=-K;
r[0]+=HL*K;
r[1]=-3*HL*K;
r[2]=3.0/2.0*HL*K;
r[0]-=3.0/2.0*QL*K;
r[1]+=11.0/2.0*QL*K;
r[2]-=9.0/2.0*QL*K;
r[3]=QL*K;
r[1]+=0.5*QL*K*(K-1);
r[2]-=3.0/2.0*QL*K*(K-1);
r[3]+=QL*K*(K-1);
r[3]+=QL*R*4.0;
solve3(r,m);
}
void test(int k,double q, int m)
{
int L=N-3*k;
double K=k*pow(3.0,(double)(k-2));
double H=1-2*q*q+2*q*q*q;
double Q=1-2*q*q+2*q*q*q*q;
double HL=pow(H,L);
double QL=pow(Q,L);
double dm=m;
double S=pow(6.0,k-2);
double R=k*6*S+k*(k-1)/2.0*S*9.0;
double r=K*dm-K*dm*(dm-1)*(dm-2)/2.0*HL-dm*(dm-1)*(dm-2)*(dm-3)/4.0*K*QL
-K*(K-1)*dm*dm*(dm-1)*(dm-1)/4.0*QL-R*dm*dm*dm*dm*QL;
if(r>=MAXR){
printf("k=%d,q=%f,m=%d,r=%f\n",k,q,m,r);
if(r>maxr)maxr=r;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int k,s;
double q;
for(k=3;k<=8;k++){
for(q=0.6667;q<0.707;q+=0.0001){
int m[3];
get_m(k,q,m);
for(s=0;s<3;s++){
if(m[s]>0&&m[s]<100000){
test(k,q,m[s]);
}
}
}
}
printf("maxr=%f\n",maxr);
return 0;
}

复制代码

mathe · 发表于 2009-6-11 08:37:25

现在写了一个穷举的程序.
对于囚犯数目n不超过5,仅可以识别n+1坛酒(2坛毒酒)
对于n=6,可以识别8坛酒
00
03
0C
15
1A
26
29
30
对于n=7,可以识别10坛酒:
00
03
05
09
12
24
38
48
54
62
对于n=8,至少可以识别13坛酒:
      00
      03
      0C
      15
      26
      38
      49
      52
      60
      8A
      90
      A1
      C4
对于n=9,至少可以识别16坛酒:
000
003
024
038
048
062
00D
016
051
081
098
0C4
10A
110
121
144
n=10,至少20坛酒
000
003
024
038
048
062
00D
016
051
098
0C4
10A
110
181
231
254
28A
2C1
30C
322
n=11,至少可以26坛酒
016
051
098
0C4
10A
110
181
231
254
28A
2C1
30C
322
000
003
00D
024
038
048
062
428
485
4C2
521
540
600
n=12,可以32坛
0C4
10A
110
081
144
221
288
301
431
494
505
602
628
740
000
00D
024
038
048
051
062
092
252
4C2
832
886
909
A04
A41
B02
C18
C80
n=13,可以39坛
010A
0110
0081
0121
0144
0205
0494
0612
0640
0720
0904
0A11
0A20
0B02
0C06
0C08
0C21
0E80
0000
0003
000D
0016
0024
0048
0051
02B0
03C0
08A8
101C
1022
10E0
1188
1242
1280
1401
1428
1444
1812
1901
n=14,至少47坛
0110
0081
0121
0144
0205
0494
0222
0460
0630
0704
0809
0842
0A11
0B02
0C10
0E80
10C0
1212
1301
1408
1421
1890
1940
1A00
0000
0003
000D
0016
0024
0038
0048
0051
0098
010A
1406
2046
2084
2214
22C0
2320
2402
2488
2908
2C20
3009
3010
3060

mathe · 发表于 2009-6-11 08:45:04

这下在Sloane网站中找到位置了:
https://oeis.org/A054961
根据A054961,有
a(9) >= 17. Here is a candidate solution: {011010001 001001010 101000110 100000001 000010110 110010100 010000011 000110000 001001101 010000100 110001000 000101100 100100010 001000000 010100101 111100000 000011001}. - Dmitry Kamenetsky, Jul 17 2017

a(10) >= 22. Here is a candidate solution: {1010110000 1110000000 0010011000 0110100001 1000010101 0011000101 1001000000 0000000010 0001110100 0001001000 0010101010 1100010010 0000010001 0000101101 0100010100 0000011110 0100101000 0001100011 0000100100 0101000001 0101000110 1010000011}. - Dmitry Kamenetsky, Jul 17 2017

a(11) >= 31. Here is a candidate solution: {00101010010 01100101000 00001101100 00001010101 00100110100 00101001001 01000100101 00010101001 10001100001 11010000010 01001001010 00000001111 01111000000 00110010001 10000111000 11100000001 10010000101 00011110000 01000011001 00100100011 01010010100 01000110010 10110100000 10101000100 11001010000 00011000110 10000010011 10000100110 10100001010 00010011010 00000000100}. - Dmitry Kamenetsky, Jul 21 2017

a(12) >= 46. Here is a candidate solution: {011000011000 000000001000 000110100001 111000000010 110100000100 000010110100 010100010010 000011000011 010001001010 000111001000 010000101100 001001100010 100010000110 000001010110 001010101000 010010100010 001001001001 101000100100 000001100101 100011100000 000100011100 001000010011 010100001001 101100001000 100110010000 001110000010 100001001100 010101100000 110001000001 110010001000 011000100001 001100110000 001000001110 000010001101 110000110000 000100100110 000010011010 101001010000 000101010001 001100000101 100000010101 000001111000 101010000001 100101000010 010000000111 010010010001}. - Dmitry Kamenetsky, Jul 21 2017

mathe · 发表于 2009-6-14 21:38:21

上面每一行数都是一个16进制数,其中A,B,C,D,E,F表示16进制中的10~15.
而我们可以将每位16进制数转化为4位二进制数,比如
0  -> 0000
1 ->  0001
2 ->  0010
3 ->  0011
4 ->  0100
...
F ->  1111
于是替换以后,每一行可以表示成一个n位二进制数.其中每一位分别对应那个人是否要喝对应的那坛酒(所在行表示酒)
如上面n=6的情况,那么第一行00,表示第一坛酒6个人都不喝.第二行0C转化为6位二进制数是001100,表示第3和第4个人喝第二坛酒.第三行15即二进制010101,所以第三坛酒是第2,4,6个人喝,等等.

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 毒酒问题(加强版)