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. 第二天的题其实没啥特别, 难度也不大. 题 6 可以推广为更普遍的形式.
  3. 第三题确实有独到之处, 是这个试卷仅有的好题.  可以对 \(m\) 个猎人考虑同样的问题.
  4. 这六个题何以成为史上得分最低的试卷呢! 除了第三题, 别的题为啥得分也不高?
  5. 大陆居然在函数方程载了跟头: 函数方程应该是必须掌握的基本功. 最难的题最可能来自组合, 这没有疑问; 数论的难题虽多, 但能成为竞赛卷子的妙题却不容易; 考场上的几何再难, 也没太大意思.
 Posted by at 2:24 pm  Tagged with:

  2 Responses to “IMO 2017 solutions”

  1. Fantastic! I LOVE your proof of injectivity for Q2. Can I put it up on my blog (provided that I link to this page)?

 Leave a Reply

(required)

(required)