抓狐狸

标签:
教育 |
分类: 逻辑智力题 |
五个洞排成一排,其中一个洞里藏有一只狐狸。每个夜晚,狐狸都会跳到一个相邻的洞里;每个白天,猎人都只允许检查其中一个洞。怎样才能保证狐狸最终会被抓住?
http://s7/mw690/00717IDmzy7itsdOMoSc6&690
解题思路:
1、首先把问题简单化,如果只有3个洞,那非常好办。第一天查看2号洞,如果当天狐狸在2号洞,那么它就被抓住了;如果第一天没有发现狐狸,那么说明它一定在1号洞或者3号洞,第二天它一定跳到相邻的洞,1号洞和3号洞相邻的洞都是2号洞,所以第二天狐狸肯定会跳到2号洞。第二天只要再查看一次2号洞,就能抓获狐狸。
2、如果有4个山洞呢?通过采取如下策略:
第一天:查看2号洞,如果狐狸在2号洞,当场抓获;
第二天:再查看2号洞,如果第一天狐狸在1号洞,当场抓获;
因为第一天狐狸在1号洞,它第二天只能跳到2号洞,如果第二天没有发现狐狸,那么说明前两天狐狸在3号洞或者4号洞;
第三天:查看3号洞,如果狐狸在3号洞,当场抓获;如果没有发现狐狸,说明狐狸在2号洞或者4号洞,因为从3号洞可以跑到2号洞;
第四天:再查看3号洞口,如果狐狸前一天在4号洞,这天当场抓获,因为4号洞只能跳回3号洞。如果没有抓获,说明狐狸第三天在2号洞。第四天,狐狸从2号洞要么跳到3号洞,要么跳到1号洞。第四天没有在3号洞发现狐狸,说明第四天狐狸就在1号洞;
第五天:查看2号洞,当场抓获狐狸,这天狐狸只能从1号洞跳到2号洞。
3、经过前面的分析,思路就清晰多了。现在说明下本题5个洞的方案。
第一天:查看2号洞,如果不在2号洞中,则狐狸只能在1、3、4、5号洞中,晚上它只能跑到2、3、4、5号洞中;
http://s5/mw690/00717IDmzy7itqX7cB6a4&690
第二天:查看3号洞,如果不在3号洞中,则只能只2、4、5号洞中,晚上它只能跑到1、3、4、5号洞中;
http://s2/mw690/00717IDmzy7itrdKK3fc1&690
第三天:查看4号洞,如果不在4号洞中,则只能在1、3、5号洞中,晚上它只能跑到2、4号洞中;
http://s3/mw690/00717IDmzy7itrkZ27M22&690
第四天:查看4号洞,如果不在4号洞中,则只能在2号洞中,晚上它只能跑到1、3号洞中;
http://s2/mw690/00717IDmzy7itrscqZPa1&690
第五天:查看3号洞,如果不在3号洞中,则只能在1号洞中,晚上它只能跑到2号洞中;
http://s11/mw690/00717IDmzy7itrvR3gC3a&690
第六天,查看2号洞,当场抓获;
4、本题的方案不唯一,还有很多的其它方案。
方案1
http://s16/mw690/00717IDmzy7itrOzZvN8f&690
方案2
方案3
http://s8/mw690/00717IDmzy7its5aMsL77&690
5、本题本质上就是一个奇偶性的判断。只要猎人知道狐狸是在偶数号洞还是奇数号洞就可以了。
比方说,猎人知道狐狸是在偶数号洞里,那猎人只要第一天待2号洞,第二天待3号洞,第三天待4号洞,最晚第三天必然能抓到狐狸,因为猎人和狐狸都在偶数号洞里,那么猎人和狐狸的距离差偶数大小,而猎人每经过一天,和狐狸的距离要么不变,要么减2,所以总会相互碰到;
狐狸在奇数号洞里同样如此,猎人选择从奇数号洞开始待就可以了。所以关键是猎人如何确定狐狸到底是在奇数号洞还是在偶数号洞里。
可行方案:猎人从1号洞开始待,一直到第四天待到4号洞,都没抓住狐狸,说明狐狸第四天待在奇数号洞里,那第五天狐狸必然要去偶数号洞里。
6、此题还可以做进一步的思考,比方说增加洞的个数6个洞或者7个洞,或者5个洞是个环形,深度思考下吧。
7、n个洞时的可行方案
不论n多大,最坏情况下只需2n−4天就能逮到狐狸,策略是这样的:
若n为奇数,则从第一天开始搜寻的山洞编号为:2, 3, 4, …, n-1, 2, 3, 4, …, n-1;
若n为偶数,则从第一天开始搜寻的山洞编号为:2, 3, 4, …, n-1, n-1, n-2, …, 3, 2;
不管哪种情况,只需2n−4步即可逮到狐狸。
如果喜欢,请关注微信公众号:建世谷,更多精彩内容等着你,识别二维码关注
http://s14/mw690/00717IDmzy7i0TI7mZDed&690