小白鼠试毒法-向小白鼠致敬
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
参考资料: