Jul 262017
 

只聊第 \(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 的中心.

IMO 2017

IMO 2017 p3 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 可以改进为一个稍大的集合.

IMO 2017

IMO 2017 p3

记 \(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\).

IMO 2017

IMO 2017 p3

事实上, 我们可以在线段 \(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\).

IMO 2017

IMO 2017 p3

显然,

\[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\) 的同一侧.

IMO 2017

IMO 2017 p3

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)\).

IMO 2017

IMO 2017 p3

当游戏处于状态 \((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\). 记 \(m=[2d]+1\). 取关于直线 \(HR\) 对称的两点 \(A\), \(B\), 使得三角形 \(RAB\) 是等腰三角形,  \(RA=RB=m\), \(AB=2\), 并且 \(HR\) 的延长线交线段 \(AB\) 于 \(M\). 显而易见, \(M\) 是线段 \(AB\) 的中点, \(RM=\sqrt{m^2-1}\).

IMO 2017

IMO 2017 p3

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

\begin{equation} \begin{split}PA^2&\geqslant1+\left(\sqrt{m^2-1}-(m-d)\right)^2\\&=d^2+2(m-d)\left(m-\sqrt{m^2-1}\right)\\&=d^2+\frac{2(m-d)}{m+\sqrt{m^2-1}}\\&\gt d^2+\frac{2\big(m-\frac m2\big)}{m+m}\\&=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\) 米?

答案依旧不变

 Posted by at 12:33 pm  Tagged with:
Jul 182017
 

2017 第 58 届 IMO 解答

Problem 1 (South Africa)

Lemma 1 当实数 \(x\geqslant6\), 则 \(x\lt(x-3)^2\).

Lemma 2 若整数 \(m\) 符合 \(m \equiv 2\pmod3\), 则 \(m\) 不能是完全平方.

若数列 \(\{a_n\}\) 的某一项 \(\gt1\), 则紧挨着的后一项也 \(\gt1\). 因此, \(a_0\gt1\) 说明这数列的所有项都 \(\gt1\).

首先, 若数列 \(\{a_n\}\) 的某一项 \(a_i\) 使得 \(a_i\equiv 2\pmod3\), 则这一项不是完全平方, \(a_{i+1}=a_i+3\), \(a_{i+1}\equiv 2\pmod3\). 于是, \(a_0\equiv 2\pmod3\) 之时, 数列 \(\{a_n\}\) 就是一个以 \(a_0\) 为首项, 公差为 \(3\) 的等差数列. 此时, 数列 \(\{a_n\}\) 的各项互不相同导出如此这般的 \(a_0\) 不是我们寻找的. 进而, 数列 \(\{a_n\}\) 的如果有一项 \(\equiv 2\pmod3\), 那么这数列不可能有无穷多项相同.

其次: 在数列 \(\{a_n\}\) 中, 如果存在某一项 \(a_s(s\geqslant0)\) 使得 \(a_s \equiv 0, 1\pmod3\), 且 \(a_s\geqslant6\), 那么必定有大于 \(s\) 的正整数 \(t\), 使得 \(a_t\lt a_s\), 并且当 \(a_s \equiv 0\pmod3\) 时, \(a_t\equiv 0\pmod3\); 当 \(a_s \equiv 1\pmod3\) 时, \(a_t\not\equiv 0\pmod3\).

这是因为, 在 \(a_s \equiv 0, 1\pmod3\), \(a_s\geqslant6\) 时, 我们依次考察从 \(a_s\) 开始的项:

\begin{equation}a_s, a_{s+1}, a_{s+2}, \dotsc.\end{equation}

然后

\[a_s\lt(a_s-3)^2,\qquad a_s \equiv (a_s-3)^2\pmod3\]

表明 \((1)\) 中必有一项 \(a_u(u\geqslant s)\), 满足 \(a_u\) 为完全平方, 且 \(a_u\leqslant (a_s-3)^2\). 取 \(t=u+1\), 则 \(t\gt s\), \(a_t=a_{u+1}\leqslant a_s-3\) 蕴涵 \(t\) 符合我们的要求.

