.国王为10天后的生日宴会准备了1000桶酒,不幸的是,其中两桶被下了毒.为了确定两桶毒酒,有人提议用死刑犯试毒.毒的潜伏期为10天.问:至少需要多少个死刑犯才能确保找出毒酒?方案如何实行?

Answer 1

最少只需要19个死刑犯可以试出毒分析如下：首先简单来说我们先假设只有10桶酒,其中有一桶被下了毒,那个需要多少个死刑犯呢?
为了能够充分利用这些死刑犯,每个人肯定需要尝试多桶酒,那么对于死刑犯来说,对于每一瓶酒喝与不喝有两个选择,我们分别记为0和1,那么对于每一个死刑犯来说,就会产生一个10位的二进制数,我们先假设全部不喝,并如下所示把它们横着排列起来：
酒 1 2 3 4 5 6 7 8 9 10
死刑犯1 0 0 0 0 0 x1 0 0 0 0
死刑犯2 0 0 0 0 0 x2 0 0 0 0
死刑犯3 0 0 0 0 0 x3 0 0 0 0
.
死刑犯n 0 0 0 0 0 xn 0 0 0 0
如上所示,如果我们竖起来看的话,每一列的二进制数据就决定了某一桶酒相对应有哪些死刑犯来喝
比如上图中（x1,x2,x3,...,xn）的意思就是说 对于6号桶酒来说,如果xn=0 则死刑犯n不用喝,如果xn=1 则死刑犯n需要喝
所以如果要用最少的死刑犯来找出毒酒的话,就需要10组不同的二进制数（相同没有意义）
那么如果需要10组不同的二进制数,最少需要几位呢?很显然需要4个,简单罗列如下：
酒 1 2 3 4 5 6 7 8 9 10
死刑犯1 0 0 0 0 0 0 0 1 1 1
死刑犯2 0 0 0 1 1 1 1 0 0 0
死刑犯3 0 1 1 0 0 1 1 0 0 1
死刑犯4 1 0 1 0 1 0 1 0 1 0
结果很显然,如果1号桶有毒,那么只有4号死刑犯死了,其他情况大家可以自己试试看
当然4位的二进制后面还有,所以4个死刑犯其实最多能找出出16桶酒中被下了毒的那1桶酒.
好了,现在10桶酒中有2桶被下了毒,那么怎么办呢?
答案很简单,10桶中1桶被下毒则有10中情况
而10桶中2桶被下毒则有10x9/2=45种情况
也就是说,我只要有主够的不同的二进制数来代表至少45种不同情况,就可以找到那被下了毒的2桶酒
所以至少需要6个死刑犯就可以找出10桶中被下了毒的2桶酒
好了大家现在应该很清楚了,这个问题普遍意义上来说可以成为下面的问题
在n桶酒中有m桶酒被下了毒(m n!/((n-m)!m!)
所以原题的答案是 2^x > 1000x999/2 x >= 19