(本部数特综数压轴题)圆$O$的圆周上有一只猫和$n$只老鼠,设猫的初始位置为洞口$P$,老鼠初始位置任意,且猫和老鼠均可自由在圆周上移动,猫的速度是老鼠的$k;;(k>1)$倍。当猫和老鼠位于同一位置时,称猫捉住了这只老鼠;当老鼠位于洞口且猫不在洞口时,称这只老鼠逃脱,显然猫和老鼠都在洞口时猫仍然捉住了这只老鼠。

若要让猫在有限时间内捉住所有老鼠,不让任何老鼠逃脱,且猫和老鼠都会选择最佳策略,那么$k$的最小值是?

题面描述

答案

$n=1$时$k_{min}=2$,$n>1$时$k_{min}=3$。

证明

分类讨论:

当$n>1$时

从老鼠的角度分析,考虑离$P$最近的左右两只老鼠$\mathtt{A}$和$\mathtt{B}$,由于其他老鼠想要逃脱肯定没有$\mathtt{A}$和$\mathtt{B}$快,因此最优策略只能让它们俩跑向洞口。再从猫的角度分析,此时猫必然跑向离他最近的老鼠(假设是$\mathtt{A}$)然后再次跑回洞口防止$\mathtt{B}$逃脱,因为要想在有限时间内捉到老鼠必须主动出击,否则只会消耗时间。

显然当$\mathtt{A}$和$\mathtt{B}$离猫距离相等时最优(因为如果$\mathtt{B}$远是没有优势的,这时候肯定离洞口越近越好,便于冲刺。但如果比$\mathtt{A}$还近,那么它们角色就交换了,所以距离相等最优)。而$\mathtt{A}$的任务就是逃离猫,$\mathtt{B}$的任务就是跑向洞口(因为距离相等,所以$\mathtt{A}$和$\mathtt{B}$关于$OP$对称,这时设猫跑向$\mathtt{A}$,那么$\mathtt{A}$一定要拖延时间远离洞口,而$\mathtt{B}$一定会跑向洞口(反着跑有啥用),因此只能这样跑)。

接着可以列方程,设$\mathtt{A}$被捉住时的时间为$t$,$\mathtt{A}$和$\mathtt{B}$距洞口的距离为$L$,老鼠速度是$1$,那么猫的速度就是$k$。得

$$kt-t=L$$

所以

$$t=\frac{L}{k-1}$$

又因为猫赶回洞口时的时间为$2t$,那么当猫回到洞口时$\mathtt{B}$移动了$2t$,一定小于等于$L$,得

$$\frac{2L}{k-1} \leqslant L$$

解得$k \leqslant 3$,此时猫一定能捉住$\mathtt{A}$并且回到P,于是只剩下了$n-1$只老鼠,问题就转化为以下两种情况:若只剩一只老鼠需要$k \leqslant 2$(接下来要证明),还剩多于一只老鼠则按上面的方法分析,两种情况无论如何都能全部捉住,因此k的最小值一定为3.

当$n=1$时

猫仍然需要主动出击,由于是一个圆周,猫肯定会选择离老鼠距离最短的弧,那么老鼠肯定要走另外一条长的弧到达洞口。从老鼠的角度分析,它必须要让长的弧越短越好,但是当长弧小于一半周长时长弧就会变为短弧,所以最优策略一定是在猫正对面。当老鼠走完一半周长到达洞口时,猫必须得走完整个圆周才能及时捉住老鼠,显然$k \leqslant 2$,证毕。


评论