这是一个老问题，最近有老同学问起，就在这里提一下吧。
1、囚犯测试毒酒的问题
原始问题是一个简单的情况：
国王有 1000 瓶酒，其中有一瓶酒里混入了毒药。这毒药奇毒无比，微量即会让人在 24 小时内死亡。国王试图用囚犯来试酒，问至少需要多少个囚犯，才能在二十四小时内找到含毒药的酒？
这个题目，有些地方可能觉得用囚犯试毒太不人性，改成了小白鼠，但大意差不多。
很自然，大家会想象它的推广。再替换成数学语言，可以表述为以下形式：
有$N$瓶酒，其中有$K$瓶酒为毒药。问至少需要多少名囚犯，才能在$T$轮试酒中找出所有的毒酒。
每轮测试，都可以让还活着的囚犯喝（微量）其中某些瓶子里的酒，但一旦喝到有毒药的酒，该名囚犯就会在这轮测试中死去。
2、数学背景
上面的问题写成了大家喜闻乐见的形式，很多人把它当做数学趣题来做。但它实质上是数学上的一个研究领域：Group Test，并在实际生活中有很多应用：
A familiar example of group testing involves a string of light bulbs connected in series, where exactly one of the bulbs is known to be broken. The objective is to find the broken bulb using the smallest number of tests (where a test is when some of the bulbs are connected to a power supply). A simple approach is to test each bulb individually. However, when there are a large number of bulbs it would be much more efficient to pool the bulbs into groups. For example, by connecting the first half of the bulbs at once, it can be determined which half the broken bulb is in, ruling out half of the bulbs in just one test.
3、简单下界
这个问题很容易得到一个下界。首先$N$瓶酒中$K$瓶毒药，共有$N \choose K$种不同情况。
而从另外一个角度，如果$M$名囚犯参与$T$轮测试，每名囚犯都只有$T+1$中结局：第一轮中死去、第二轮死去、......、最后一轮中死去和活到最后。这样一共$(T+1)^M$种结局，每种结局最多对应上面一种情况。
因此：
从而得到所需囚犯的下界：
对于文章开头的简单情况，很容易就得到 10 名囚犯的下界。
4、$K=1$ 单瓶毒酒情况
对于单瓶毒酒，上面的下界是可以达到的。
将$N$瓶酒从 0 开始编号，并用$T+1$进制表示，每瓶酒的编号的位数不超过$M=\lceil\log_{T+1}N\rceil$。
在第$t, 1\leq t \leq T$轮，第$i, 1\leq i \leq M$名囚犯喝下面集合里面的酒，即所有$T+1$进制表示的第$i$位为$t$的编号：
对第$i, 1\leq i \leq M$号囚徒，如果在第$t$轮死去，表示毒酒的编号的$T+1$进制的第$i$位为$t$。若该囚徒一直活了下去，表示毒酒的该位为 0。
5、单轮两瓶毒酒的情况
两瓶毒酒的情况要复杂很多。这甚至是一个学术问题。不过网络上也有很多的讨论，有一些很有意思的结果。
单轮测试多瓶毒酒的情况，一般称之为non-adaptive group testing，可以规约到Disjunct matrix。
In a matrix that is d-separable, the Boolean sum of every d columns is unique.
A $ t\times n$ matrix $M$ is d-separable if and only if $ \forall S_{1}\neq S_{2}\subseteq [n]$ where $|S_{1}|,|S_{2}|\leq d$, such that $\bigcup _{j\in S_{1}}M_{j}\neq \bigcup _{i\in S_{2}}M_{i}$
而两瓶毒酒的情况，可进一步地简化为下面的问题：
Maximal number of binary vectors of length n such that the unions (or bitwise ORs) of any 2 distinct vectors are all distinct.
需要注意的是，上面两个等价问题都是从给定多少个囚犯，最多可以测试多少瓶酒的角度。
5.1、学术上的一般性结果
在一篇学术论文里，作者研究了等价问题：
对于$n$个元素的集合，其子集合族
F被称为strong union free，如果任意不同的$A, B, C, F\in F$，都有$A\cup B \neq C \cup D$，以及 $A\cup B\neq A\cup C$。
作者证明了最大的strong union free的子集合族的大小f(n)有上下界：
对应到我们的问题，可以得到对$N$瓶毒酒，所需要的囚犯$g(N)$的上下界：
这里的下界和上面的简单下界差不多，但上界是一个很棒的结果。对于 1000 瓶酒，上界大约是 32 左右。不过论文里构造很复杂，不太容易看出具体的构造细节。
5.2、小范围内求解
这里是个很有意思的网站，提供了该问题的小范围内的最优解记录。值得提一下的是，其中最新一些结果是咱们中国人在一个数学论坛上做出来的。
对于 0 到 9 名囚犯，该网站给出了精确解，即依次最多能测试出 1、2、3、4、5、6、8、10、13、17 瓶酒中的两瓶毒酒。
对于 10 名以上囚犯，还没有精确的解，该网站给出一些下界：
10:22, 11:31, 12:46, 13:55, 14:63, 15:72, 16:91, 17:113, 18:145, 19:182, 20:230, 21:281, 22:359, 23:449, 24:571, 25:690, 26:892, 27:1078
也就是说 27 名囚犯可以测试 1078 瓶酒里的两瓶毒酒。如果只有 1000 瓶或者 1024 瓶酒，也最多需要 27 名囚犯。
5.3、有趣的递推式
上面小范围内得到了很有趣的结果，不过其过程比较暴力，用计算机搜索出来的，得到的答案也没有结构可言。上面同样的数学论坛上提出一种递归构造的方法，很有美感，可以用约 40 个囚犯识别 1000 瓶酒中的 2 瓶毒酒。
在解决问题之前，我们设$f(N)$为$N$瓶酒中至多两瓶毒酒（可能只有一瓶毒酒）的情况下，需要的囚犯的最小数量。
假设$N\leq n_1 \times n_2, n_1\leq n_2$，将$N$瓶酒分成$n_1\times n_2$的矩阵，递归地，用$f(n_1)$个囚犯识别两瓶毒酒所在的行，用$f(n_2)$瓶毒酒识别两瓶毒酒所在的列。这时候我们可以将两瓶毒酒锁定在一个矩阵的两个对角的情况。我们只需要同步地，设计测试区分这些对角情况，这只需要$f(\frac{n_2}{2})$个囚犯。
于是，我们得到递归式：
6、两轮两瓶毒酒的情况
待续。
Q. E. D.
