1000瓶水问题的证明(数学归纳法) 本帖最后由 XINYONGHUCSDN 于 2010-05-04 17:35:58 编辑 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 C(N , 0) + C(N , 1) + ... +C(N , N) >= 1000;1 + N + N(N-1)/2 + ... +1 >= 1000;==> 2^N >= 1000;==>N >= 10;故最少是 10 只。 貌似很难,不是说黄金分割在实际环境中可能效率更高吗。而且,我觉得lz题目有问题。只有n=1的时候,才能在24小时得出答案。假如lz无须证明24小时内得出答案的话,那么最小的答案就永远是1,用时间复杂度换空间复杂度。每天喝1瓶,等24小时。 假如有N只老鼠,那么24小时后,每只老鼠的状态都可以分为 死/活 2种,总共会有2的N次方种死法。每种死法对应一瓶水,就可以检测出2的N次方瓶水。如果瓶子数量大于这个值的话,就必然有2个瓶子或多个瓶子有毒的结果是同样的,检测不出来。10只老鼠可以检测出1024瓶水。9只老鼠是512只。所以说10只老鼠是可以查出1000瓶水的最小值。具体每只老鼠该怎么喝水,就有N多种喝法了。最简单的是按2进制位数去算。这样任何一瓶水有毒,24小时候,他的2进制位数为1的老鼠都会死。为0的都活着。 数学归纳法有问题b)的k只老鼠只能要么检测P1,要么检测P2,而要等a)中的老鼠死后才能知道毒在P1或P2,然后再用b)的k只老鼠去检测P1或P2,这样显然超出24小时了,如果a)和b)同时进行,那是没法判断的比如,假设毒在P1,a)的1只全喝了P1,b)的k只检测P2,那样是没法知道结果的该题的思路是,老鼠有生和死两种状态,所以n只老鼠可以有2^n种状态,如果老鼠的状态大于x瓶水(其实是1瓶有的水在x个位置的排列的状态,p(x,1)=x,有x种排列状态),那么就可以用n只老鼠检测出哪瓶水有毒。所以只要取老鼠的状态的最小值即可,即min(2^n)>x注意这里是大于,等于也不行比如,2只老鼠,4瓶水,是没法判断的 假设2只老鼠4瓶水老鼠A B 水 1 2 3 4A老鼠喝 1 3 B老鼠喝 2 3结果------------------------------> 如果A死B没死 那么1有毒 如果A死B死 那么3有毒 如果A没死B死 那么2有毒 如果AB都没死 那么4有毒 不过我同意15楼对LZ证明的分析,LZ的证明是有问题的.我觉得不应该是这样去证. k只老鼠检测P1,同时k只老鼠也可以检测P2,二者是不相关的。因为P1或P2中有一个是全无毒的,也就是说老鼠尝了无毒这组瓶后不会对另一组的检测有任何干扰和影响,所以不会影响结果的准确性。 为什么说很重要,其实是你问题里面有:“须要n只小白鼠就能在24小时时鉴别出那瓶水有毒”如果中毒时间无限趋近于0,则每只老鼠喝了那瓶毒水就死了,那么无论n=?,1只老鼠足矣。如果中毒时间不是无穷小,则对于n足够大时,无法满足24小时以内鉴别完的条件。也就是说,无论中毒时间为何,你的证明都是错误的。所以,你可能需要考虑把24小时的限制去掉。但是,一旦去掉这个限制,那么,也可以得出“只要1只老鼠就可以鉴别那瓶水有毒”的结论。 整个操作是,先根据喂药策略对老鼠进行喂药,喂药完毕后,静待24小时,24小时后根据老鼠的死亡情况来判断哪瓶药有毒。通过你的回复,可以看出,你的理解是喂药->查看结果->再喂药->再查看结果……所以我们讨论的不是同一个问题。 又忽略了,LZ的证明没问题,收回我的分析a)和b)同时进行,比如a)的1只全喝P1,b)的k只同时喝P1和P2,如果a)的1只没死,则毒在P2,由2)知b)的k只能检测出P2,所以命题成立,反之,a)死了,则毒在P1,由2)也知b)的k只能检测出P1,所以命题成立 阁下的证明意思是:N个老鼠,每个老鼠中毒与不中毒的情况组合数是2^N个,因此对于M瓶水,至少需要ROUND(lg2(M))个老鼠。但是是否需要一个证明,将两个问题等价起来啊?或者说对于N个老鼠的生与死的情况,只能表示2^N种信息。但能否或如何证明这里面一个信息必须与某一瓶水是一一对应的。 理解了,我理解成binary search了 顶ls的,本来也想回来发这个的。每个老鼠只能提供生死两种信息,也就是说,每只老鼠只能提供1Bit信息。接下来,就是数的二进制表示了。 数据库连接不报错,却没得到数据??? 求教一个在JPanel面板上动态显示当前时间的问题,请高手帮下忙! 在网上看见一个计算器的代码,结果有些不会,特开重分贴.顶着有分.特开重分贴.顶着有分. hashset的遍历为何没有按照输入的顺序 加操作是原子操作吗 java中怎样定义字符串/整型数组,并赋值? Java->EXE?use JBuilder ,how? 大家考完SCJP后都做些什么呢? 请问UDP协议不能在同一个IP地址上通过两个端口完成双向传输吗? 卡在这了,一直运行不了,到底哪里出现问题了,老铁们支支招呗? 为什么图片总是加载不上去? ##各位熟人我来也,帮忙看看我的问题
1 + N + N(N-1)/2 + ... +1 >= 1000;
==>
2^N >= 1000;
==>
N >= 10;
故最少是 10 只。
具体每只老鼠该怎么喝水,就有N多种喝法了。最简单的是按2进制位数去算。这样任何一瓶水有毒,24小时候,他的2进制位数为1的老鼠都会死。为0的都活着。
比如,假设毒在P1,a)的1只全喝了P1,b)的k只检测P2,那样是没法知道结果的该题的思路是,老鼠有生和死两种状态,所以n只老鼠可以有2^n种状态,如果老鼠的状态大于x瓶水(其实是1瓶有的水在x个位置的排列的状态,p(x,1)=x,有x种排列状态),那么就可以用n只老鼠检测出哪瓶水有毒。所以只要取老鼠的状态的最小值即可,即min(2^n)>x
注意这里是大于,等于也不行
比如,2只老鼠,4瓶水,是没法判断的
假设2只老鼠4瓶水
老鼠A B 水 1 2 3 4
A老鼠喝 1 3
B老鼠喝 2 3
结果------------------------------>
如果A死B没死 那么1有毒
如果A死B死 那么3有毒
如果A没死B死 那么2有毒
如果AB都没死 那么4有毒
如果中毒时间不是无穷小,则对于n足够大时,无法满足24小时以内鉴别完的条件。也就是说,无论中毒时间为何,你的证明都是错误的。所以,你可能需要考虑把24小时的限制去掉。但是,一旦去掉这个限制,那么,也可以得出“只要1只老鼠就可以鉴别那瓶水有毒”的结论。
所以我们讨论的不是同一个问题。
又忽略了,LZ的证明没问题,收回我的分析
a)和b)同时进行,比如a)的1只全喝P1,b)的k只同时喝P1和P2,如果a)的1只没死,则毒在P2,由2)知b)的k只能检测出P2,所以命题成立,反之,a)死了,则毒在P1,由2)也知b)的k只能检测出P1,所以命题成立