|
公众号：数学加 优惠不掺假，买课7折啦！3月15日截至24点，数学加小升初强化班，2017中考冲刺强化班（上、下）限时7折优惠啦！学霸折扣、课程连报优惠同享哦，详情请询4000600789. 小编有话说 烧脑子的趣味数学题：国王与毒酒。这个故事的内容是这样的：500桶酒，其中1桶是毒酒；48小时后要举行酒会；毒酒喝下去会在之后的第23-24小时内毒死人；国王决定用囚犯来试酒，不介意囚犯死多少，只要求用最少的囚犯来测试出哪一桶是毒酒，问最少需要多少囚犯才能保证找出毒酒？请诸位自序们为乌有国王出个主意！ 分析与解答 答案：只需要2名囚犯就可以保证找出毒酒。 这是一道很有意思的题目。 首先我们看题目说囚犯喝下毒酒后23~24小时毒发，自然就会想，23人够吗？显然23人是可以的（每人喝22种酒，在23~24小时内毒死一人，确定毒酒在这22种之内，剩下22人每人喝一种，在46~48小时内就可以确定毒酒），问题是23人是最少的人数吗？ 题友们可能会联想到之前我们发过一道类似的题，用老鼠试毒药（公众号中回复 老鼠与毒药 查看），背后的思路是二进制编码，所以那题用10只老鼠就可以在1000瓶水中找出1瓶毒药（因为21o=1024＞1000）。那么本题只需从500桶酒中找出1桶毒酒，理应用更少的人。 根据上题的思路，9人就可以找出毒酒（用二进制编码，29=512＞500），问题是9人是最少的人数吗？（具体的方法可在公众号中回复 老鼠与毒药 参考该期问题的方法） 再读一下题目，发现本题和老鼠试毒药题除了测试样本数量不同以外，还有中毒时间的不同。本题的中毒时间为23~24小时，而共有48小时可以测试，也就是说可以测试两轮，于是测试人数可以减少到8人（2^8×2=512＞500），那么8人就是最少的人数了吗？ 进一步思考，我们发现，可以把500桶酒分成32组（25=32），每组15~16桶（24=16），第一轮5个人在23~24小时判断出毒酒在哪一组（25=32），毒死一人，第二轮剩下的4人在46~48小时判断出毒酒是哪一桶（24=16）。这样看来，5人应该是最少的测试人数了。 以上的方法背后的思路都是二进制，有没有其他思路呢？本题的死亡时间非常精确，在23~24小时之间，又有什么用处呢？下面请看题友会微信群里（回复 题友会 可查看加入方法）的大神们的奇思妙解：“两个囚犯就够了！把500桶酒摆成23×23的矩阵（实际上23×22=506已经超过500）。囚犯A每隔一小时喝一行的取样混合液，囚犯B每隔一小时喝一列的取样混合液，然后根据两人的死亡时间，就可以确定毒酒是哪桶了。” 本题很容易和前面老鼠试毒药的题混淆，误以为都可以利用二进制方法找出最佳解。实际上本题因为死亡时间的精确性、毒发时间与测试时间的时间差，使建立坐标成为可能。换一种思路，也许你就会发现一片新的天地。 拓展思维 （1）如果需要测试的酒的数量有10000桶，那么最少需要几名囚犯呢？ （2）如果需要测试的毒酒的数量有2桶，那么最少需要几名囚犯呢？ 数学加 微信：shuxuejiafen 开心学习，快乐加分！ |
|
|
