毒酒问题 Poison Wine

毒酒问题---1000桶酒，其中1桶有毒。而一旦吃了，毒性会在1周后发作。问最少需要多少只老鼠可在一周内找出毒酒
如对1000桶按1~1000编码，需要10位二进制数。

因此只需要取10只老鼠，每只老鼠只喝其对应位数为1的编号的酒。
即10只老鼠按以下编码：

第一只 00000 00001
第二只 00000 00010
第三只 00000 00100
第四只 00000 01000
...
第十只 10000 00000

每只老鼠只喝其编码与酒编码做位与运算非0的酒。如果毒酒的编码在某一位为1，则监控该位的老鼠必喝，结果为1.

即把10只老鼠的结果，按位填入一个10位二进制数中，其结果即为毒酒编号。

例如：编号为10001 00011的酒是毒酒。则对应的只有第一只，第二只，第六只，第十只死亡。其对应位数置1，即为10001 00011
http://www.matrix67.com/blog/archives/4361

这个问题的答案也堪称经典：把瓶子从 0 到 999 依次编号，然后全部转换为 10 位二进制数。让第一只老鼠喝掉所有二进制数右起第一位是 1 的瓶子，让第二只老鼠喝掉所有二进制数右起第二位是 1 的瓶子，等等。一星期后，如果第一只老鼠死了，就知道毒药瓶子的二进制编号中，右起第一位是 1 ；如果第二只老鼠没死，就知道毒药瓶子的二进制编号中，右起第二位是 0 ⋯⋯每只老鼠的死活都能确定出 10 位二进制数的其中一位，由此便可知道毒药瓶子的编号了。

    现在，有意思的问题来了：如果你有两个星期的时间（换句话说你可以做两轮实验），为了从 1000 个瓶子中找出毒药，你最少需要几只老鼠？注意，在第一轮实验中死掉的老鼠，就无法继续参与第二次实验了。

    答案：7 只老鼠就足够了。事实上，7 只老鼠足以从 3⁷ = 2187 个瓶子中找出毒药来。首先，把所有瓶子从 0 到 2186 编号，然后全部转换为 7 位三进制数。现在，让第一只老鼠喝掉所有三进制数右起第一位是 2 的瓶子，让第二只老鼠喝掉所有三进制数右起第二位是 2 的瓶子，等等。一星期之后，如果第一只老鼠死了，就知道毒药瓶子的三进制编号中，右起第一位是 2 ；如果第二只老鼠没死，就知道毒药瓶子的三进制编号中，右起第二位不是 2，只可能是 0 或者 1 ⋯⋯也就是说，每只死掉的老鼠都用自己的生命确定出了，三进制编号中自己负责的那一位是 2 ；但每只活着的老鼠都只能确定，它所负责的那一位不是 2 。于是，问题就归约到了只剩一个星期时的情况。在第二轮实验里，让每只活着的老鼠继续自己未完成的任务，喝掉它负责的那一位是 1 的所有瓶子。再过一星期，毒药瓶子的三进制编号便能全部揭晓了。

    类似地，我们可以证明， n 只小白鼠 t 周的时间可以从 (t+1)ⁿ 个瓶子中检验出毒药来。

http://bbs.emath.ac.cn/thread-1511-1-1.html
国王为10天后的生日宴会准备了1000桶酒，不幸的是，其中两桶被下了毒。为了确定两桶毒酒，有人提议用死刑犯试毒。毒的潜伏期为10天。
问:至少需要多少个死刑犯才能确保找出毒酒？方案如何实行？
http://www.zhihu.com/question/19731686
http://www.cnblogs.com/graphics/archive/2010/03/28/1699048.html

1、现有1000个苹果，10个盒子，现在要你将1000个苹果装入10个盒子中，使得用户无论购买多少个苹果（1-1000），都能由若干个盒子拼装而成（卖的时候是整个盒子卖，不能拆盒子的包装）

解法：考虑1， 2， 4， 8这四个数，由这四个数可以组成1-15之间任意一个数，也即1，2， 4 ... 2n 可以组成1-2⁽ⁿ⁺¹⁾-1之间所有的数。所以这十个盒子分别放入

1， 2， 4， 8， 16， 32， 64， 128， 256， 489个苹果，即可组成1-1000内所有的数。