现在, 当 \(a_0\equiv 0, 1\pmod3\), 我们知道必有 \(\{a_n\}\) 的某一项 \(a_j(j\geqslant0)\), 使得 \(a_j\lt6\), 并且 \(a_0 \equiv 0\pmod3\) 时, \(a_j\equiv 0\pmod3\); 当 \(a_0 \equiv 1\pmod3\) 时, \(a_j\not\equiv 0\pmod3\).

事实上, 如果 \(a_0\geqslant6\), 那么必定有大于正整数  \(t_1\), 使得 \(a_{t_1}\lt a_0\); 在 \(a_{t_1}\geqslant6\), 那么必定有大于 \(t_1\) 的正整数 \(t_2\), 使得 \(a_{t_2}\lt a_{t_1}\); 在 \(a_{t_2}\geqslant6\), 有大于 \(t_2\) 的正整数 \(t_3\), 使得 \(a_{t_3}\lt a_{t_2}\);…; 如此这般下去. 但这个过程不可能一直继续: 我们最终会得到 \(\{a_n\}\) 的某一项 \(a_j(j\geqslant0)\), 使得 \(a_j\lt6\).

既然 \(a_j\), 使得 \(1\lt a_j\lt6\), 于是 \(a_j\) 只可能是 \(2\), \(3\), \(4\),  \(5\).

当 \(a_j=4\) 时, \(a_{j+1}=2\). 于是, 在 \(a_j\) 为 \(2\), \(4\), \(5\) 之一(此时 \(a_0 \equiv 1\pmod3\)), 当 \(k\gt j\), 有 \(a_k\equiv 2\pmod3\). 因之, 数列 \(a_{j+1}\), \(a_{j+2}\), \(a_{j+2}\), \(\dotsc\) 是一个以 \(a_{j+1}\) 为首项, 公差为 \(3\) 的等差数列, 故而不可能在数列 \(\{a_n\}\) 有无穷多项重复.

当 \(a_j=3\) 时(此时 \(a_0 \equiv 0\pmod3\)), \(a_{j+1}=6\), \(a_{j+2}=9\), \(a_{j+3}=3\). 于是, 数列 \(\{a_n\}\) 从 \(a_j\) 开始的项依次就是

\[3, 6, 9, 3, 6, 9, 3, 6, 9, \dotsc.\]

此时, \(3\), \(6\), \(9\) 都会在数列 \(\{a_n\}\) 无穷多次的重复出现,

综上所述, 我们寻找的符合要求的所有 \(a_0\) 就是全体的满足 \(a_0 \equiv 0\pmod3\) 的正整数.

Problem 2 (Dorlir Ahmeti, Albania)

本题的难点是 \(f(x)\) 为单射.

如果\(f(0)=0\).

令 \(y=0\), 有

\[f(0)+f(x)=f(0),\]

即, 对于任意的实数 \(x\), \(f(x)=0\) 为真.

如果 \(f(0)\ne0\). 在 \(f(x)\) 为符合要求的函数, 则 \(-f(x)\) 亦为所求. 故此, 我们只要考虑 \(f(0)\gt0\) 此种情况就行了.

令 \(x=y=0\), 得

\[f(f^2(0))+f(0)=f(0).\]

若记 \(f^2(0)=a\), 则 \(f(a)=0\).

如果 \(f(b)=0\), 则 \(b=1\).

若不然, \(b\ne1\). 令 \(x=\dfrac b{b-1}\), \(y=b\), 则

\begin{equation}f(f(\frac b{b-1})f(b))+f(\dfrac b{b-1}+b)=f(\frac {b^2}{b-1}),\end{equation}

即 \(f(0)=0\). 矛盾!  故而, \(f(a)=0\) 蕴涵 \(a=1\), 进而, 根据 \(f^2(0)=1\), 鉴于我们只观摩  \(f(0)\gt0\), 于是 \(f(0)=1\), \(f(1)=0\).

令 \(y=1\), 我们得出

\[f(0)+f(x+1)=f(x),\]

\begin{equation}f(x+1)=f(x)-1.\end{equation}

