毒药老鼠问题

####1,毒药与老鼠的问题

问题:1000 个一模一样的瓶子,其中有 999 瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在,给你一星期的时间,如何用最少的老鼠检验出哪个瓶子里有毒药?

首先考虑8个瓶子,用二进制的思想,给瓶子编号,分别为0~7。

  • 000,0
  • 001,1
  • 010,2
  • 011,3
  • 100,4
  • 101,5
  • 110,6
  • 111,7

一共用了三位,每一位代表一个老鼠a,b,c。

  • 给a投编号为4567的水
  • 给b投编号为2367的水
  • 给c投编号为1357的水

结果:一星期后,哪只老鼠死了,相应的那一位就赋值为1。比如ac死了,b没死。结果就为101,第五瓶有毒。

结论:可以用n只老鼠在2^n 瓶药水中检测出一瓶毒药。

####衍生问题:如果有两个星期?
那就用三进制。拿9瓶做例子。

  • 00,0
  • 01,1
  • 02,2
  • 10,3
  • 11,4
  • 12,5
  • 20,6
  • 21,7
  • 22,8

只需要两只老鼠a,b就可以。让a喝掉678,b喝掉258。若一星期后a死了,代表三进制的左起第一位为2,而如果b没死,就代表第二位为0或者1。即:所有死掉的老鼠证明了相应的那一位为2,没死的证明了相应的那一位为0或者1。

结论:可以用n只老鼠在3^n 瓶药水中检测出一瓶毒药。

####衍生问题:如果有k个星期
那可以用k+1进制,因而可以用n只老鼠在(k+1)^n 瓶药水中检测出一瓶毒药。

#####2,重球的问题

有n个球,其中只有一个稍重,其它n-1个重量相同。用无砝码的天秤称量,最少几次能找出这个唯一的重球?

一次称量可以分成三组。假设3个球,那么只需要把其中两个放到天秤两端,如果一样重,那么剩余的是重球,如果天秤倾斜,那么重的那个是重球。由此可得,称量k次,可以分辨出3^k个球。故可以用:以3为底n的对数,向上取整得到次数。