毒酒问题(加强版)

王守恩

mathe 发表于 2018-2-20 16:31
9个人最多只能识别17瓶正好包好两瓶毒酒的方案，而且本质上只有一种方案：
G HI EF AB DEI CFI ADH BCH AC ...

一，对于囚犯数目n，可以识别2^n坛酒(其中有1坛毒酒)
1，n=1,可以识别2坛酒(其中有1坛毒酒)
       n1=1
2，n=2,可以识别4坛酒(其中有1坛毒酒)
       n1=1+2
       n2=1+3
3，n=3,可以识别8坛酒(其中有1坛毒酒)
       n1=1+2+3+4
       n2=1+2+5+6
       n3=1+3+5+7
4，n=4,可以识别16坛酒(其中有1坛毒酒)
       n1=1+2+3+4+5+ 6 + 7 + 8
       n2=1+2+5+6+9+10+11+12
       n3=1+3+5+6+9+10+13+14
       n4=1+3+5+7+9+11+13+15
5，n=5,可以识别32坛酒(其中有1坛毒酒)
       n1=1+2+3+4+5+ 6 + 7 + 8 + 9 +10+11+12+13+14+15+16
       n2=1+2+3+4+5+ 6 + 7 + 8 +17+18+19+20+21+22+23+24
       n3=1+2+3+4+9+10+11+12+17+18+19+20+25+26+27+28
       n4=1+2+5+6+9+10+13+14+17+18+21+22+25+26+29+30
       n5=1+3+5+7+9+11+13+15+17+19+21+23+25+27+29+31
.............

二，对于囚犯数目n，可以识别n+1坛酒(其中有2坛毒酒)
1，n=2,可以识别3坛酒(其中有2坛毒酒)
       n1=1
       n2=2

2，n=3,可以识别4坛酒(其中有2坛毒酒)
       n1=1
       n2=2
       n3=3

3，n=4,可以识别5坛酒(其中有2坛毒酒)
       n1=1
       n2=2
       n3=3
       n4=4
   
4，n=5,可以识别6坛酒(其中有2坛毒酒)
       n1=1
       n2=2
       n3=3
       n4=4
       n5=5
   
5，n=6,可以识别8坛酒(其中有2坛毒酒)
       n1=1+2+3
       n2=1+4+5
       n3=2+4+6
       n4=3+5+6
       n5=3+4+7      
       n6=2+5+7

6，n=7,可以识别10坛酒(其中有2坛毒酒)
       n1=1+2+3
       n2=1+4+5
       n3=2+4+6
       n4=3+4+7
       n5=2+5+8      
       n6=1+6+9
       n7=7+8+9
   
7，对于n=8,至少可以识别13坛酒(其中有2坛毒酒):
       n1=1+2+ 3 + 4
       n2=1+5+ 6 + 7
       n3=2+5+ 8 + 9
       n4=3+6+ 8 +10
       n5=4+7+ 8 +11      
       n6=1+9+10+11
       n7=4+6+ 9 +12
       n8=2+7+10+12
   
8，对于n=9,至少可以识别16坛酒(其中有2坛毒酒):
       n1=1+ 2 + 3 + 4
       n2=5+ 6 + 7
       n3=1+ 5 + 8 +11+12
       n4=2+11+13+14
       n5=3+ 6 + 8 + 9 +13      
       n6=4+ 6 +10+12+13
       n7=1+ 5 + 9 +10+14
       n8=4+ 9 +11+15
       n9=2+ 7 + 8 +10+15
        
9，n=10,至少20坛酒(其中有2坛毒酒)
       n 1 =1+2+ 3 + 4 + 5 + 6
       n 2 =1+2+ 7 + 8 + 9
       n 3 =3+4+ 7 +11
       n 4 =3+5+10+12+15+16
       n 5 =1+6+15+17+18      
       n 6 =5+6+ 8 +11+12+13+17
       n 7 =2+4+ 9 +11+14+16+17
       n 8 =2+5+10+13+14+18
       n 9 =1+4+ 9 +13+15+19
       n10=3+6+ 7 +12+14+19