下面指出: \(f(x)\) 为单射.

事实上, 如果实数 \(a\) 和 \(b\) 使得 \(f(a)=f(b)\). 注意

\begin{equation}\big(a^2-4(b-1)\big)+\big(b^2-4(a-1)\big)=(a-2)^2+(b-2)^2\geqslant0\end{equation}

说明 \(a^2-4(b-1)\geqslant0\), \( b^2-4(a-1)\geqslant0\) 至少一个, 不妨前者, 为真.

然后, \(a^2-4(b-1)\geqslant0\) 蕴涵二次方程 \(x^2-ax+b-1=0\) 有两个实根 \(r\), \(s\). 故此, \(r+s=a\), \(rs=b-1\).

令 \(x=r\), \(y=s\),

\[f(f(r)f(s))+f(r+s) = f(rs).\]

根据 \((3)\),

\[f(f(r)f(s)+1)+f(r+s) = f(rs+1).\]

由 \(r+s=a\), \(rs+1=b\),

\begin{equation}f(f(r)f(s)+1) = 0\end{equation}

这表示 \(f(r)f(s)+1=1\), 即 \(f(r)f(s)=0\), 故 \(f(r)=0\), 即 \(r=1\),  或 \(f(s)=0\), 即 \(s=1\). 无论是 \(r=1\), 此时 \(a=b=s+1\), 还是 \(s=1\), 此时 \(a=b=r+1\), 都能得出 \(a=b\). 从而 \(f(x)\) 为单射.

令 \(y=-x\), 得

\[f(f(x)f(-x))+f(0) = f(-x^2).\]

这就是

\[f(f(x)f(-x)) = f(-x^2)-1=f(1-x^2).\]

\(f(x)\) 为单射导出

\begin{equation}f(x)f(-x) =1-x^2.\end{equation}

令 \(y=1-x\), 得

\[f(f(x)f(1-x))+f(1) = f(x-x^2).\]

这就是

\[f(f(x)f(1-x))= f(x-x^2).\]

\(f(x)\) 为单射导出 \(f(x)f(1-x)=x-x^2\), 即

\begin{equation}f(x)(f(-x)-1) =x-x^2.\end{equation}

于是

\[f(x)=f(x)f(-x)-(x-x^2)=(1-x^2)-(x-x^2)=1-x.\]

经检验, \(f(x)=1-x\), \(f(x)=x-1\), \(f(x)=0\) 满足条件, 从而就是我们要找的全部函数.

Problem 3 (Austria)

这个题刷新了记录, 成了 IMO 得分最低的题. 考场上居然只有 2 个人得到 7 分, 一共也只有 7 人的分不是 0, 尤其中国, USA 这样的竞赛强国在这个题都得了 0. 中国上一次出现这样的尴尬还是 21 年前, 即 1996 年的 P5 的几何不等式.

本题有专文处理: IMO 2017 solutions II

Problem 4 (Charles Leytem, Luxembourg)

写第 3 题花费不少时日, 第二天的题迟迟未动笔. 这个题只是寥寥数语.

IMO 2017

IMO 2017 p4

记 \(RA\) 与 \(\Gamma\) 的另一个交点为 \(B\). 连结 \(KR\), \(KS\), \(BS\), \(BT\).

\(K\), \(R\), \(J\), \(S\) 四点共圆, 以及\(S\), \(J\), \(A\), \(B\) 亦是四点共圆, 定出 \(\angle KRS=\angle KJS=\angle RBS\).

\(RA\) 为 \(\Omega\) 的切线蕴涵 \(\angle RKS=\angle BRS\). 于是, \(\triangle RKS\sim\triangle BRS\), 故此

\(\angle RSK=\angle BSR\), 然后  \(\angle RSK=\angle BSR\);

以及

\(\frac{KS}{RS}=\frac{RS}{BS}\),  结合 \(RS=TS\), 然后

\[\frac{KS}{TS}=\frac{TS}{BS}.\]

至此, 我们可以断言 \(\triangle KTS\sim\triangle TBS\), 进而 \(\angle KTS=\angle TBS\), 这也就导出了直线 \(KT\) 与圆 \(\Gamma\) 相切.

