IMO 2017 solutions II

只聊第 \(3\) 题.

这个题读起来有点费劲, 其实游戏的两方, 兔子和猎人, 都没有任何办法保证距离一定能多长或多近. 换句话说, 不管兔子和猎人如何行动, 兔子与猎人的距离是可能无限大也可能任意小. 这个问题要证明的结论就是: 不管猎人如何行动, 兔子有一个可能成功(而不是一定成功)的策略使得猎人的办法无效.

下面来证明这一点: 每一回合不管猎人如何行走, 兔子有一个行动方案, 在定位设备反馈某些点的情况下, 可能(而不是一定)使得与猎人的距离要多大有多大.

新加坡的 Jeck Lim 给出了一种漂亮的解法. Jeck Lim 很不得了, 是一个仙才哦, 他代表新加坡 5 次挂帅出征 IMO.

我们从这样的一种闭曲线开始: 这种曲线是由单位圆, 即半径为 \(1\) 的圆, 的下半圆和一段放置在半圆上面的半径为 \(r\) 的圆弧连结而成的闭曲线. 换句话说, 这种曲线的上部分是一个弓形, 下部分是一个半径为 \(1\) 的半圆. 显然, 这里要求 \(r\geqslant1\). 把这种曲线围成的有限区域称为 \(r\)-muffin. 注意:  \(r\)-muffin 包含曲线本身, 即有限区域的边界.  特别的, 半径为 \(1\) 的单位圆及其内部就是一个 \(1\)-muffin.

把那段半径为 \(r\) 的圆弧的中点称为这个 \(r\)-muffin 的顶; 把下面的那个半径为 \(1\) 的半圆的圆心称为 \(r\)-muffin 的中心.

Lemma 1  一个 \(r\)-muffin 和一个 \(r+1\)-muffin, 如果两者的对称轴重合, 前者的半径为 \(r\) 的圆弧的圆心和后者的半径为 \(r+1\) 的圆弧的圆心是同一点 \(O\), 并且前者的顶比后者的顶低 \(1\), 那么, 对于这 \(r+1\)-muffin 的任一点, 都存在这 \(r\)-muffin 的一点, 使得这两点的距离为\(1\).

事实上, 我们可以在 \(r\)-muffin 的半径为 \(r\) 的那段圆弧上找到这么的一点, 并且 \(r+1\)-muffin 可以改进为一个稍大的集合.

记 \(r\)-muffin 的半径为 \(r\) 的圆弧与下半单位圆的两个交点为 \(B_1\) 和 \(B_2\). 以 \(O\) 为心, 作半径为 \(r-1\) 的圆与 \(OB_1\) , \(OB_2\) 分别交于点 \(C_1\),  \(C_2\). 我们指出: 对于由 \(\widehat{A_1A_2}\), \(A_2C_2\), \(\widehat{C_1C_2}\), \(A_1C_1\) 围成的区域 \(R\) 内的任一点, 都可在 \(r\)-muffin 的半径为 \(r\) 的那段圆弧上找到这么的一点, 使得这两点的距离为\(1\).

我们只要以 \(\widehat{B_1B_2}\) 上的任意一点 \(M\) 为心, 作半径为 \(1\) 的圆. 然后 \(M\) 沿着 \(\widehat{B_1B_2}\) 移动得到的所有这样的单位圆, 必定经过了 \(R\) 的每一点.

Lemma 2  记号同 Lemma 1. 对于以 \(B_1\) 为心的单位圆的内部任一点(包括圆周),  都存在这 \(r\)-muffin 的一点, 使得这两点的距离为\(1\).

事实上, 我们可以在线段 \(B_1B_2\) 上找到这么的一点.

设 \(P\) 满足 \(B_1P\leqslant1\). 那么, 只要注意

\[B_1P\leqslant1\leqslant B_2P,\]

即 \(B_1\) 落在 \(P\) 为心的单位圆的内部(包括圆周), 而\(B_2\) 落在 \(P\) 为心的单位圆的外部(包括圆周), 于是线段 \(B_1B_2\) 与以 \(P\) 为心的单位圆周必有交点, 这交点当然与 \(P\) 的距离为 \(1\).

如果我们承认 “如果一段圆弧的一个端点在另一个圆的圆周或者内部, 另一个端点在这圆的外部, 那么这段弧与这个圆必有交点” 为真, 那么, Lemma 1 和Lemma 2 可以采用类似的手段统一解决.

