老鼠和毒药问题

昨天在上完课回宿舍的路上，楠哥提起了一道他在某个基础知识竞赛上遇到的题目，我觉得解法很巧妙，分享记录一下。

题目

有 1024 瓶水，其中一瓶有毒，你有 10 只老鼠用于试毒（这里是题目假设，所以别下不了手让老鼠试毒 OVO），老鼠如果喝到毒药，会在一星期后死亡。你有一周时间，如何找出这一瓶毒药？

解法

楠哥说他刚开始想用二分，可是时间上不允许。

也就是把瓶子分两组，每组的瓶子里都倒出一点混合在一起给一只老鼠喝，哪一组的老鼠中毒了，就再把这一组的瓶子分两组，以此类推。但是这样时间上来不及，第一周缩小范围到 512 瓶……第九周 2 瓶，第十周找到。耗时太长。

---

于是他想到了另一种解法：

给每个瓶子标号，给老鼠也标号 0 到 9。

从逻辑上将 10 只老鼠当成 10 位的二进制数。

将瓶子的编号转换为二进制数，比如第 5 号瓶子转换为第 101 号瓶子，将编号第 0 位（即最右边一位）为 1 的水给 0 号老鼠喝，编号第 1 位（即从右边数第二位）为 1 的水给 1 号老鼠喝，以此类推。

也就是说，0 号老鼠喝了 1,11,101,111……这些瓶子的水，1 号老鼠喝了 10,11，110,111……这些瓶子的水，后面的老鼠也是如此。

如果一周时间到，0 号老鼠嗝屁了，那么就说明有毒的水的编号的第 0 位（最右边的位）为 1；如果 1 号老鼠嗝屁了，就说明有毒的水编号的第 1 位是 1……

最后根据 10 只老鼠中毒情况，得到一个 10 位的二进制数，这个数转换为十进制就是毒药的编号。

我觉得这个解法很巧妙。

这让我想起了在听我们学校 ACM 协会的某节课的时候提到的状态压缩，也是使用二进制的，不过我当时没听懂，也就没记下来。

老鼠有 10 只，它们的死活可以表示 2^10 种状态，恰好是 1024 种。