如何在多轮试酒中找出多杯毒酒

作者:, 发表于

最近的一个题目:

500桶酒,其中2桶是毒酒,非常毒,一丁点就必死;48小时后要举行酒会;毒酒喝下去会在之后的0-24小时内毒死人;国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪2桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?

这个题目是一个老题的翻版:

1000桶酒,其中1桶是毒酒,非常毒,一丁点就必死;24小时后要举行酒会;毒酒喝下去会在之后的0-24小时内毒死人;国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪2桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?

所以这个题目可以推广到:

N桶酒,其中M桶是毒酒,非常毒,一丁点就必死。国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯,在k轮测试中,来测试出哪2桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?

其中M=1,k=1是最简单的情况,由于一轮测试,囚犯只有死和不死两种状态,要区分N桶酒的情况,至少需要 \(log_2 N\) 个囚犯。同样,也很容易构造出这个 \(log_2 N\) 的试酒方法。

上面的推断很容易延续到任意k的情况。此时所需囚犯数目为 \(log_{k+1}N\)

但当M>1的情况就复杂多了。假设M=2,同样的逻辑得到下界 \(log_{k+1}\frac{N(N-1}{2}\) 。但还没找到简单的构造方法。

对于最上面的500桶酒2杯毒酒2轮的情况,我这边现在最好的下界是11,上界是13(也有人给出过12的答案,没有细究)。

Q.E.D.


上一篇:如何匿名统计平均收入2012年1月14日
网络的力量太大,这两次把问题放到网上不到半天,这些问题不但被解答,而且连出处都被翻出来了。这让我自己少了很多思考的乐趣。以后不能把问


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。