Lemma 2 的证明, 把线段 \(B_1B_2\) 换成 \(\widehat{B_1B_2}\) 也是可以的. 也就是说, 如同 Lemma 1 一样, 我们也可以 在 \(\widehat{B_1B_2}\) 找到这一点.

至于 Lemma 1, 记 \(\widehat{A_1A_2}\) 与 \(\widehat{C_1C_2}\) 的中点分别是 \(N_1\), \(N_2\). 我们只要对线段 \(N_1N_2\) 上的点 \(P\) 证明 Lemma 1 即可, 一般的情形只要一个旋转就行了. 设 \(\widehat{B_1B_2}\) 的中点是 \(N\), 则 \(N\) 落在以 \(P\) 为心的单位圆内(包括圆周), 点 \(B_1\) 和 \(B_2\) 都落在这单位圆外. 于是 \(\widehat{B_1B_2}\) 与以 \(P\) 为心的半径为 \(1\) 的圆周必有交点.

Lemma 3  两个半径为 \(1\) 的圆, 彼此经过对方的中心, 即 \(\odot U\) 与 \(\odot V\) 都是单位圆, 且 \(\odot U\)  经过 \(V\),  \(\odot V\)  经过 \(U\). 那么, 对于 \(\odot U\)  的圆周或内部的任一点 \(P\), 必能在 \(\odot V\) 的圆周找到一点 \(A\), 使得 \(PA=1\).

显然,

\[PV\leqslant2\]

说明以 \(P\) 为心的单位圆周与 \(\odot V\) 必有交点. 在这交点任选一个为 \(A\).

我们称猎人到 \(r\)-muffin 的顶的距离为 \(d\), 如果猎人到过 \(r\)-muffin 的顶的切线的距离为 \(d\), 且猎人与 \(r\)-muffin 在过 \(r\)-muffin 的顶的切线的同侧.

在某个回合结束后, 如果有一个 \(r\)-muffin 满足下列两个条件:

• 在猎人看来, 兔子可能落在这个 \(r\)-muffin 的任何一点;
• 此时猎人到 \(r\)-muffin 的顶的距离至少是 \(d\),

则称游戏处于状态 \((r, d)\).

当游戏处于状态 \((r,d)\), 且 \(r\gt d\geqslant2\) 时, 设猎人在点 \(H\), \(\widehat{B_1B_2}\) 的中点是 \(N\). 作 \(HX\parallel B_1B_2\) 交 \(ON\) 于点 \(X\). 注意: 猎人不知道自己是否与兔子在直线 \(ON\) 的同一侧.

Lemma 2 说明: 下一回合, 兔子的位置可能是以 \(B_1\) 为心的单位圆内部(包括圆周) 的任一点.

此时, 定位设备向猎人反馈点 \(B_1\).

如果 \(H\), \(B_1\) 在 \(ON\) 的异侧, 记 \(HB_1\) 的延长线 与以 \(B_1\) 为心的单位圆周交于点 \(T\). 现在把以 \(B_1\) 为心的单位圆看成 \(1\)-muffin, \(T\) 为其顶. 然后, \(ON=r\), \(XN=d\),

\begin{equation}   \begin{split}HT&=1+HB_1 \\ &\geqslant1+XB_1 \\&=1+ \sqrt{1+\Big(d-r+\sqrt{r^2-1}\Big)^2} \end{split}    \end{equation}

说明猎人行动后, 游戏已经处于状态 \(\Big(1,\sqrt{1+\big(d-r+\sqrt{r^2-1}\big)^2}\Big)\).

Lemma 4 \(r\gt d\geqslant2\) 时, 兔子可能把处于状态 \((r, d)\) 的游戏改成状态 \(\Big(1,\sqrt{1+\big(d-r+\sqrt{r^2-1}\big)^2}\Big)\).

我们实际只需要 Lemma 4 和下面的 Lemma 5 当 \(r=[2d]+1\) 时的结果(这里 \([x]\) 表示不超过 \(x\) 的最大整数), 主要的原因就是因为 Lemma 6 导致我们只能对正整数的 \(r\) 使用 Lemma 4 和 Lemma 5. \([2d]+1\) 换成稍大一点的数也是可以的, 比如 \(4[d]\), 只要最后估计的回合数小于 \(10^9\) 就行.

