千瓶毒酒：10只老鼠找出那一瓶

题目

有 1000 瓶酒，其中恰好 1 瓶有毒。老鼠喝了毒酒，恰好一周后死亡（更早看不出）。你只有一周时间，且要保证找出毒酒。最少需要几只老鼠？

答案与解析

10 只。 原理是二进制编码：

给每瓶酒编一个 0 到 999 的号，写成 10 位二进制（因为 $2^{10}=1024>1000$）。第 $k$ 只老鼠喝下“所有二进制第 $k$ 位为 1 的酒”的混合样。

一周后，哪只老鼠死了，就把对应位记为 1，活着的记 0。死/活模式拼出的 10 位二进制数，正好就是毒酒的编号。

例如第 3、7、9 只死了，其余活，则毒酒编号 = 第 3、7、9 位为 1 的那个数。唯一确定。

背后的数学

这是信息论的精妙演示：每只老鼠提供 1 比特信息（死/活），$n$ 只共 $2^n$ 种结果，要区分 1000 种可能，需 $2^n\ge1000\Rightarrow n=10$。它和“用最少的称次数从假币中找问题”“格雷码/汉明码检错”同属**分组测试（group testing）**家族——新冠疫情里的混合核酸检测，思路如出一辙。