1,000瓶酒,其中有两瓶有毒。现有10只老鼠,只要尝到毒酒,不管多少,10分钟后死掉。只给10分钟时间,最多可以鉴定多少瓶酒无毒。 最简单的方法是每鼠100瓶,这样至少能鉴定800瓶,也可能900瓶。现在对此加以改进。 每个老鼠的100瓶除自己尝,还拿出90瓶让其他老鼠也尝,即每个老鼠尝190瓶。这样最多会有4只老鼠死掉。为讨论方便,老鼠编为1-10,1号领1-100号酒,…额外分配也类似。1号老鼠得201-210,301-310,…,901-1,000。为叙述方便,把酒10瓶一组放在10×10的方格内。对角线上的酒,只有一个老鼠喝,其余的由两个老鼠喝。根据这种安排,一瓶酒不可能由3个老鼠都喝。 (1)只死1只,假定是1号鼠。有毒的两瓶显然在原先分配的1-100号内。外加的90瓶其他老鼠吃了没事,自己的100瓶内11-100号其他老鼠吃过没事,所以可以鉴定出990瓶。2瓶毒酒均在1-10号。 (2)死2只。不失普遍性,1号和2号死了。300号以后的显然无毒。21-100及121-200也没事。这样可鉴定出960瓶。 (3)死3只,假定1,2,3号死了,可鉴定出910瓶。这儿至少有1瓶毒酒不在对角线。31-100,131-200,231-1,000无毒。 (4)死4只,1 2 3 4。如(1)-(3),可至少鉴定出840瓶。但1瓶酒不可能由3个老鼠喝,所以2瓶毒酒均不在对角线,所以在160瓶内,以下4组亦无毒,1-10,111-120,221-230,331-340。所以最坏情况可鉴定880瓶。 |