Lemma 5 \(d\geqslant2\), \(r\geqslant2d\) 时,

\begin{equation} \sqrt{1+\big(d-r+\sqrt{r^2-1}\big)^2}\gt\sqrt{d^2+\frac12}.\end{equation}

\(-r+\sqrt{r^2-1}\) 的单调性蕴涵我们只要对 \(r=2d\) 证明这结论就行了, 即只要指出

\begin{equation} \sqrt{1+(-d+\sqrt{4d^2-1})^2}\gt\sqrt{d^2+\frac12}.\end{equation}

一个 \(r\)-muffin 和一个 \(r+1\)-muffin, 并且两者的对称轴重合, 前者的半径为 \(r\) 的圆弧的圆心和后者的半径为 \(r+1\) 的圆弧的圆心是同一点 \(O\), 前者的顶比后者的顶低 \(1\), 那么, 如果在某个回合结束后, 游戏处于状态 \((r, d)\), 则依据 Lemma 1, 下一回合兔子的位置可能是 \(r+1\)-muffin 的任一点. 定位设备向猎人反馈点是 \(r+1\)-muffin 的中心, 于是, 无论猎人如何行动, 游戏都进入状态 \((r+1, d)\).

Lemma 6 \(d\geqslant1\) 时, 兔子能把处于状态 \((r, d)\) 的游戏改成状态 \((r+1, d)\).

外围清理完毕, 准备工作结束, 现在正式的回到游戏之初.

第一回合, 兔子随便的移动到某点, 然后定位设备向猎人反馈点是 \(A_0\). 待猎人应对完毕, 则兔子和猎人的位置是以 \(A_0\) 为心的半径为 \(1\) 的圆周上的任意可能的两个点 \(R_1\), \(H_1\).

第二回合, 设点 \(C\) 落在以 \(A_0\) 为心的半径为 \(1\) 的圆周上, 并且 \(C\) 是 \(H_1\) 的对径点. 在这一回合, 对兔子移动到的点 \(R_2\) 的惟一要求是: \(R_2\) 与 \(C\) 的距离至多为 \(1\). 把以 \(C\) 为心的单位圆看成  \(1\)-muffin, \(A_0\) 在此单位圆的对径点为其顶. Lemma 3 表明 \(R_2\) 可能是这个 \(1\)-muffin 的任意一点. 然后, 定位设备向猎人反馈点是 \(C\). 此时, 无论猎人如何行动, 游戏都会进入状态 \((1, 2)\).

当游戏处于状态 \((1, t)\), 且实数 \(t\geqslant2\). 据 Lemma 6, 兔子经过 \([2t]\) 回合, 能使游戏到达状态  \(([2t]+1, t)\). 然后, Lemma 4, 兔子可能在下回合使得游戏是状态 \(\Big(1,\sqrt{1+\big(t-a+\sqrt{a^2-1}\big)^2}\Big)\), 这里 \(a=[2t]+1\). Lemma 5 说明此时的游戏处于状态 \(\Big(1, \sqrt{t^2+\frac12}\Big)\). 故此, 兔子可能在至多 \(2\sqrt s+1\) 回合把游戏的的状态由 \((1, \sqrt s)\) 改为 \(\Big(1, \sqrt{ s+\frac12}\Big)\),  实数 \(s\gt 2\). 于是, 兔子至多只需要

\begin{equation} 2\Big( \sqrt4 +\sqrt{4.5}+\sqrt5 +\sqrt{5.5}+\dotsb+\sqrt{103^2-0.5}\Big)+2\cdot103^2\end{equation}

回合, 可能使游戏处于状态 \((1, 103)\). 然而

\begin{equation} \begin{split}2\Big( \sqrt4 +\sqrt{4.5}+\sqrt5 +\sqrt{5.5}+\dotsb+\sqrt{103^2-0.5}\Big)+2\cdot103^2&\lt  4\Big( \sqrt4 +\sqrt5 +\sqrt{6}+\dotsb+\sqrt{103^2}\Big)+2\cdot103^2 \\ &\lt  4\cdot103\cdot103^2+2\cdot103^2 \\ &\lt500\cdot1000^2=5\cdot10^8\lt10^9\end{split}    \end{equation}

