毒瓶问题

目录：

• 问题
• 解答
• 后记

问题

有 1000 个外观完全相同的瓶子。已知其中恰好有 2 个瓶子含有同一种毒药，其余都是水。毒药有如下性质：任何剂量都会致命；喝下毒药后，小鼠会在大约 1 小时内死亡，且不会超过 1 小时。

现在你有 10 只小鼠。实验按轮进行，每轮持续 1 小时。每一轮开始前，你可以查看此前所有实验结果，然后决定让任意数量仍然活着的小鼠，从任意数量的瓶子中各喝一点。每轮结束时，观察哪些小鼠死亡。已经死亡的小鼠不能再用于后续实验。

如果逐瓶测试当然可行，但会很慢。问题是：

在最坏情况下，至少需要多少轮，才能 100% 确定哪两个瓶子有毒？对应的策略是什么？

思考区

先停一下。读者在继续往下看之前，可以无剧透自己想一想。

解答

1轮和2轮不可能证明

我们需要区分的毒药状态数是

如果只过 1 小时，每只老鼠只有“死/活”两种状态，10 只老鼠最多给出 $2^{10}=1024$ 种结果，不足以区分所有毒瓶对。

如果过 2 小时，每只老鼠有三种最终状态：第 1 小时死、第 2 小时死、或者存活。于是 10 只老鼠最多给出 $3^{10}=59049$ 种结果，仍然小于 $\binom{1000}{2}=499500$。

一个必胜策略必须让不同的毒瓶对产生不同的可观察结果，否则最坏情况下无法确定答案。因此 1 轮和 2 轮都不可能，至少需要 3 轮。

到 3 小时，纯信息量不再排除可行性，因为 $4^{10}>1000^2>\binom{1000}{2}$。不过死掉的老鼠不能继续提供新信息，所以这并不自动给出构造。

4轮的构造

这是我之前想的解答。

4 小时有 $5^{10}$ 种理论状态，看起来应该足够。直觉上可以把最坏情况想成一个“麦克斯韦妖”：它总是在我们喂完之后，选择最能减少后续信息量的死亡模式。因此策略要尽量把两个毒瓶分散成互不干扰的子问题，并且每条分支都能收尾。

一个小工具：单毒瓶编码

如果已知 $n$ 个瓶子里恰好有 1 瓶有毒，手上有 $r$ 只老鼠和 $s$ 轮剩余时间，那么可以区分最多 $(s+1)^r$ 个瓶子。

做法是给每个瓶子一个长度为 $r$ 的码字，每一位取值于

第 $m$ 位为 $q$，表示第 $m$ 只老鼠在剩余第 $q$ 轮喝这个瓶子；第 $m$ 位为 $\ast$，表示这只老鼠永远不喝这个瓶子。最后每只老鼠的死亡时间，或者存活，刚好还原出毒瓶码字。

后面只用到两个特例：

也就是说，4 只老鼠、3 轮可以在 100 瓶中找 1 瓶毒药；3 只老鼠、2 轮可以在 12 瓶中找 1 瓶毒药。

第 1 轮：把 1000 瓶分成 10 个百瓶块

把瓶子分成 $G_1,\ldots,G_{10}$，每组 100 瓶。第 $i$ 只老鼠喝 $G_i$ 中所有瓶子。

1 小时后只有两种情况。

A1：死了两只老鼠。 设死的是第 $i,j$ 只。那两瓶毒药分别在 $G_i$ 和 $G_j$ 中，各有 1 瓶。此时还剩 8 只活鼠，把它们分成两队，每队 4 只。每队用上面 $4^4>100$ 的单毒瓶编码，在剩余 3 轮内解决一个“100 瓶中找 1 瓶”的子问题。总计 4 小时完成。

A2：只死了一只老鼠。 设死的是第 $i$ 只。那两瓶毒药都在同一个百瓶块 $G_i$ 中。此时还剩 9 只活鼠和 3 轮。

第 2 轮：在 A2 中，把 100 瓶压缩到 12 瓶块

把 $G_i$ 分成 9 组 $H_1,\ldots,H_9$，每组至多 12 瓶。为了叙述整齐，可以用第一轮已经确定无毒的瓶子补齐，使每组都是 12 瓶；这些补位瓶不会影响结果。因为

所以 9 只活鼠足够一人测一组。

2 小时后又有两种情况。

