6-17 2,314 views
1000瓶药有1瓶有毒，如果小白鼠服用有毒的药，则24小时后死亡。现在需设计一种策略，使用尽可能少的小白鼠，在24小时内找出有毒的药。
思路：
令1000瓶药的序号为1,2,…,999,1000,小白鼠的数目为n。
a(k)表示小白鼠k在24小时后的状态:
a(k) = 1, 小白鼠k存活；a(k) = 0,小白鼠k死亡。
如此，所有n只小白鼠在24小时后的状态为a(1)a(2)…a(k)…a(n-1)a(n),相当于n位2进制数，若n = 10,则2^10 = 1024 > 1000，也就是说，可设计一种策略，使得某一瓶有毒映射一个10位二进制数，这样，需要10只小白鼠就可以在24小时内找出哪一瓶有毒。
具体策略：
令瓶号表示为b(1)b(2)…b(k)…b(9)b(10),对于第k只小白鼠，它尝试b(k) = 0的药。
对于第1只小白鼠，它尝试b(1) = 0的药，即尝试1至512的药。
对于第10只小白鼠，它尝试b(10) = 0的药，即尝试瓶号为偶数的药。
这样，当24小时后，得到10只小白鼠的状态a(1)a(2)…a(k)…a(9)a(10)，且由10个状态组成的10位二进制数即有毒药瓶序号。
举例分析：
若10只小白鼠的状态为1001001001，换算成10进制即585。
进行验证：
a(1) = 1,由于第1只小白鼠尝试1至512的药，且存活，所以有毒药瓶在513至1000之间。
a(2) = 0,由于第2只小白鼠尝试1至256,513至768的药，且死亡，所以有毒药瓶在513至768之间。
a(3) = 0,由于第3只小白苏尝试1至128,257至384,513至640,769至896的药，且死亡，所以有毒药瓶在513至640之间。
a(4) = 1,有毒药瓶在577至640之间。
a(5) = 0,有毒药瓶在577至608之间。
a(6) = 0,有毒药瓶在577至592之间。
a(7) = 1,有毒药瓶在585至592之间。
a(8) = 0,有毒药瓶在585至588之间。
a(9) = 0,有毒药瓶在585至586之间。
a(10) = 1,有毒药瓶是585。