Problem 5 (Russia)

用归纳法几句话就能透彻.

把全部的队员按身高分成 \(N\) 组: 身高最低的 \(N+1\) 个队员一组, 身高次低的 \(N+1\) 个队员一组, …, 身高最高的 \(N+1\) 个队员一组. 我们来从每组选出  \(2\) 人, 使得在最后的  \(2N\) 人, 属于同组的  \(2\) 人是紧挨的.

\(N=2\) 时, 这排球员左边 \(3\) 人必有 \(2\) 人属同一组, 选出这 \(2\) 人; 右边 \(3\) 人必有 \(2\) 人亦属同一组, 选出这 \(2\) 人. 如此, 教练移走了 \(2\) 人, 剩下 \(4\) 人的左边  \(2\) 人与右边 \(2\) 人分属不同的组.

假定对于 \(N(N-1)\) 个球员结论为真, \(N\geqslant3\). 下面来考察 \(N(N+1)\) 个球员.

这一排最左边的 \(N+1\) 人必有 \(2\) 人是同一组. 在这\(N+1\) 人选出同组的 \(A\) 和 \(B\),  且 \(A\) 在 \(B\) 左边, 并且 \(B\) 左边的队员都属于不同的组. 移走 \(B\) 左边除 \(A\) 以外的其他队员, 再把 \(B\) 右边那些与 \(B\) 同组队员全部移走. 这样, \(B\) 右边的队员全部与 \(B\) 不同组, 并且 \(B\) 不属于的每个组至少留下 \(N\) 人在 \(B\) 右边. 如果有哪个组有 \(N+1\) 人在 \(B\) 右边, 就随便在这组移走 \(1\) 人. 现在, \(B\) 右边 \(N(N-1)\) 个球员分属于 \(N-1\) 组, 每组 \(N\) 人. 由归纳假设, \(B\) 右边的 \(N(N-1)\) 个球员可以每组选出 \(2\) 人是紧挨的. 这选出的 \(2(N-1)\) 人, 以及 \(A\) 和 \(B\), 这 \(2N\) 个队员属于同组的  \(2\) 人是紧挨的.

Problem 6 (John Berman, USA)

本题用来做 2 或者 5 是比较合适的.

对 \(|S|\) 进行归纳.

当 \(S\) 只有一个元素 \((p_0, q_0)\) 时, 既然 \((p_0, q_0)=1\) 时, 著名的 Bezout 恒等式指出存在整数 \(a\), \(b\), 使得

\[ap_0+bq_0=1.\]

令 \(P(x, y)=ax+by\), 此多项式对于\(S\) 的惟一的元素 \((p_0, q_0)\), 有 \(P(p_0, q_0)=1\).

假定当 \(|S|=m\) 时, 命题为真, \(m\geqslant1\). 下面认定 \(S = \left \{ (p_1, q_1), (p_2, q_2), \dotsc, (p_{m+1}, q_{m+1}) \right \}\), \(|S|=m+1\).

依归纳假设, 有齐次整系数多项式 \(G(x, y)\) 符合 \(G(p_k, q_k) = 1\), \(k=1\), \(2\), \(\dotsc\), \(m\). 令 \(\deg(G)=g\).

然后,  \((p_{m+1}, q_{m+1}) =1\), 故此, 存在整数 \(u\), \(v\), 使得

\begin{equation}up_{m+1}+vq_{m+1}=1.\end{equation}

考察

\begin{equation}F(x, y) = \big (G(x, y) \big )^h – w\Big(\prod_{k=1}^m\left ( q_kx-p_ky \right ) \Big) \Big(ux+vy\Big)^{gh-m},\end{equation}

这里的 \(h\) 是大于 \(\dfrac mg\) 的待定的正整数, \(w\) 是待定的整数. 于是, \(F(x, y)\) 是整系数齐次多项式, 并且 \(F(p_k, q_k) = 1\), \(k=1\), \(2\), \(\dotsc\), \(m\).