B1：死了两只老鼠。 说明两瓶毒药分别在两个已知的 12 瓶组中，各有 1 瓶。此时还剩 7 只活鼠和 2 轮。取两队各 3 只老鼠，用 $3^3=27>12$ 的单毒瓶编码，各自解决一个“12 瓶中找 1 瓶”的子问题；多出来 1 只老鼠不用。总计 4 小时完成。

B2：只死了一只老鼠。 说明两瓶毒药都在同一个 12 瓶组中。此时还剩 8 只活鼠和 2 轮。

第 3 轮：在 B2 中，把 12 瓶分成 6 对

把这个 12 瓶组分成 6 对：

用 6 只活鼠测试，一只老鼠喝一对。

3 小时后仍然只有两种情况。

C1：死了两只老鼠。 说明两瓶毒药分别在两个已知的 2 瓶对中，各有 1 瓶。第 4 轮，对每个 2 瓶对，各用 1 只活鼠测试其中一个瓶子：若死，则测试的那瓶有毒；若不死，则另一瓶有毒。总计 4 小时完成。

C2：只死了一只老鼠。 说明两瓶毒药都在同一个 2 瓶对中。既然总共有且只有两瓶毒药，那么这个 2 瓶对里的两个瓶子就是答案。此时 3 小时已经完成。

综上，每条分支都能在 4 小时内完成。

3轮的构造

这个漂亮的构造来自 ChatGPT 5.5 Pro，使用了45分钟思考得出，我仔细检查了一遍认为是正确的。

直观概览

答案是：最坏情况下正好需要 3 轮。

前面已经说明 2 轮不可能。真正漂亮的地方在于：3 轮居然够。

核心想法是把 10 只小鼠看成一个完全图的 10 个顶点。第一轮不急着精确定位，而是给每个瓶子贴一个“会杀死哪些小鼠”的标签：

• 有些瓶子贴单点标签 ${i}$，放入顶点盒 $V_i$；
• 有些瓶子贴双点标签 ${i,j}$，放入边盒 $E_{ij}$。

具体分配为：

• 每个顶点盒 $V_i$ 放 64 瓶，一共 $10\cdot64=640$ 瓶；
• 每个边盒 $E_{ij}$ 放 8 瓶，一共 $\binom{10}{2}\cdot8=45\cdot8=360$ 瓶。

刚好 $640+360=1000$。

第一轮中，小鼠 $i$ 喝下所有 $V_i$ 里的瓶子，以及所有与 $i$ 相连的边盒 $E_{ij}$ 里的瓶子。于是每个有毒瓶子会杀死它标签里的那些小鼠。因为有两瓶毒药，第一轮死掉的小鼠集合 $U$ 就是两个标签的并集，所以 $\lvert U\rvert$ 只能是 1、2、3、4。剩下两轮只需要根据这四种情况分别收尾。

下面是形式化的证明。

形式证明

引理 1：两个常用编码技巧。

后面会反复用到两个小技巧。

第一，若已知某一组 $N$ 个瓶子里恰好有 1 瓶有毒，用 $r$ 只小鼠在 1 轮内可以区分最多 $2^r$ 个瓶子。做法是给每个瓶子一个 $r$ 位二进制标签，第 $t$ 位为 1 就让第 $t$ 只小鼠喝它。死亡集合就是这瓶毒药的二进制标签。

第二，若已知某一组 $N$ 个瓶子里恰好有 1 瓶有毒，用 $r$ 只小鼠在 2 轮内可以区分最多 $3^r$ 个瓶子。每只小鼠对每个瓶子有三种安排：第 1 个剩余轮次喝、第 2 个剩余轮次喝、或者永远不喝。最终死亡时间给出一个 $r$ 位三进制标签。

有时我们还需要保证“如果毒药在这组里，那么第 1 个剩余轮次一定会死至少一只小鼠”。这时只使用含有至少一个“第 1 个剩余轮次喝”的三进制标签。数量是 $3^r-2^r$。当 $r=4$ 时，$3^4-2^4=65$，足够编码 64 个瓶子。

引理 2：第一轮的图标签构造。

把 10 只小鼠编号为 $1,2,\ldots,10$。

把 1000 个瓶子分成两类盒子：

• 对每个小鼠 $i$，建立顶点盒 $V_i$，内含 64 个瓶子；
• 对每个无序小鼠对 ${i,j}$，建立边盒 $E_{ij}$，内含 8 个瓶子。

瓶子总数为 $10\cdot64+\binom{10}{2}\cdot8=640+360=1000$。

第一轮，让小鼠 $i$ 喝：

• $V_i$ 中的所有瓶子；
• 所有与 $i$ 相邻的边盒 $E_{ij}$ 中的所有瓶子。

