毒酒

49642

老师刚才发来了方法，想发图但是又发不了，由于是用QQ沟通的，所以我就复制了他的想法过来。
假设用39位囚徒作为元素组成集合
对于39个元素的集合,拆分成15个元素的集合X和24个元素的集合Y
对X中元素每三三分组成5组.并且每组中三个元素分别标上0,1,2三个数
然后如下选择X中的一些子集:
  5组中任意选择1组,将三个元素全部选入,余下4组每组选择一个元素,但是要求所有选择的元素对应数字之和为3的倍数.
这样的子集总共有5乘以3的三次方=135533135个.
然后对于每个这样的子集,随机产生14个Y中子集,要求Y中每个元素被选中的概率为0.3.
这样我们可以构造出共135乘以14=1890个子集.
然后在其中遍历所有三个集合的组合A,B,C，判断是否有A∪B=A∪C，同样A遍历四个集合的组合A,B,C,D，判断是否有A∪B，C∪D。
最后得到的集合还没算，估计在一千八百个左右。

看完我就觉得，不愧是国家一级辅导员。

49872

最少只需要19个死刑犯可以试出毒

49642

上网页搜了一下才发现这题是09年甚至更早的？
网上的答案都十分晦涩难懂【对于我来说】，但我觉得有一个六边形解法很有意思，就是没看懂。

49837

先将1000桶分成两批，一批729，一批271。
将729的那批，先进行试毒，这一环节需要十八个人，分成六个轮次，每个轮次三个人。
第一轮次，每人试232桶，设三个人分别是1a，1b，1c，此时这批酒桶的序号都或者为1a，或者为1b，或者为1c。
第二轮次，三个人试毒，2a试1a的三分之一，1b的三分之一，1c的三分之一。2b试1a的另外三分之一，1b的另外三分之一，1c的另外三分之一。2c测试1a的最后三分之一，1b的最后三分之一，1c的最后三分之一，此时，这批酒桶的序号为，1a2a，1a2b，1a2c，1b2a，1b2b，1b2c，1c2a，1c2b，1c2c。
后面依次 直到六轮后这批酒桶都有自己独特的编号，
再将第二批271的并入第一批次，此时有271桶序号两两重合，再加两个死刑犯，特殊序号XY，将重合的分开，按照死亡序号即可判断出那两桶酒有毒。
最后结论，至少需要18＋2＝20人

48918

程序求解

50085

聚会时间和潜伏期时间是相同的。
也就是说,只能一次性完成任务。
以三维情况采取办法:
把1000个排成10*10*10的立方体。
然后取30个人,每个人喝一层。
这样，通过最后死掉的人就可以确定哪两
桶。
或者是说:
n维排列需要n以(n次根号下(1000 )进位
取整个人)。
比如,四维需要24个人
五维需要20人
六维需要24人
但这样的前提是立方体排列。
如果是长方体排列，可能人数会变少。
由此可以看出目前没有正确答案也没有至少.
根据借鉴大家的观点和推断由此得出个人观点

49962

我死活没想出来，觉得自己真是太笨了……看评论发现这题原来这么难，突然有点小开心

50125

用树状图应该能解决。
1.先把1000酒分为10个分组每组100坛酒，挑10个犯人标记为A组，分别品尝100坛酒。
2.再把每组的100坛酒分为10组，每组10个。再让10个犯人标记为组别B,对应编号1―10,分别对应品尝100组别中10坛酒中的1―10号酒。
3.把100组每组10坛酒再分为10组，1000组，每组一个。让另外10个犯人标记为C组，编号1―10,每人品尝100组分出的对应坛子的酒。每人品尝100坛。
4.最后根据死亡情况推出有毒的俩坛酒。

50097

最少只需要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

50085

10个
根据二进制，2^9＜1024＜2^10