令 \(A= G(p_{m+1}, q_{m+1})\), \(B=\prod\limits_{k=1}^{m}\left(q_kp_{m+1}-p_kq_{m+1} \right )\). 下面来说明  \((A, B)=1\).

若不然, 存在质数 \(p\), 满足 \(p|G(p_{m+1}, q_{m+1})\), \(p|\left(q_kp_{m+1}-p_kq_{m+1} \right )\), 这里 \(k\in\{1, 2, \dotsc, m\}\).

由 \(\left(q_k, p_k \right )=1\), 因此 \(q_k\), \(p_k \) 必有一个不被 \(p\) 整除, 不妨 \(q_k\) 不被 \(p\) 整除. 既然 \(G(x, y)\) 是齐次多项式, 并且 \(p_kq_{m+1}\equiv q_kp_{m+1}\pmod p\), 于是

\begin{equation}q_{m+1}^g = q_{m+1}^g G(p_k, q_k) = G(p_kq_{m+1}, q_kq_{m+1}) \equiv G(q_kp_{m+1}, q_kq_{m+1}) = q_k^g G(p_{m+1}, q_{m+1}) \equiv 0 \pmod p\end{equation}

导出 \(p|q_{m+1}\). 结合 \(p|\left(q_kp_{m+1}-p_kq_{m+1} \right )\), 给出 \(p|p_{m+1}\). 矛盾!

既然 \((A, B)=1\), Euler 定理指出, 存在足够大的正整数 \(h\) 以及整数 \(w\), 使得

\begin{equation}A^h – wB = 1.\end{equation}

如此一来,

\begin{equation}\begin{split}F(p_{m+1}, q_{m+1}) &= \big (G(p_{m+1}, q_{m+1}) \big )^h – w\Big(\prod_{i=1}^m\left ( q_ip_{m+1}-p_i q_{m+1} \right ) \Big)\Big(up_{m+1}+v q_{m+1}\Big)^{gh-m}\\&=A^h – wB=1.\end{split}\end{equation}

这便完成了征途.

Annotations

  1. 第 2 题的函数方程, 没有什么新奇的. 得分那么低, 倒是有点出乎意料.
  2. 第二天的题其实没啥特别, 难度也不大.
  3. 第三题确实有独到之处, 是这个试卷仅有的好题.
  4. 这六个题何以成为史上得分最低的试卷呢! 除了第三题, 别的题为啥得分也不高?
 Posted by at 2:24 pm  Tagged with:
Jul 182017
 

                                      Day \(1\)

 Tuesday, July 18, 2017

Problem 1. For each integer  \(a_0\gt1\), define the sequence \(a_0\), \(a_1\), \(a_2\), \(\dotsc\) by:

\[a_{n+1} = \begin{cases}\sqrt{a_n} & \text{if } \sqrt{a_n} \text{ is an integer,} \\a_n + 3 & \text{otherwise.}\end{cases}\quad \text{for each}\; n\geqslant 0.\]

Determine all values of \(a_0\) so that there exists a number \(A\) such that \(a_n = A\) for infinitely many values of \(n\).

Problem 2. Let \(\Bbb R \) be the set of real numbers. Determine all functions \(f\colon \Bbb R \rightarrow \Bbb R\) such that, for all real numbers \(x\) and \(y\),

\[f\big(f(x)f(y)\big) + f(x+y) = f(xy).\]

Problem 3. A hunter and an invisible rabbit play a game in the Euclidean plane. The rabbit’s starting point, \(A_0\) , and the hunter’s starting point, \(B_0\) are the same. After \(n-1\) rounds of the game, the rabbit is at point \(A_{n-1}\) and the hunter is at point \(B_{n-1}\) . in the \(n^{\text{th}}\) round of the game, three things occur in order:

i) The rabbit moves invisibly to a point \(A_n\) such that the distance between \(A_{n-1}\) and \(A_n\) is exactly \(1\) .

ii) A tracking device reports a point \(P_n\) to the hunter. The only guarantee provided by the tracking device to the hunter is that the distance between \(P_n\) and \(A_n\) is at most \(1\) .

iii) The hunter moves visibly to a point \(B_n\) such that the distance between \(B_{n-1}\) and \(B_n\) is exactly \(1\) .