如果毒瓶在 $V_i$，它只杀死小鼠 $i$。如果毒瓶在 $E_{ij}$，它杀死小鼠 $i$ 和 $j$。令第一轮死亡的小鼠集合为 $U$。由于有两瓶毒药，$U$ 是两个单点或双点标签的并集，所以 $\lvert U\rvert\in{1,2,3,4}$。

下面分别处理。

情形一：$\lvert U\rvert=1$。

设 $U={i}$。这说明两瓶毒药都在同一个顶点盒 $V_i$ 中。因为只要有一瓶毒药在边盒里，就一定还会杀死另一只小鼠。

此时 $V_i$ 有 64 瓶，剩余 9 只活鼠和 2 轮。

第 2 轮，把 $V_i$ 分成 8 组，每组 8 瓶。用 8 只活鼠分别测试这 8 组。

• 如果死了两只小鼠，说明两瓶毒药分别位于两个已知的 8 瓶组中。第 3 轮用 3 只小鼠二进制编码第一组，用另外 3 只小鼠二进制编码第二组，即可找出两瓶毒药。
• 如果只死了一只小鼠，说明两瓶毒药都在同一个 8 瓶组中。第 3 轮用 8 只小鼠一一测试该组 8 瓶，死掉的两只小鼠对应的就是两瓶毒药。

所以 $\lvert U\rvert=1$ 可在 3 轮内完成。

情形二：$\lvert U\rvert=2$。

设 $U={i,j}$。可能相关的盒子只有 $A=V_i,\;B=V_j,\;C=E_{ij}$。两瓶毒药的形式只能是 $A+B,\;A+C,\;B+C,\;C+C$。

此时剩余 8 只活鼠。第 2 轮把它们分成两队，每队 4 只。

• 第一队在 $A$ 上运行“非空 4 鼠三进制编码”；
• 第二队在 $B$ 上运行同样的编码；
• $C$ 暂时不测。

这里“非空”的意思是：如果毒药在这个 64 瓶盒子里，那么这一队在第 2 轮一定至少死一只。因为可用标签数是 $3^4-2^4=65$，足够覆盖 64 瓶。

第 2 轮后：

• 两队都有人死：形式是 $A+B$。第 3 轮完成两边的三进制编码。
• 只有第一队有人死：形式是 $A+C$。第 3 轮完成 $A$ 的三进制编码，同时用第二队仍活着的 4 只小鼠二进制编码 $C$ 的 8 瓶。
• 只有第二队有人死：对称处理，是 $B+C$。
• 两队都没人死：形式是 $C+C$。第 3 轮用 8 只活鼠一一测试 $C$ 的 8 瓶。

所以 $\lvert U\rvert=2$ 也可完成。

情形三：$\lvert U\rvert=4$。

设第一轮死掉的是 $i,j,k,l$ 四只小鼠。要让四个顶点都出现，两瓶毒药必须分别在两个不相交的边盒里。也就是说，它们对应四个顶点上的一个完美匹配。可能的匹配恰好有三个：$(E_{ij},E_{kl}),\;(E_{ik},E_{jl}),\;(E_{il},E_{jk})$。

每个边盒只有 8 瓶，此时剩余 6 只活鼠。

第 2 轮，把 6 只活鼠分成三队，每队 2 只，一队负责一个可能匹配。对每个匹配，任选其中一个边盒作为“第一盒”。把第一盒中的 8 瓶编号为 $\mathtt{000}$ 到 $\mathtt{111}$。这一队的两只小鼠只测试第一盒的一位信息：一只喝第一位为 0 的瓶子，另一只喝第一位为 1 的瓶子。

真实匹配对应的那一队，一定恰好死一只小鼠；另外两队不会死。这样我们同时知道：

• 哪个匹配是真的；
• 真实匹配中“第一盒”的毒瓶编号的第一位。

第 3 轮还剩 5 只活鼠。用 2 只小鼠确定第一盒毒瓶编号的剩下两位，用 3 只小鼠二进制编码另一个 8 瓶边盒。于是两瓶毒药都被确定。

所以 $\lvert U\rvert=4$ 也可完成。

情形四：$\lvert U\rvert=3$。

这是最麻烦、也最有意思的情况。

设 $U={i,j,k}$。记三个顶点盒为 $A=V_i,\;B=V_j,\;C=V_k$，再记三个边盒为 $X=E_{jk},\;Y=E_{ik},\;Z=E_{ij}$。

