在 30 瓶水中找出一瓶有毒的

问题

有 30 瓶水，其中一个瓶子是有毒的，毒性在 n 分钟发作，最少用多少只白鼠可以一次找出那瓶毒水，判断和操作时间不能超过 n 分钟。

分析

30 瓶水，从 0 到 29 编号。

• 1 只 2 种状态：生死

• 2 只白鼠的话可以有 4 种状态：

  • 1 活， 2 活
  • 1 死， 2 死
  • 1 活， 2 死
  • 1 死， 2 活

……

• 5 只白鼠可以组合出 32 种状态，并对应瓶子的编号如下：

00000   0
00001   1
00010   2
00011   3
00100   4
00101   5
00110   6
00111   7
01000   8
01001   9
01010   10
01011   11
01100   12
01101   13
01110   14
01111   15
10000   16
10001   17
10010   18
10011   19
10100   20
10101   21
10110   22
10111   23
11000   24
11001   25
11010   26
11011   27
11100   28
11101   29

求解

• 把白鼠从左到右编号 1 - 5，然后给第 1 只喝它的那一位标记为 1 的瓶里的水，也就是： 16 到 29。
• 2 号白鼠如上喝：8 - 15, 24 - 29 ……

最后观察所有白鼠的状态，对应它们的位置，如果死掉了，就把对应位置标记为 1，如果活着，就是 0。这个 2 进制对应的 10 进制数就是那瓶有毒的水。

因为前题是只有一瓶有毒，所以如果都活着就是 0 号瓶有毒。

如果有多瓶水有毒，就不对瓶子做 0 号编号(因为没有老鼠喝这个瓶子中的水，在其它瓶子有毒的情况下无法判断这个瓶子有没有毒)，还用上面的方法可以找出所有有毒的瓶子。