Is it always possible, no matter how the rabbit moves, and no matter what points are reported by the tracking device, for the hunter to choose her moves so that after \(10^9\) rounds, she can ensure that the distance between her and the rabbit is at most \(100\) ?

                                      Day \(2\)

 Wednesday, July 19, 2017

Problem 4. Let \(R\) and \(S\) be different points on a circle \(\Omega\) such that \(RS\) is not a diameter. Let \(\ell\) be the tangent line to at \(R\). Point \(T\) is such that \(S\) is the midpoint of the line segment \(RT\). Point \(J\) is chosen on the shorter arc \(RS\) of \(\Omega\) so that the circumcircle  \(\Gamma\) of triangle \(JST\) intersects \(\ell\) at two distinct points. Let \(A\) be the common point of \(\Gamma\) and \(\ell\) that is closer to \(R\). Line \(AJ\) meets \(\Omega\) again at \(K\). Prove that the line \(KT\) is tangent to \(\Gamma\).

Problem 5. An integer \(N\geqslant2\) is given. A collection of \(N(N + 1)\) soccer players, no two of whom are of the same height, stand in a row. Sir Alex wants to remove \(N(N-1)\) players from this row leaving a new row of \(2N\) players in which the following \(N\) conditions hold:

(1) no one stands between the two tallest players,

(2) no one stands between the third and fourth tallest players,

\(\vdots\)

(N) no one stands between the two shortest players.

Show that this is always possible.

Problem 6. An ordered pair \((x, y)\) of integers is a primitive point if the greatest common divisor of \(x\) and \(y\) is \(1\). Given a finite set \(S\) of primitive points, prove that there exist a positive integer \(n\) and integers \(a_0\), \(a_1\) , \(\dotsc\), \(a_n\) such that, for each \((x, y)\) in \(S\), we have:

\[a_0x^n + a_1x^{n-1}y + a_2x^{n-2}y^2 + \dotsb + a_{n-1}xy^{n-1} + a_ny^n = 1.\]

 Posted by at 2:09 pm  Tagged with:
Mar 172017
 

试题来自贴吧

2017 China IMO team selection

2017 China IMO team selection test 2 day 1

2017 China IMO team selection

2017 China IMO team selection test 2 day 2

这里转一下贴吧网友 1a2b03c 给出的题 6 有关的一个关键, 这网友水平挺高的

\(\alpha\), \(\beta\) 都是无理数,

2017 China IMO team selection test

2017 China IMO team selection test

2017 China IMO team selection test


邓煜的看法:

最后那里可以不用极限来说. 只要证明对任何 \(c\gt0\), 存在 \(n\) 使得\(\{n\beta\}\) 属于 \((b_3, b_4)\) 且 \(\{n\alpha\}\lt c\) 即可. 假设不然, 由引理 3, 取 \(n^\prime\) 和 \(n^{\prime\prime}\) 使得 \(\{n^\prime\beta\}\lt \dfrac{b_4-b_3}2\), \(\{n^\prime\alpha\}=1-p(p<c) \) 和 \(\{n^{\prime\prime}\beta\}>1-\dfrac{b_4-b_3}2\), \(\{n^{\prime\prime}\alpha\}=1-q(q<c)\).

今对任何 \(n\),若\(\{n\beta\}\) 属于 \((b_3, b_4)\),则取决于是否 \(\{n\beta\}<\dfrac{b_3+b_4}2\), 令 \(n_1=n+n^\prime\)或 \(n+n^{\prime\prime}\), 则由于\(\{n\alpha\}\gt c\gt \max(p,q)\),故 \(\{n_1\alpha\}\lt\{n\alpha\}-\max(p,q)\); 因 \(\{n_1\alpha\}\gt c\), 故 \(\{n\alpha\}\gt c+\max(p,q)\). 如此迭代下去即得矛盾.

最后应该是 \(\{n_1\alpha\}\leqslant \{n\alpha\}-\min(p,q)\); 因 \(\{n_1\alpha\}\gt c\), 故 \(\{n\alpha\}\gt c+\min(p, q)\).

 Posted by at 12:23 am
