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=logMN。
而具体实验的操作方法为：
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}
29<1000
所以最少需要10只老鼠。
触类旁通：
初级版问题——每只只能实验一次
即上题。因为每只老鼠只能实验一次，所以，每只老鼠身上有两种状态一死亡或者存活，而酒中有毒的信息总量为1000，即每桶酒都有可能有毒。
所以需要的编码长度为：
l
o
g
2
1000
log_ 2 {1000}
log21000 向上取整得到10
中级版问题一一每只可以实验多次
10000桶酒，其中1桶是毒酒；48小时后要举行酒会；毒酒喝下去会在之后的第23-24小时内毒死人（时间确定）；国王决定用囚犯来试酒，不介意囚犯死多少，只要求用最少的囚犯来测试出哪一桶是毒酒，问最少需要多少囚犯才能保证找出毒酒？
根据题目要求，对于每个囚犯，是可以实验24次的，即第0小时喝，然后第1小时再喝，。。。如果第K小时死亡，则是因为第K-24（上取整）小数喝的酒导致的。
这样的话，每个人就含有了25个状态，即24小时分别每个小时死亡，外加最后没有死。
所以需要的囚犯数为
l
o
g
25
10000
log_{25}{10000}
log2510000 = 3， 即将10000桶酒按照25进制编码进行编码，是一个三位数长度的25进制数。
然后三个人分别第i小时去喝对应位数上编码为i的所有酒，最后就能确定下来具体喝哪一桶酒。
类似的题：
1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？
解：每头猪有5种状态，所以5头猪即可完成编码。
高级问题—-不止一桶有毒
不止一桶有毒的情况下，其实非常地复杂。
1000桶水中两桶有毒，猪喝毒水后会在15分钟内死去，想用一个小时找到毒水，至少需要几只猪？如何实现？
因为有两桶有毒，所以信息量为：
N
=
C
1000
2
N = C _ {1000}^{2}
N=C10002种情况。
每只猪身上有5种状态，所以最低有：
l
o
g
5
N
=
9
log_{5}{N}= 9
log5N=9 。
但是这个只是理论下界，因为猪死亡是不能够区分出，是被一桶毒水毒死的，还是两桶毒水。
假设猪死亡的状态可以区分出来/或者两种毒水需要混合才能有毒性的话，那么做法是，将这1000桶毒水两两混合，一共
N
=
C
1000
2
N = C _ {1000}^{2}
N=C10002 种组合，然后将这些组合按照5进制进行编码。然后9只猪就可以区分出来了。
而对于这道题来说，不止一桶水有毒的情况，就是先用交叉法再用进制法。
即10只猪每只喝100桶，然后按照死一只还是死两只进行分开讨论。
具体如下：
1.给每只猪喂对应个位数编号的水，这样第一个15分钟后肯定最多死两只猪。
2.1.如果死了两只猪的话，则同时确定了两个[100桶水里有一桶水有毒]。问题简化成两个[100桶水里有一桶水有毒]，45min确定哪两桶。
将剩下八只猪平均分开，思考可以用几进制的四位数至少可以表示到100，分别确定这桶水。因为
4
4
4^{4}
44>100，刚好每只猪剩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的牌。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
