小白鼠试毒法-向小白鼠致敬

小白鼠试毒法

向小白鼠致敬😂

1000瓶药水,1瓶有毒药,服用后一小时毒发,毒药可以无限稀释,那么一小时内用几只小白鼠能够找出毒药?

一只老鼠的状态是2种生或死,这里可以看做bit位,而1000瓶药水有1000种情况,显然我们可以使用2^10 = 1024>1000 来描述这1000种可能,而2进制数的唯一性可以唯一确定一种情况。

用信息熵来计算,1000个瓶子之中有1个有毒药,包含的信息熵为log2(1000)< log2(1024)=10bit。每个老鼠有死和活两种可能,故一只的信息量是log2(2)=1bit

10只小白鼠可以表示为10bit。将1000瓶药水表示为长度为10的二进制数:

老鼠10 老鼠9 老鼠8 老鼠7 老鼠6 老鼠5 老鼠4 老鼠3 老鼠2 老鼠1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 1
1 1 1 1 1 0 1 0 0 0

第1号小白鼠喝 xxxxx xxxx1的药,第2号小白鼠喝xxxxx xxx1x的药,第3号小白鼠喝 xxxxx xx1xx的药,… 第10号小白鼠喝 1xxxx xxxxx的药(x表示0/1)。

举个例子,如果最后的毒药的编号是10010 11001,则容易知道死的小白鼠是1号,4号,5号,7号,10号,其他小白鼠没死。(除了1024外的毒药编号同情况)如果最后没有小白鼠死亡,则容易想到1024号是毒药。

变种1

如果可以测两轮,那么可以测多少瓶水中的一瓶毒药?

首先是第一轮死掉的小鼠不能被replace的情况,小鼠有三种状态,第一轮死,第二轮死,和两轮都没死,那么三种状态可以类比为3进制,小鼠的量程为3^10即59049瓶。对不能replace的N轮,量程为(N+1)^10

如果第一轮死掉小鼠可以被replace,显然一轮最多能描述2^10种状态。N轮可以确定2^(10N)种状态。实现方法类似变种3的思想,通过剪枝实现。

变种2

如果1000瓶里有2瓶毒药,需要多少只小鼠?

1000瓶里1瓶毒药有1000种可能性,而1000瓶2瓶毒药则有C(1000,2),即499500种可能性,那么2^18<499500<2^19。需要19只小鼠。

变体3

有16瓶水1瓶有毒,一轮时间,用多少只小白鼠能测出14瓶无毒的水?

将16瓶药水用二进制XXXX表示,取3只小白鼠来测,测出的状态为XXX。那么毒在XXX0或XXX1中,剩下14瓶无毒。

把XXX0和XXX1看做是一种情况的。16种情况就变为了16/2种情况。

3只小白鼠:

  • 0000=0
  • 0001=1
  • 0010=2
  • 0011=3
  • 0100=4
  • 0101=5
  • 0110=6
  • 0111=7
  • 1000=8
  • 1001=9
  • 1010=10
  • 1011=11
  • 1100=12
  • 1101=13
  • 1110=14
  • 1111=15

参考资料:

  • https://zhuanlan.zhihu.com/p/24375080
-------------本文结束感谢您的阅读-------------
坚持分享,您的支持将鼓励我继续创作!
0%