面试遇到了，复习下
熵
如果随机变量$X$，它的概率函数为$p(x)$，那么$X$的熵定义为： $H(X)=-\sum_xp(x)\log{p(x)}$
老鼠、毒药
1、有n只一模一样的瓶子。其中n-1瓶是水，1瓶是毒药。老鼠喝了一天死掉，只给一天时间，至少需要k只老鼠，问n和k的关系？
一只老鼠喝水后，有两种状态（生、死），一瓶水是毒药的概率是$1/n$，熵是$\log{n}$，一直老鼠信息量$\log2$，则$n<=2^k$。
给n个瓶子编码，编码为1的喂给所对应老鼠，0..000000、0..000001喂给第1只、0..000010喂给第2只、…、00..1100011喂给第1、2、6、7只等，一共k位编码。 然后得到老鼠状态（生0，死1）$i_1i_2…i_k$，对应的编码则为毒药。
证明：
假设第n个瓶子有毒，n的编码不等于老鼠状态编码，则至少有一位不同，记为$i_j$。
1、第j位为0，但是第j只老鼠死掉，矛盾
2、第j位为1，但是第j只老鼠活着，矛盾
故假设不成立
证毕
球
有1个天平秤和n个球，里面有一个与其他重量不一样，最少称重k次能找出这个球，问n和k的关系？
题1：有一个异常，只需找到这个异常球。
答：
熵是$\log2n$，称重无论什么结果都能找到小球，k次称重信息量最大能达到$k*\log3$，那么
$\log{2n}<=(k*\log{3})$
=>$2n<=3^k$
=>$n<=\frac{3^k}{2}$
n为整数，可以得到$n<=\frac{3^k-1}{2}$。
当k=3，n=12，一种称重方法：
对12个球编码，001，112，220，010，121，202，012，120，201，120，201，012。
第k位为0的和第k位为1的称，如果为0的球重记为0，轻为1，平衡为2。最后得到编码，显而易见如果编码存在12个球中，则为当前编码球且较重；如果不存在编码，则0-1对换，对应编码球，较轻。
题2：不仅需要找到异常球，还需要知道轻还是重。
答：
根据问1答案中，如果称重中有不平衡的情况，能知道轻重；当都平衡，则当加一个非异常球时n+1，异常球必然上称，那么能得到轻或者重，可以得到$n<=\frac{3^k-3}{2}$。