Nov 262016
 

第 32 届中国数学奥林匹克

湖南 长沙

第一天

(2016 年 11 月 24 日    8:00–12:30)

1. 数列 \(\{u_n\}\), \(\{v_n\}\) 满足: \(u_0=u_1=1\), \(u_n=2u_{n-1}-3u_{n-2}(n\geqslant2)\), \(v_0=a\), \(v_1=b\), \(v_2=c\), \(v_n=u_{n-1}-3u_{n-2}+27v_{n-3}(n\geqslant3)\). 已知存在正整数 \(N\), 使得当 \(n\geqslant N\) 时, \(u_n\mid v_n\). 求证: \(3a=2b+c\).

2. 锐角 \(\triangle ABC\) 中, 外心为 \(O\), 内心为 \(I\). 过点 \(B\), \(C\) 作外接圆的切线交于点 \(L\), 内切圆切 \(BC\) 于点 \(D\), \(AY\) 垂直 \(BC\) 于点 \(Y\), \(AO\) 交 \(BC\) 于点 \(X\), \(PQ\) 为过点 \(I\) 的圆 \(O\) 的直径. 求证: \(P\), \(Q\), \(X\), \(Y\) 共圆等价于 \(A\), \(D\), \(L\) 共线.

3. 将矩形 \(R\) 分为 \(2016\) 个小矩形, 每个小矩形的顶点称为结点, 每个小矩形的边和 \(R\) 平行. 若一条线段的两端为结点, 且线段上没有其他结点, 称之为基本线段. 求遍历所有划分方式时, 基本线段数量的最小值个最大值.

第二天

(2016 年 11 月 25 日    8:00–12:30)
CMO 2017

cmo 2017 day 2

 Posted by at 5:14 pm  Tagged with:
Aug 112016
 

集合

\[\{\sqrt n|n\in\Bbb N\; \text{is Square-free integer}\}\]

在有理数域上线性无关.

这其实是非常古老的问题, 早已经有很一般的结果.

先厘清无平方因子整数Square-free integer这个概念: \(1\) 到底是不是无平方因子整数?

wiki 给出的定义是: 不被不是 \(1\) 的完全平方整除的整数称为无平方因子整数. 因此, \(1\) 算无平方因子正整数. 鉴于此, 我们认为: 无平方因子整数定义为”不被质数的平方整除的整数”更为恰当.

下面的证明来自 Iurie Boreico 的文章 Linear Independence of Radicals.

我们把问题写的更清楚一点, 即我们要证明:

\(n_1\), \(n_2\), \(\dotsc\), \(n_k\) 是互不相同的无平方因子正整数; \(a_1\), \(a_2\), \(\dotsc\), \(a_k\) 都是整数. 令

\[S=a_1\sqrt{n_1}+a_2\sqrt{n_2}+\dotsb+a_k\sqrt{n_k},\]

那么 \(S=0\) 当且仅当 \(a_1=a_2=\dotsb=a_k=0\).

第一个办法是指出更精细的结果:

记 \(p_1\), \(p_2\), \(\dotsc\), \(p_N\) 是 \(n_1n_2\dotsm n_k\) 的所有互不相同的质因子. 则存在

\[S^\prime=b_1\sqrt{m_1}+b_2\sqrt{m_2}+\dotsb+b_l\sqrt{m_l},\]

(这里 \(b_1\), \(b_2\), \(\dotsc\), \(b_l\) 都是整数; \(m_1\), \(m_2\), \(\dotsc\), \(m_l\) 都是无平方因子正整数, 并且都没有 \(p_1\), \(p_2\), \(\dotsc\), \(p_N\) 以外的质因子), 使得 \(SS^\prime\ne0\) 是整数. 进而, 顺水推舟, \(S\ne0\).

对 \(N\) 进行归纳.

明显 \(N=0\) 时, 结论为真: 此刻 \(k=1\), \(n_1=1\), 于是 \(S=a_1\ne0\). 令 \(S^\prime=1\) 即可.

 Posted by at 5:04 pm