1000桶酒，其中1桶有毒。而一旦吃了，毒性会在1周后发作。问最少需要多少只老鼠可在一周内找出毒酒?

如题。

分析思路： 要用尽可能少的老鼠完成相对大的任务量，要想到把问题进行对数分解。 从而不难想到 2 10 = 1024 2^{10}=1024 210=1024 这个数量关系。

解法一： 二进制编码。

首先对1000桶酒按照1~1000进行二进制编码，因为 2 10 2^{10} 210 = 1024 > 1000，因此需要10位二进制。 故只需要取10只老鼠，每只老鼠只喝其对应位数为1的编号的酒。

然后给10只老鼠按以下编码: 第一只 0000000001 第二只 0000000010 第三只 0000000100 … 第十只 1000000000

结果举例：编号为1000100011的酒是毒酒。 则对应喝酒的只有第一只，第二只，第六只，第十只死亡。

故最后可从哪几只老鼠死亡来判断毒酒的编号是多少。

通用公式： N桶酒，老鼠所能表示的状态数目为M，则需要的老鼠个数为： K = l o g M N K =log_M{N} K=logM​N。

而具体实验的操作方法为： 1.每种状态按照 M 进制进行编码，编码长度为 K 2.每个老鼠分别去拿自身的 M 中状态去实验 N 的 M 进制编码的某一位 3.所以 K 个老鼠，等同于是 K 长度 M 进制的对应的每一位 4.这样试验完后，就确定了每一位上面的数字，找到对应的那种状态就好。

解法二： 二分法。

具体喝法如下： 第一只：1-500 第二只：1-250，501-750 第三只：1-125，251-375，501-625，751-875 … 因为 2 10 2^{10} 210>1000 , 2 9 2^{9} 29100，刚好每只猪剩4种状态，所以两步一共需要10只猪。

2.2 如果仅死一只猪的话，问题变成100桶水里两桶有毒，45min确定哪两桶。 利用1思路，给剩下的猪每只喂12桶水。

2.2.1若死两只猪（此时还剩下7只猪），则问题简化成两个[12桶水一桶有毒]，30min确定。 因为 3 3 3^{3} 33>12，所以刚好将剩下的猪分成33两组。

2.2.2若死一只猪（此时还有八只猪），问题变成12桶水里两桶有毒，30min确定哪两桶。 利用1思路，给剩下的猪每只喂2桶水。

2.2.2.1若死两只猪（此时还有六只猪），问题变成两个[2桶水里一桶有毒]，15min确定哪两桶。

2.2.2.2若死一只猪（此时还有七只猪），问题变成2桶水里两桶有毒，15min确定哪两桶。

故而此方法10只是最多的。

可利用 二进制编码 解法的又一种题目：

500张多米诺骨牌整齐地排成一列，依顺序编号为1、2、3…499、500。第一次拿走所有奇数位置上的骨牌，第二次再从剩余骨牌中拿走所有奇数位置上的骨牌，依此类推。请问最后剩下的一张骨牌的编号是多少？

如题。

所有骨牌都可以用一个9位的二进制编码来标记。

题目中，第1次取牌抽走了所有末位是1的牌，剩余末位为0的牌；第2次抽牌则在第一次剩余的牌中抽走倒数第二位为1的牌…

以此类推，第k次抽牌留下的是形如XXX…X000…0（k个0）的牌。

因此，最后一次抽牌留下的是二进制编码为100000000，即十进制256的牌。