.............
mathe！能把122楼翻译成上面的格式吗？
      

mathe

9个人最多只能识别17瓶正好包好两瓶毒酒的方案，而且本质上只有一种方案：
G HI EF AB DEI CFI ADH BCH ACE BDF CDG AFHI BEHI CEGH DFGH AEGI BFGI
但是9个人最多只能识别15瓶包含两瓶或一瓶毒酒的方案，可以有29种不同的识别方案
BEF DFG AEH ACG BCH GHI DEI CFI ABI ADEF ABFG BDGH EFHI CEGI CDHI
EGH DGI FHI ADF BDE CEF BFG AEI CDH ADGH BEHI CFGI ABFI BCDG ACEH
EHI FGH DGI ADE BEF CDF ABH ACI BCG AEFI BDFH CDEG ADGH BEGI CFHI
GHI DEI BFG CFH CDG BEH ADF AEG BCI EFGI BDFH CDEH AFGH ABDI ACEI
AH BG EF CI DI GHI EGH CFG DFH AFI BFI ADG BCH ACE BDE
AH BG EG DH CI FI GHI CDG CEH AEI BDI AFG BFH ABC DEF
CG BH EF AI DI FGI AGH DFH EGH CHI BDG ABF ACF BEI CDE
CH DG EF AI BI BGH AFG AEH ACD BCF BDE CGI DHI EGI FHI
CI DE FGH BGI AFI ADG BDH BCF AEH DFHI EFGI CDFG CEGH ABCH ABEI
EH ABD DFG CDI BGI CEF AEI ACH FHI ABCF BEFG DEGI AFGH BDHI CGHI
EH ADF CFG BFI ACI BEG DEI BDH GHI ABGI ACEF DEFG CDGH AFHI BCHI
EH DI AGI BFH CFG AEF BDG ACH BCI FGHI DEFG CDFH CEGI ABDH ABEI
EH FG BC DI AI BFH CEG DEF BDG CDH GHI BEI CFI AEG AFH
EI FH DG AH BI CG EGH FGI DHI ABG ACI BCH ADE BDF CEF
FG AH CH DI BE DGH AGI CFI BHI EFH EGI ADF ABF BCG CDE
FI GH CD AE BE CGI DFH AFG BHI EFH EGI ACH ADI BCF BDG
GH AC BD EI FI CFG AEH BFH DEG BCE ADF AGI BGI CHI DHI
GH BE CF DI AI BFH CEG DEF BDG CDH FGI EHI BCI AEG AFH
GH BE CF DI AI BFH CEG DFG DEH BCD EFI BGI CHI AEG AFH
GH EFG DFH ADG AEH CDI BEI ABDF ACFG BCEF DEHI BDGI CEGI AFHI BCHI
GH FI CF AD BE EFG DFH DGI EHI AHI BGI ACG BCH ABF CDE
HI AB EGH DGI ADH BEI AEF BDF CDE AFGI BFGH CDFH CEFI ACGH BCGI
HI ACEH ABDI BDEH CDEI BCFH ACFI BEFI ADFH BCGI ABGH CDGH AEGI EFGH DFGI
HI AG BF CH DE AFI BGI DGI EFI CFG DFH EGH ABH ACD BCE
HI CF BG AF DE FGI EFH DGH AGH BDF CEG BCH CDI ABI AEI
HI CG DF AB BE CFI DGH AFG BGH BFI EFH EGI ACH ADI CDE
HI CG DF EI AB FGI CFH DGH AGH BFH AEF BEG ACI BDI CDE
HI DE CFG AEI BDH ADG BEF ACH BCI EFGH DFGI ABFH ABGI CDFH CEGI
HI DG AF CF BE FGH CGI DFI BFI EGH ADH ABG BCH AEI CDE
tannis_jin曾经在百度数学吧猜测两瓶毒酒的最优方案是否总可以有某瓶酒没人喝的方案，9人17瓶酒的结论明确给出了反例。
本搜索对应的程序还比较简陋，首先里面使用bliss库对图进行标准化，但是发现bliss库有内存泄漏，于是再对大量图反复进行标准化时会导致最后内存不够用，
于是只好另外开了一个进程专门做标准化工作，而每工作一段时间重启这个进程。
但是程序运算过程还会产生大量重复数据，为了实现方便，直接调用外部命令sort对数据进行排序，结果对其中产生一个最大达到20g左右的文件进行排序就要花数小时，所以最终花费一天多才处理完9个人的情况。

王守恩

mathe 发表于 2018-2-18 14:46
在人数比较少时，两瓶毒酒问题的搜索算法竟然可以和果树问题非常类似。
双方问题最关键的都是搜索过程会出 ...

弱弱地问一个与本题关系不大的问题：
1人能识别出包含一瓶毒酒的2瓶酒，
2人能识别出包含一瓶毒酒的4瓶酒，
3人能识别出包含一瓶毒酒的8瓶酒，
4人能识别出包含一瓶毒酒的16瓶酒，
5人能识别出包含一瓶毒酒的32瓶酒，
6人能识别出包含一瓶毒酒的64瓶酒，

mathe

在人数比较少时，两瓶毒酒问题的搜索算法竟然可以和果树问题非常类似。
双方问题最关键的都是搜索过程会出现大量同构的树，如果不过滤掉这些同构的树会导致大量重复搜索
所以我采用果树问题中类似算法，采用bliss库来过滤同构的树，得出8个人的确只能最多验证13瓶正好包含两瓶毒酒情况，其中有两种不同的验证方法。
不过输出记号和本贴的其它部分不同，采用类似果树问题中方法，分别用字母A,B,C,D等代表第0，1，2，3比特是1（也就是字母出现对应比特为1，不出现，对应比特为0),而特殊的，所以比特都是0的情况用当个字母O代替，那么8个验证13瓶本质上只有两组解:
G H BD AF CE ABC DEF AEG BFG CDG ADH BEH CFH
O BD AF CE GH ABC DEF AEG BFG CDG ADH BEH CFH
其中第二种方案去掉O,对应8个人验证12瓶包含一瓶或两瓶毒酒的情况

mathe

毒酒滴冻鸭 发表于 2014-11-20 16:40
请问64桶酒，其中两瓶有毒，16人能试出来吗？我只能想到17人的解法。。。

另外16桶酒，最少应该确定是9 ...

16 人可以识别出正好包含两瓶毒酒的67瓶酒，这是用计算机随机搜索找到的
288 9040 7008 9490 4270 1220 2401 805 c201 1449 a810 c836 395 a08e 5920 64 d21 4560 820 81 1018 90a 8402 c4a4 d012 1550 a06 4290 821a 22c4 1380 4848 f40 20a2 c150 a211 8644 7804 a106 4063 8882 29 3803 2017 2152 c302 4328 2430 4411 6c40 3980 6622 1406 3045 2168 8c0 9c08 e009 3214 46a 400e 584 61c0 c52 d14 50c2 a224

ahyyz2008

好贴，涨姿势了，这么牛逼的解法，我还真没见过，佩服众位大神

毒酒滴冻鸭

以下是用三人确定4x13矩阵对角线的系统：

0 000 123 123 123
0 123 000 231 312
0 231 312 000 231
0 312 231 312 000

建构方法看似很简单但是很容易触礁，如果想照板煮碗套用到5x21或6x31的话会死得很难看。。。

mathe

两瓶毒酒只能在四桶中对角出现，所以73#的方案没有问题

mathe

7楼的方法可以在3倍的h(37)个人识别1028桶，估计h(37)=13,如果这样得出39人方案，不知道推广到三维会如何，应该可以考虑正八面体结构

mathe

现在感觉73#的方案有问题，以110#中例子，如果是第一行第三行，第二列和最后一列，得到四个交点有三个分在同一组，所以无法区分，有问题