两瓶毒酒问题

Mon, 21st October 2019Edit on Githubcombination poisoned-wine

摘要

网络上广为流传着一个毒酒问题，这个问题也由于牵涉到二进制表示，有时候会被用于程序员面试：

现在有1024瓶红酒，其中有一瓶有剧毒。人喝了之后经过大约七天然后突然毒发而死。 (喝一滴和喝一瓶效果一样，七天内并没有病发的现象) 毒酒跟普通红酒外表、气味完全一样，所以除了用活人试毒外别无他法。现在你手上有一批用来试毒的死囚，每位死囚都按规定能收取安家费一万元(不论最后是否中毒)。你必须于七天后找出哪一瓶是毒酒。问如何设计方案使用最少成本？

通过使用二进制表示可以轻松仅用10个囚犯解决上面这个问题，并且用信息论可以证明这已经是最优结果了。但是如果把上面的问题中的一桶毒酒改为两桶，会出现什么情况呢？同样使用信息论可以得出这时理论下界是19,但是实际上我们能达到的数目却远远大于19。这个问题曾经在百度多个贴吧中出现，后来这个两桶毒酒问题在数学研发论坛被深入讨论, 通过各种不同的方案，从最初构造出使用127个囚犯的方案到最终通过计算机搜索出一种使用27个囚犯解决1090瓶酒的方案

wine

详细内容

手工构造模型

百度贴吧最早有人提出将 $n^2$ 桶酒排列成 $n\times n$ 的方阵，然后让n个囚徒分别喝n行,n个囚徒分别喝n列，再使用 $2n-1$ 个囚徒喝和一条对角线平行的各条线上的酒，就可以得到一种使用 $4n-1$ 个囚徒区分 $n^2$ 桶酒的方案。很多没有经过深思熟虑的同学们都会提议直接用 $2n$ 个囚徒分别去喝n行喝n列来解决这个问题，却没有注意到在最后当某两行与某两列各自有两个囚徒倒下时，我们只能确定这两瓶毒酒是属于这两行与这两列的四个交点中的两个，但是不能完全确定是哪两个。这就是为什么我们需要 $2n-1$ 个额外的囚徒来区分各条对角线。于是这个粗糙的正方形模型对于1000瓶酒，我们需要使用一个 $32\times 32$ 的方阵来解决，最终需要使用 $4\times 32-1=127$ 个囚徒。

随后zed提议改进正方模型为正六边形模型, 在这个模型中，我们可以用 $6a+3$ 个囚徒解决 $3a^2+3a+1$ 瓶酒，从而将囚犯数目降低为 $6\times 18+3=111$ 人。

hexagon

初步数学模型

接着mathe利用果树种植问题中的现成结论得出一种使用79个囚犯的方案。其主要思路就是问题转化为Packing $K_3$ into $K_n$ 的图论问题。于是对于n桶酒，大概需要 $\sqrt{6n}$ 个囚犯。而后来他直接通过在OEIS网站寻找到关于Packing $K_3$ into $K_n$ 的已知最好结果得出了41个囚犯的方案, 并且给出了搜索41个囚徒方案的C代码。

随后shshsh_0510提出了一种方案使得对于充分多的酒瓶数目时的复杂度得到了突破，达到了O(log^2(x)).

通过在网络上找到一篇文章《Union-free Hypergraphs and Probability Theory》(Peter Franki and Zoltan Furedi)可以得出了一种使得 $4n$ 个囚犯解决 $2^n$ 瓶酒的构造方案从而可以使用40个囚犯解决1024桶酒问题。其思路是将长度为n的0,1向量看成 $2^n$ 阶有限域 $F_{2^n}$ 中的数。而记 $I=(1,1,\dots,1)$ 也就是所有n个分量都是1的数。对于4n个囚犯,可以将他们分成4组X,Y,Z,W；其中每组n个囚犯分别做 $F_{2^n}$ 到各组n个囚犯构成集合的一一映射，映射 $g_1:F_{2^n}\to 2^X, g_2: F_{2^n}\to 2^Y, g_3: F_{2^n}\to 2^Z, g_4: F_{2^n}\to 2^W$ 于是集合 $\text{\{}g_1(a)\cup g_2(I-a)\cup g_3(a^3) \cup g_4(I-a^3)| a\in F_{2^n} \text{\}}$ 就满足条件。

通过google找到一篇使用随机构造的算法的文章New Bounds for Union-free Families of Sets，我们竟然可以使用这种碰运气的算法产生33个囚徒的方案和32个囚徒的方案（点击链接获取33个囚徒方案数据的16进制格式表示以及32个囚徒方案数据的16进制格式表示）。

小规模数据穷举

随后mathe写了一个穷举代码穷举了酒瓶数目比较少的情况得出6个囚徒可以识别8坛酒，7个囚徒识别10坛酒等：

对于n=6,可以识别8坛酒

对于n=7,可以识别10坛酒:

对于n=8,至少可以识别13坛酒:

对于n=9,至少可以识别16坛酒:

n=10,至少20坛酒

n=11,至少可以26坛酒

n=12,可以32坛

n=13,可以39坛

n=14,至少47坛

上面每一行数都是一个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位二进制数.其中每一位分别对应那个人是否要喝对应的那坛酒(所在行表示酒) 从而在OEIS上找到了A054961和本问题相对应。

手工模型改进

而后tannis_jin在百度上对正方形模型的对角线确定方法进行了改善,使得确定对角线的数目从2n-1降低到 $\lfloor\frac{n}2\rfloor$ 。

设正方形变长为a

对角线需要：

若a=2k，则需k人。

若a=2k+1，则需k人。（k>1）

举个例子：

a=7

0123321

1012332

2101233

3210123

3321012

2332101

1233210

在这个方案的基础上，继续优化。并且指出识别32行中最多两行不需要32个囚犯而是12个即可，同样识别对角线不需要16个囚犯，9个即可

于是通过构造法也可以达到只需要33给囚犯。

进化模型

随后mathe使用BLISS库淘汰同构结构得出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

以及9人最多只能识别17瓶正好包好两瓶毒酒的方案，而且本质上只有一种方案：

G HI EF AB DEI CFI ADH BCH ACE BDF CDG AFHI BEHI CEGH DFGH AEGI BFGI

并且随后将图的同构代码切换成nauty ,找出10人22瓶，11人31瓶，12人46瓶等方案。

10个人22瓶毒酒的一些本质不同的方案，每个数据表示为16进制数（需要将它们转化为10比特的二进制数)

1 2 300 a0 50 c 2c8 234 1c4 138 285 229 21a 246 18a 115 149 126 99 96 65 6a

11人31瓶:

400 40b 415 452 464 622 506 4b0 48c 618 528 4c1 701 63 a9 125 5c 96 20e 11a 245 149 283 191 268 170 1a2 2a4 342 2d0 1c4

12人46瓶:

800 825 84a 870 c12 898 914 a11 c09 a0c 886 903 c44 928 a22 8c1 451 238 132 d4 426 a9 14c 243 468 264 161 e2 518 614 191 292 48c 60a 505 483 309 18a 285 306 4b0 350 621 542 1a4 2c8

并给出了基本搜索源码，而最终代码采用类似单性繁殖的进化方案进化到使用27个囚犯解决1090瓶酒的方案，并把结果更新到A054961

wine

点击下载进化版本代码和最终数据

最新版本更新在: https://blog.emath.ac.cn/two-poisoned-wine/