修改日期

2021-01-07 09:38:03

一道题

category:

• 数学

tags:

• 学术
• MO

（本部数特综数压轴题）圆$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$，证毕。