小白鼠问题
问题描述：有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。问，在一星期时间内，如何用最少的白鼠试验出有毒的那瓶？
错误解法：
1.只要一只白鼠，一瓶瓶喝过去，喝到哪瓶死了，哪瓶有毒。
注意到问题为一星期内最少老鼠，上述方法大概要500个星期。
2.二分法思想。还是犯了上面的问题，只限在一星期内，二分法收敛要logN的时间，也就是logN星期。
正确解法：
根据信息论的知识，1000瓶药水1瓶有毒，那么有1000种不同的情况；每个小老鼠有1死，0活，两种情况。如果有10只小老鼠，我们就能表示2^10=1024种情况，应该能表示1000种不同的药水情况。
于是我们用二进制编码的方法解决上面问题。
为了方便说明，下面举N=6的情况，不妨设4号瓶有毒。
依据上面的理论，我们应该可以用2^3=8,也就是3只小白鼠来表示6种情况，具体如下：
小白鼠： A B C
药水：1 ——》二进制编码：001 1
2 010 2
3 011 3 3
4 100 4
5 101 5 5
6 110 6 6
如上图，小白鼠A，B，C列为一排，某个数的二进制里对应的位数为1，则小白鼠喝这瓶（注意，小白鼠可以喝任意瓶数的药水）。如6的编码为110，则A，B都要喝6，C不要。
上图表示A喝4,5,6号，B喝2,3,6，C喝1,3,5。
如果4号有毒，那么A死1，B活0，C活0，编码为100，也就正好是4.
问题扩展
如果限定为两周，那么情况又如何？
现在小白鼠不单单只有1死，0活两种情况，而是0第一次活第二次活，1第一次死，2第一次活第二次死。也就是3种情况。
同理，我们可以用3^7=2187来模拟。也就是采用3进制编码。
总结：
再扩展到t个星期的问题，t个星期，N 个小白鼠，能表示的瓶数为（t+1）^N.
参考文章：matrix67.com