注意这个命名是“对边”式的：$X$ 不含 $i$，$Y$ 不含 $j$，$Z$ 不含 $k$。

两瓶毒药的可能形式只有两类：$A+X,\;B+Y,\;C+Z$；或者，两瓶都在边盒中，且分别来自 $X,Y,Z$ 里的两个不同盒子。

此时有 7 只活鼠。把它们分成两队：

• P 队：4 只小鼠；
• Q 队：3 只小鼠。

第 2 轮，P 队对 $A,B,C$ 同时做同一套“非空 4 鼠三进制编码”。也就是说，$A,B,C$ 中相同编号位置的瓶子使用相同的三进制标签。这样做有两个效果：

• 如果毒药在 $A,B,C$ 中某一个顶点盒里，P 队第 2 轮一定会死至少一只小鼠；
• P 队死亡的时间模式，会在第 3 轮结束后给出该顶点盒内的精确瓶号。

Q 队则只负责 $X,Y,Z$ 这 24 个边盒瓶子。给每个瓶子贴一个 3 位二进制标签；某一位是 1，就表示第 2 轮让对应的 Q 队小鼠喝它。

标签分配如下：

如果 Q 队第 2 轮的死亡集合是某个二进制串，例如 $\mathtt{011}$，意思就是第 2、3 只 Q 鼠死了，第 1 只 Q 鼠没死。这个结果等于所有边盒毒瓶标签的按位 OR。

先看有顶点盒毒药的分支。假如 P 队有人死，那么毒药形式一定是 $A+X$、$B+Y$、或 $C+Z$ 之一。Q 队的死亡结果会告诉我们边盒毒瓶属于哪个标签类：

• $\mathtt{000}$ 只可能来自 $X$，于是形式是 $A+X$；
• $\mathtt{001}$ 或 $\mathtt{010}$ 来自 $Y$，于是形式是 $B+Y$；
• $\mathtt{011}$、$\mathtt{100}$、$\mathtt{101}$、$\mathtt{110}$ 来自 $Z$，于是形式是 $C+Z$。

第 3 轮中，P 队继续完成顶点盒的三进制编码，找出顶点盒里的毒瓶。Q 队剩下的小鼠则在已知标签类中二进制细分边盒毒瓶。各标签类大小分别是：

它们都不超过对应剩余 Q 鼠的二进制容量。例如结果 $\mathtt{011}$ 时，Q 队死了 2 只，只剩 1 只，但 $\mathtt{011}$ 标签类只有 2 瓶，刚好可以用 1 只小鼠在第 3 轮区分。

再看 P 队没人死的分支。由于 P 队使用的是非空三进制编码，这说明顶点盒 $A,B,C$ 中没有毒药。因此两瓶毒药都在 $X,Y,Z$ 中，且来自其中两个不同的盒子。

这时 Q 队第 2 轮看到的不是单个标签，而是两个边盒毒瓶标签的按位 OR。关键表格如下：

这张表为什么成立？以最容易出错的 $\mathtt{011}$ 为例。

$\mathtt{011}$ 表示 Q 队第 2、3 只小鼠死亡。因为 P 队没人死，两瓶毒药都在边盒中，所以我们要数的是“两个边盒标签按位 OR 后等于 $\mathtt{011}$”的所有可能瓶对。

可能来源有三种：

• $X+Z$：$X$ 的标签永远是 $\mathtt{000}$，所以 $Z$ 必须是 $\mathtt{011}$。$X$ 有 8 瓶，$Z$ 中 $\mathtt{011}$ 有 2 瓶，贡献 $8\cdot2=16$ 对。
• $Y+Z$：如果 $Y$ 取 $\mathtt{001}$，$Z$ 取 $\mathtt{011}$，OR 是 $\mathtt{011}$。贡献 $4\cdot2=8$ 对。
• $Y+Z$：如果 $Y$ 取 $\mathtt{010}$，$Z$ 取 $\mathtt{011}$，OR 也是 $\mathtt{011}$。贡献 $4\cdot2=8$ 对。

总数是 $16+8+8=32$。此时 Q 队死了 2 只，P 队 4 只全活，所以第 3 轮共有 5 只活鼠。

其他行也是同样的计数：