表明兔子在不超过 \(5\cdot10^8\) 回合就有可能使得与猎人的距离至少是 \(101\). 也就是说, 猎人不能保证经过 \(10^9\) 回合后, 她和兔子的距离至多是 \(100\).

解答二

另一种较为常见的办法是:

这个解答的字母记号与前一个答案有一点点的差别.

第一回合, 兔子随便的移动到某点, 然后定位设备向猎人反馈点是 \(A_0\). 待猎人应对完毕, 则兔子和猎人的位置是以 \(A_0\) 为心的半径为 \(1\) 的圆上的任意的两点 \(A_1\), \(B_1\). \(A_1\) 与 \(B_1\) 之间的距离可以是区间 \([0, 2]\) 的任何实数.

在某个回合结束后, 兔子和猎人的距离为 \(d\), 并且 \(d\geqslant1\). 那么, 不论猎人如何移动, 兔子在 \([2d]+1\) 回合后, 可能和猎人的距离至少是 \(\sqrt{d^2+\frac12}\).

事实上, 此时兔子和猎人分别所在的点 \(R\) 和 \(H\) 有 \(RH=d\). 记 \(l=[2d]+1\). 取关于直线 \(HR\) 对称的两点 \(A\), \(B\), 使得三角形 \(RAB\) 是等腰三角形,  \(RA=RB=l\), \(AB=2\), 并且 \(HR\) 的延长线交线段 \(AB\) 于 \(M\). 显而易见, \(M\) 是线段 \(AB\) 的中点, \(RM=\sqrt{l^2-1}\).

设 \(U_1\), \(U_2\), \(\dotsc\), \(U_{l-1}\); \(V_1\), \(V_2\), \(\dotsc\), \(V_{l-1}\); \(T_1\), \(T_2\), \(\dotsc\), \(T_{l-1}\)  分别是线段\(RA\), \(RB\), \(RM\) 的 \(l\) 等分点. 鉴于 \(RA=RB=l\), 在接下来的 \(l\) 个回合, 兔子可以从 \(R\) 出发, 沿着 \(RA\) 依次路过 \(U_1\), \(U_2\), \(\dotsc\), \(U_{l-1}\) 到达 \(A\) 或者沿着 \(RB\) 依次路过 \(V_1\), \(V_2\), \(\dotsc\), \(V_{l-1}\) 到达 \(B\). 当兔子停留 \(U_i\) 或者 \(V_i\) 之时, 定位设备向猎人反馈点是 \(T_i\), 因为 \(U_iT_i=V_iT_i\leqslant1\) 说明把 \(T_i\) 作为反馈点是允许的, \(i=1\), \(2\), \(\dotsc\), \(l-1\). 兔子到达 \(A\) 或者 \(B\) 之时, 定位设备向猎人反馈点是 \(M\), 此时, 猎人行动来到点 \(P\). 然而, 猎人不能保证自己与兔子在直线 \(HM\) 的同一侧. 如果猎人与兔子在直线 \(HM\) 的两侧, 比如兔子在 \(A\), 而猎人在直线 \(HM\) 的下方(包括猎人在直线 \(HM\) 上), 那么, 注意到 \(d\lt\dfrac l2\),

\begin{equation} \begin{split}PA^2&\geqslant1+\left(\sqrt{l^2-1}-(l-d)\right)^2\\&=d^2+2(l-d)\left(l-\sqrt{l^2-1}\right)\\&=d^2+\frac{2(l-d)}{l+\sqrt{l^2-1}}\\&\gt d^2+\frac{2\big(l-\frac l2\big)}{l+l}\\&=d^2+\frac 12.\end{split}    \end{equation}

在 \(d\leqslant100\) 之时, 兔子至多只要 \([2d]+1\leqslant201\) 回合, 就有可能使得和猎人的距离的平方增加至少 \(\dfrac12\). 于是, 兔子在 \(201 \cdot 2 \cdot 100^2 < 10^9\) 回合之后, 可能使得和猎人的距离达到 \(100\). 因此, 猎人不能保证经过 \(10^9\) 回合后, 她和兔子的距离至多是 \(100\).

如果把题目的一个猎人改为 \(m\) 个, 结果会怎么样? 兔子是否依旧有可能逃走? 或者, 猎人能保证不管多少回合以后, 她与兔子的距离不会超过某个界, 比如 \(100\) 米?

答案依旧是猎人不能保证!