• $\mathtt{001}$：只能是 $X(\mathtt{000})+Y(\mathtt{001})$，共有 $8\cdot4=32$ 对；
• $\mathtt{010}$：只能是 $X(\mathtt{000})+Y(\mathtt{010})$，共有 $8\cdot4=32$ 对；
• $\mathtt{100}$：只能是 $X(\mathtt{000})+Z(\mathtt{100})$，共有 $8\cdot4=32$ 对；
• $\mathtt{101}$：来自 $X(\mathtt{000})+Z(\mathtt{101})$ 的 $8\cdot1$ 对，以及 $Y(\mathtt{001})+Z(\mathtt{100}\text{ or }\mathtt{101})$ 的 $4\cdot4+4\cdot1$ 对，共 28 对；
• $\mathtt{110}$：对称地也是 28 对；
• $\mathtt{111}$：只能由 $Y(\mathtt{001})+Z(\mathtt{110})$ 或 $Y(\mathtt{010})+Z(\mathtt{101})$ 得到，共 $4\cdot1+4\cdot1=8$ 对。

表格的最后一列说明第 3 轮还剩多少只活鼠。这里不是只靠“候选数不超过 $2^r$”这个粗略计数，而是每一行都有固定的二进制拆法。

对于 $\mathtt{001}$、$\mathtt{010}$、$\mathtt{100}$：

• $\mathtt{001}$ 只可能是 $X(\mathtt{000})+Y(\mathtt{001})$，所以用 3 只小鼠定位 $X$ 中 8 瓶之一，用 2 只小鼠定位 $Y(\mathtt{001})$ 中 4 瓶之一。
• $\mathtt{010}$ 对称处理。
• $\mathtt{100}$ 只可能是 $X(\mathtt{000})+Z(\mathtt{100})$，同样是 $8\cdot4$ 的直积，用 $3+2$ 只小鼠即可。

对于 $\mathtt{011}$，上面的例子已经说明：一定是一瓶在 $Z(\mathtt{011})$ 的 2 瓶中，另一瓶在 $X(\mathtt{000})\cup Y(\mathtt{001})\cup Y(\mathtt{010})$ 的 16 瓶中。用 1 只小鼠区分前者，用 4 只小鼠区分后者，正好 5 只。

对于 $\mathtt{101}$，候选结构是：

这里要稍微小心：第 3 轮的喂法必须在看到第 3 轮结果之前就固定好，不能先观察某只小鼠死没死再决定其余小鼠怎么喂。一个固定编码如下。

令第 3 轮的 5 只活鼠给出 5 位二进制结果。第一位专门标记 $Z(\mathtt{101})$ 那唯一一瓶：这瓶的第一位为 1，其余四位为 0；其他相关瓶子的第一位都为 0。

剩下 4 位这样安排：

• 把 $Y(\mathtt{001})$ 的 4 瓶用前 2 位编号，后 2 位为 0；
• 把 $Z(\mathtt{100})$ 的 4 瓶用后 2 位编号，前 2 位为 0；
• 把 $X(\mathtt{000})$ 的 8 瓶放入不与 $Y(\mathtt{001})$ 重合的四位标签中；这样的标签有 12 个，任选 8 个即可。

于是如果真正形式是 $Y(\mathtt{001})+Z(\mathtt{100})$，OR 结果的后 4 位就是“2 位定位 $Y$，2 位定位 $Z$”。如果真正形式包含 $Z(\mathtt{101})$，第一位会变成 1，而后 4 位则唯一定位 $X(\mathtt{000})\cup Y(\mathtt{001})$ 中的另一瓶。两类结果由第一位分开，互不混淆。

$\mathtt{110}$ 与 $\mathtt{101}$ 完全对称。

对于 $\mathtt{111}$，候选只有：

共 8 对，而第 3 轮还剩 4 只活鼠。可用一位区分是哪一类，再用两位定位对应的 $Y$ 盒中 4 瓶之一，剩下一位不用。

具体地，让 $Z(\mathtt{110})$ 那唯一一瓶只触发第一位，让 $Z(\mathtt{101})$ 那唯一一瓶只触发第二位；再用最后两位分别编号 $Y(\mathtt{001})$ 和 $Y(\mathtt{010})$ 中的 4 瓶。若第一位死亡，就是第一类；若第二位死亡，就是第二类；最后两位给出对应的 $Y$ 瓶编号。

因此在 P 队没人死时，第 3 轮总能把剩下的边盒候选对完全区分开。

至此，$\lvert U\rvert=3$ 也处理完毕。

结论。

两轮不可能，而上面的构造说明三轮一定足够。

后记

之前在小红书上看到的问题。容易证明2轮不可能，3轮有可能但不知道怎么做，4轮可以比较简单的构造出来。Gpt 5.5 Pro 这次给出了3轮的构造，非常厉害！