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:
Jul 302016
 

这个续集只聊第 \(3\) 题. 需要的数论的基本知识, 另文写成.

以 \(A_1\) 为反演中心, 以 \(1\) 为反演幂作反演变换. 记 \(A_2\), \(A_3\), \(\dotsc\), \(A_k\) 在此反演变换下的关于 \(A_1\) 的反演点分别是 \(B_2\), \(B_3\), \(\dotsc\), \(B_k\). 显而易见, \(B_2\), \(B_3\), \(\dotsc\), \(B_k\) 在一条直线上, 并且这些点在此直线上的排列就是如此次序,

IMO 2016

IMO 2016 Problem 3 Proof 2

因此,

\begin{equation}B_2B_3+B_3B_4+\dotsb+B_{k-1}B_k=B_2B_k.\end{equation}

既然 \(\triangle A_1B_iB_{i+1}\sim \triangle A_1A_{i+1}A_i\), \(i=2\), \(3\), \(\dotsc\), \(k-1\), 以及 \(\triangle A_1B_2B_k\sim \triangle A_1A_kA_2\), 于是

\begin{equation}\frac{B_iB_{i+1}}{A_iA_{i+1}}=\frac{A_1B_{i+1}}{A_1A_i},\end{equation}

\(i=2\), \(3\), \(\dotsc\), \(k-1\), 以及

\begin{equation}\frac{B_2B_k}{A_2A_k}=\frac{A_1B_k}{A_1A_2}.\end{equation}

设 \(a_j=A_1A_j^2\)(\(j=2\), \(3\), \(\dotsc\), \(k\)), \(b_i=A_iA_{i+1}^2\)(\(i=2\), \(3\), \(\dotsc\), \(k-1\)), 以及 \(c=A_2A_k^2\), 我们可有

\begin{equation}B_iB_{i+1}=\sqrt{\frac{b_{i+1}}{a_ia_{i+1}}},\end{equation}

\(i=2\), \(3\), \(\dotsc\), \(k-1\), 以及

\begin{equation}B_2B_k=\sqrt{\frac{c}{a_2a_k}}.\end{equation}

至此, 出现在眼前的是

\begin{equation}\sum_{i=2}^{k-1}\sqrt{\frac{b_{i+1}}{a_ia_{i+1}}}=\sqrt{\frac{c}{a_2a_k}}.\end{equation}

关键的任务是说明当 \(k\gt3\) 时, 上式不可能为真: 对于 \(n=p^\alpha\)(\(p\) 为奇质数, \(\alpha\) 是正整数), 且 \(P\) 的每条对角线长度的平方不被 \(p^\alpha\) 整除.

为此, 我们需要工具.

这里正在进行的这个证明来自 oneplusone. 他的想法借用了”无平方因子正整数的算术平方根没有非平凡的线性组合”!

我们先写出他的引理:

Lemma 1  如果 \(a_1\), \(a_2\), \(\dotsc\), \(a_n\), \(b\) 都是正有理数, 且

\[\sum_{l=1}^n\sqrt{a_l}=\sqrt b,\]

那么对于任意的奇质数 \(p\), 设 \(t=\min\{v_p(a_l)\}\), 我们有 \(v_p(b)\geq t\).
这里 \(v_p(x)\) 是使得 \(x=p^s\cdot\dfrac uv\) 成立的整数 \(s\), 其中 \(u\), \(v\) 是都与 \(p\) 互质的整数.

背后的工作是单独的一篇短文 \(\{\sqrt n\}\) is linearly independent over the rationals

解答三

\(x\ne0\) 是有理数, 记 \(x=\dfrac ab\), \(a\), \(b\) 都是整数, \(b\ne0\). \(p\) 是质数, 定义 \(v_p(x)=v_p(a)-v_p(b)\).

容易看出 \(v_p(x)\) 的几个简单性质: 对于任意的都不等于 \(0\) 的有理数 \(r_1\), \(r_2\) 和 \(r\), 有

  1. \(v_p(r_1r_2)=v_p(r_1)+v_p(r_2)\). 特别的, \(v_p(r)=\dfrac12v_p(r^2)\); 如果 \(q\) 是与 \(p\) 互质的整数, 则 \(v_p(rq)=v_p(r)\).
  2. \(v_p\Big(\dfrac1r\Big)=-v_p(r)\); 于是有下一条
  3. \(v_p\Big(\dfrac{r_1}{r_2}\Big)=v_p(r_1)-v_p(r_2)\);
  4. 当 \(r_1\pm r_2\ne0\), 有 \(v_p(r_1\pm r_2)\geqslant\min\{v_p(r_1), v_p(r_2)\}\). 特别的, 如果 \(v_p(r_1)\ne v_p(r_2)\), 在 \(r_1\pm r_2\ne0\) 时, 有 \(v_p(r_1\pm r_2)=\min\{v_p(r_1), v_p(r_2)\}\).

下面的解答是贴吧网友 1a2b03c 给出的:

设 \(P\) 的顶点 \(A_1\), \(A_2\), \(\dotsc\), \(A_k\) 依逆时针落在半径为 \(R\) 的 \(\odot O\) 上. 很明显, \(O\) 是有理点(即 \(O\) 的座标都是有理数). 进而, \(R^2\) 为有理数.

记 \(OA_l\) 按逆时针旋转 \(2\alpha_l\) 到\(OA_{l+1}\)(\(0\lt2\alpha_l\lt2\pi\); \(2\alpha_l\) 可以是平角, 也可能大于平角), \(A_lA_{l+1}=2a_l\), \(l=1\), \(2\), \(\dotsc\), \(k\). 我们约定 \(A_{k+1}=A_1\).

显然 \(2\alpha_1+2\alpha_2+\dotsb+2\alpha_k=2\pi\).

不妨认为 \(n=p^\alpha\)(\(p\) 为奇质数, \(\alpha\) 是正整数).

注意对正整数 \(l\), \(1\leqslant l\leqslant k\), 显然 \(\triangle OA_lA_{l+1}\) 的有向面积 \(S_{\triangle OA_lA_{l+1}}=\dfrac12R^2\sin(2\alpha_l)\). 然后, 由 \(S=\sum\limits_{l=1}^kS_{\triangle OA_lA_{l+1}}\),

\begin{equation}2S=2\sum_{l=1}^kS_{\triangle OA_lA_{l+1}}=\sum_{l=1}^kR^2\sin(2\alpha_l).\end{equation}

\(O\), \(A_l\), \(A_{l+1}\) 是有理点蕴涵 \(S_{\triangle OA_lA_{l+1}}\) 为有理数.

第一种情况:  \(v_p(R^2)\geqslant\alpha\).

\(S_{\triangle OA_lA_{l+1}}^2=a_l^2(R^2-a_l^2)\). 结合上面的性质一与四, 在 \(S_{\triangle OA_lA_{l+1}}\ne0\)(其实就是 \(R\gt a_l\) 时),

\begin{equation}\begin{split}v_p\big(S_{\triangle OA_lA_{l+1}}^2\big)&=v_p\big(a_l^2(R^2-a_l^2)\big)\\&=v_p(a_l^2)+v_p(R^2-a_l^2)\\&\geqslant\alpha+\alpha=2\alpha,\end{split}\end{equation}

这是因为

  • 第二个等号是由于第一个性质;
  • \(P\) 的每条边长的平方是 \(p^\alpha\) 的倍数的另一种说法 \(v_p\big(4a_l^2\big)\geqslant\alpha\). 第一个性质表明这就是 \(v_p\big(a_l^2\big)\geqslant\alpha\), 因为 \(p\) 是奇质数.
  • 然后 \(v_p(R^2)\geqslant\alpha\) 与 \(v_p(a_l^2)\geqslant\alpha\), 第四个性质得出 \(v_p(R^2-a_l^2)\geqslant\alpha\).

然后, \((8)\) 表明 \(v_p\big(S_{\triangle OA_lA_{l+1}}\big)\geqslant\alpha\). 换言之, 这其实也就是 \(v_p\Big(\dfrac12R^2\sin(2\alpha_l)\Big)\geqslant\alpha\), 因为显而易见的事实 \(S_{\triangle OA_lA_{l+1}}=\dfrac12R^2\sin(2\alpha_l)\). 故此, \(v_p\Big(R^2\sin(2\alpha_l)\Big)\geqslant\alpha\), 这是由于第一条性质说明 \(v_p\Big(R^2\sin(2\alpha_l)\Big)=v_p\Big(\dfrac12R^2\sin(2\alpha_l)\Big)\).

然后, 由 \((7)\), 并且注意至多只有一个 \(l\), \(1\leqslant l\leqslant k\), 使得 \(S_{\triangle OA_lA_{l+1}}=\dfrac12R^2\sin(2\alpha_l)=0\)(此时 \(A_lA_{l+1}\) 是 \(\odot O\) 的直径), 根据第四条性质可得

\begin{equation}v_p\big(2S\big)=v_p\Big(\sum_{l=1}^kR^2\sin(2\alpha_l)\Big)\geqslant\alpha.\end{equation}

另一种情形 \(v_p(R^2)\lt\alpha\).

记 \(\beta=v_p(R^2)\), 则 \(\beta\lt\alpha\). 既然 \(v_p\big(R^2\big)\lt\alpha\), \(P\) 不可能有任何一条边是 \(\odot O\) 的直径. 换言之, \(2\alpha_l\ne\pi\), 即 \(\alpha_l\ne\dfrac\pi2\), \(l=1\), \(2\), \(\dotsc\), \(k\).

\(S_{\triangle OA_lA_{l+1}}=\dfrac{a_l^2}{\tan\alpha_l}\) 蕴涵 \(\tan\alpha_l\) 是有理数.

另一方面, \(\tan^2\alpha_l=\dfrac{a_l^2}{R^2-a_l^2}\). 性质四表明 \(v_p(R^2-a_l^2)=\beta\); 然后, 性质三证明 \(v_p\Bigg(\dfrac{a_l^2}{R^2-a_l^2}\Bigg)\geqslant\alpha-\beta\) 为真. 我们得到了\(v_p(\tan^2\alpha_l)\geqslant\alpha-\beta\). 记 \(t_l=\tan\alpha_l\), \(l=1\), \(2\), \(\dotsc\), \(k\).  第一个性质表示

\begin{equation}v_p(t_l)\geqslant\frac12(\alpha-\beta).\end{equation}

由 \(1+t_l^2=1+\dfrac{a_l^2}{R^2-a_l^2}=\dfrac{R^2}{R^2-a_l^2}\) 知道

\[v_p(1+t_l^2)=\beta-\beta=0,\]

进而

\begin{equation}v_p\Big(\prod_{l=1}^k(1+t_l^2)\Big)=\sum_{l=1}^kv_p(1+t_l^2)=0.\end{equation}

\begin{equation}f(x)=\prod_{l=1}^k(x+t_l)=\sum_{j=0}^{k-1}s_jx^j+x^k,\end{equation}

这里 \(t_j\) 都是有理数蕴涵 \(s_j\) 亦都为有理数, \(j=0\), \(1\), \(2\), \(\dotsc\), \(k-1\).

然后, \((10)\) 说明了下述事实为真

\begin{equation}v_p(s_j)\geqslant\frac12(k-j)(\alpha-\beta),\end{equation}

\(j=0\), \(1\), \(2\), \(\dotsc\), \(k-1\).

由 \(\alpha_1+\alpha_2+\dotsb+\alpha_k=\pi\) 知道

\[\prod_{l=1}^k(\cos\alpha_l+i\sin\alpha_l)=\prod_{l=1}^k(\cos\alpha_l-i\sin\alpha_l)=-1,\]

\begin{equation}\prod_{l=1}^k(1+it_l)=\prod_{l=1}^k(1-it_l)\ne0,\end{equation}

这就是

\begin{equation}f(i)=(-1)^kf(-i)\ne0.\end{equation}

换句话说, 现在知道

\[\sum_{j=0}^{k-1}s_ji^j+i^k=(-1)^k\big(\sum_{j=0}^{k-1}s_j(-i)^j+(-i)^k\big),\]

\begin{equation}\sum_{j=0}^{k-1}\big(1+(-1)^{k+j-1}\big)s_ji^j=0.\end{equation}

根据 \((7)\), \((15)\), 并注意 \(f(i)\) 与 \(f(-i)\) 都不为 \(0\), 以及熟知的 \(\dfrac{f^\prime(x)}{f(x)}=\sum\limits_{l=1}^k\dfrac1{x+t_l}\), 我们可有

\begin{equation}\begin{split}2S&=R^2\sum_{l=1}^k\sin(2\alpha_l)\\&=R^2\sum_{l=1}^k\frac{2t_l}{1+t_l^2}\\&=-iR^2\sum_{l=1}^k\frac{(1+it_l)-(1-it_l)}{(1+it_l)(1-it_l)}\\&=-iR^2\Bigg(\sum_{l=1}^k\frac1{1-it_l}-\sum_{l=1}^k\frac1{1+it_l}\Bigg)\\&=R^2\Bigg(\sum_{l=1}^k\frac1{i+t_l}+\sum_{l=1}^k\frac1{-i+t_l}\Bigg)\\&=R^2\Bigg(\frac{f^\prime(i)}{f(i)}+\frac{f^\prime(-i)}{f(-i)}\Bigg)\\&=R^2\frac{f^\prime(i)+(-1)^kf^\prime(-i)}{f(i)}\\&=R^2\frac{\Big(\sum\limits_{j=0}^{k-1}js_ji^{j-1}+ki^{k-1}\Big)+(-1)^k\Big(\sum\limits_{j=0}^{k-1}js_j(-i)^{j-1}+k(-i)^{k-1}\Big)}{f(i)}\\&=R^2\frac{\sum\limits_{j=0}^{k-1}\big(1+(-1)^{k+j-1}\big)js_ji^{j-1}}{f(i)}\\&=-R^2\frac{\sum\limits_{j=0}^{k-1}\big(1+(-1)^{k+j-1}\big)\big(k-1-j\big)s_ji^{k+j-1}}{i^kf(i)},\end{split}\end{equation}

最后的等号是因为 \((16)\) 导出 \(\sum\limits_{j=0}^{k-1}\big(1+(-1)^{k+j-1}\big)\big(k-1\big)s_ji^{j-1}=\big(k-1\big)\sum\limits_{j=0}^{k-1}\big(1+(-1)^{k+j-1}\big)s_ji^{j-1}=0\).

当整数 \(j\) 符合 \(0\leqslant j\leqslant k-1\) 时,

  •  \(k+j-1\) 为奇数, 此时 \(1+(-1)^{k+j-1}=0\), 于是 \(\big(1+(-1)^{k+j-1}\big)\big(k-1-j\big)s_ji^{k+j-1}=0\);
  • \(k+j-1\) 是偶数, 此时 \(i^{k+j-1}\) 等于 \(1\) 或 \(-1\), 于是 \(\big(1+(-1)^{k+j-1}\big)\big(k-1-j\big)s_ji^{k+j-1}\) 是 \(s_j\) 与整数的乘积.

总而言之, 在 \(j=0\), \(1\), \(2\), \(\dotsc\), \(k-1\) 之时, \(\big(1+(-1)^{k+j-1}\big)\big(k-1-j\big)s_ji^{k+j-1}\) 为 \(s_j\) 与整数的乘积, 进而 \(\sum\limits_{j=0}^{k-1}\big(1+(-1)^{k+j-1}\big)\big(k-1-j\big)s_ji^{k+j-1}\) 必是有理数. \((17)\) 蕴涵 \(i^kf(i)\) 亦是有理数.

当 \(j=k-2\), 此时 \(1+(-1)^{k+j-1}=0\); 若 \(j=k-1\), 此时 \(k-1-j=0\). 也就是说, 在  \(j=k-2\) 或 \(k-1\) 之时, 必定 \(\big(1+(-1)^{k+j-1}\big)\big(k-1-j\big)s_ji^{k+j-1}=0\). 然而, 当整数 \(j\) 符合 \(0\leqslant j\leqslant k-3\) 时, \((13)\) 说明

\begin{equation}v_p(s_j)\geqslant\frac32(\alpha-\beta).\end{equation}

\(\big(1+(-1)^{k+j-1}\big)\big(k-1-j\big)s_ji^{k+j-1}\) 是 \(s_j\) 与整数的积, 因此

\begin{equation}v_p\Bigg(\sum_{j=0}^{k-1}\big(1+(-1)^{k+j-1}\big)\big(k-1-j\big)s_ji^{k+j-1}\Bigg)=v_p\Bigg(\sum_{j=0}^{k-3}\big(1+(-1)^{k+j-1}\big)\big(k-1-j\big)s_ji^{k+j-1}\Bigg)\geqslant\frac32(\alpha-\beta).\end{equation}

另一方面, \((15)\) 导出

\[\big(i^kf(i)\big)^2=f(i)f(-i)=\prod_{l=1}^k(1+t_l^2).\]

记得 \((11)\),

\begin{equation}v_p\big(i^kf(i)\big)=0.\end{equation}

最后, 由 \((17)\), 利用 \((19)\), \((20)\), 得

\begin{equation}\begin{split}v_p(2S)&=v_p\Bigg(R^2\frac{\sum\limits_{j=0}^{k-1}\big(1+(-1)^{k+j-1}\big)\big(k-1-j\big)s_ji^{k+j-1}}{i^kf(i)}\Bigg)\\&=v_p(R^2)+v_p\Big(\sum_{j=0}^{k-1}\big(1+(-1)^{k+j-1}\big)\big(k-1-j\big)s_ji^{k+j-1}\Big)-v_p\big(i^kf(i)\big)\\&\geqslant\beta+\frac32(\alpha-\beta)-0\gt\alpha.\end{split}\end{equation}

综合 \((9)\), \((21)\), 我们知晓 \(v_p(2S)\geqslant\alpha\) 总是成立的. 换句话, \(2S\) 是被 \(p^\alpha\) 整除的整数.

解答四

从现在开始, 后面的解法将需要一些代数数论的知识.

 Posted by at 5:12 pm  Tagged with:
Jul 112016
 

2016 第 57 届 IMO 解答

Problem 1 (The Kingdom Of Belgium)

IMO 2016

IMO 2016 Problem 1

注意 \(\triangle FAB\), \(\triangle DAC\), \(\triangle EAD\) 是顶角相等的等腰三角形, 即

\[\angle FBA=\angle FAB=\angle DAC=\angle DCA= \angle EAD=\angle EDA.\]

既然 \(\triangle FAB\sim \triangle DAC\), 于是 \(\triangle ABC\sim \triangle AFD\), 进而

\begin{equation}\begin{split}\angle FDC&=180^\circ-\angle ADF-\angle DAC-\angle DCA\\&=180^\circ-\angle ACB-\angle FAB-\angle FBA\\&=\angle FBC=90^\circ,\end{split}\end{equation}

\(D\) 落在以 \(M\) 为心, \(MB\) 为半径的圆上, 即 \(D\), \(F\), \(B\), \(C\) 四点共圆, 并且 \(FC\) 即为此圆的直径. 记这个圆为 \(\Gamma_1\). 然后, \(\angle FBD=\angle FCD=\angle FBA\) 表明 \(FB\) 平分 \(\angle DBA\). 结合 \(AF\) 是 \(\angle DAB\) 的平分线, 我们知道 \(F\) 就是 \(\triangle DAB\) 的内心, 并且 \(DA=DB\), 这是因为

\[\angle DBA=2\angle FBA=\angle DAB.\]

从 \(\angle DBA+\angle DEA =2\angle FAB+\angle DEA=180^\circ\) 得出 \(E\), \(A\), \(B\), \(D\) 四点共圆. \(EA=ED\), 以及 \(F\) 为 \(\triangle DAB\) 的内心蕴涵 \(E\), \(F\), \(B\) 三点共线, \(EF=EA=ED\).

\(M\) 是直角三角形 \(FBC\) 的斜边 \(FC\) 的中点, 因此 \(MF=MB\). 由

\[\angle MFB= \angle FBA+\angle FBA=\angle DAB\]

得出 \(\triangle MFB\sim \triangle DAB\), 进而 \(\angle FMB=\angle ADB\), 于是 \(M\), \(D\), \(A\), \(B\) 四点共圆.  至此, 我们已经明白, \(A\), \(B\), \(M\), \(D\), \(E\) 五点共圆 \(\Gamma_2\). \(\angle ADE=\angle EAD=\angle DAC=\angle BAM\) 说明 \(AE=ED=MD=MB\).

四边形 \(MXEA\) 为平行四边形, \(MX=AE=MB\) 定出 \(X\) 位于以  \(M\) 为心, \(MB\) 为半径的圆上, 即 \(D\), \(F\), \(B\), \(C\), \(X\)  五点共圆

\[\angle DEA+\angle EAC= \angle DEA+(\angle EAD+\angle DAC)=\angle DEA+(\angle EAD+\angle EDA)=180^\circ\]

蕴涵 \(ED\parallel AC\). 既然 \(EX\parallel AC\),  从而 \(E\), \(D\), \(X\) 三点共线.

既然 \(MX=AE=FE\), \(FM\parallel EX\), 从而四边形 \(FMXE\) 为等腰梯形,  四边形 \(FMXE\) 在圆 \(\Gamma_3\) 上.

最后, \(\Gamma_1\), \(\Gamma_2\), \(\Gamma_3\) 两两的根轴 \(BD\), \(FX\), \(ME\) 是相交于同一点.

解答二

Problem 2 ( Australia)

先来指出符合要求的 \(n\) 必须 \(9\mid n\).

事实上, 如果在一张 \(n \times n\) 方格表填入字母 \(I\), \(M\), \(O\) 满足要求, 显然 \(3\mid n\). 令 \(n=3k\), 这里 \(k\) 是正整数. 我们来考察符合下列三个条件之一的所有格子:

  • 第一类: 第 \(2\), \(5\), \(8\), \(\dotsc\), \(3k-1\) 行的所有格子;
  • 第二类: 第 \(2\), \(5\), \(8\), \(\dotsc\), \(3k-1\) 列的所有格子; 以及
  • 第三类: 小方格个数是三的倍数的所有对角线上的全部格子.

注意,  这个\(n \times n\) 方格表中既属于第一类也属于第二类的格子对我们考察的格子的贡献为 \(4\) 次, 而这个方格表其余的格子对我们考察的格子的贡献恰是 \(1\) 次. 由此, 这个\(n \times n\) 方格表中既属于第一类也属于第二类的格子, 也就是这个方格表的第 \(2\), \(5\), \(8\), \(\dotsc\), \(3k-1\) 行; 第 \(2\), \(5\), \(8\), \(\dotsc\), \(3k-1\) 列的交叉处的全部 \(k^2\) 个格子恰有三分之一填入字母 \(I\), 三分之一填入字母 \(M\), 三分之一填入字母 \(O\). 这就迫使 \(3\mid k^2\), 进而 \(3\mid k\). 现在我们清楚 \(9 \mid n\).

现在, 我们说明当 \(9 \mid n\) 之时, 可在一张 \(n \times n\) 方格表填入字母 \(I\), \(M\), \(O\) 满足要求.

当 \(n=9\) 时的构造如下:

IMO 2016

IMO 2016 Problem 2 Proof 1

对于 \(n=9l\) (\(l\) 是正整数), 取 \(l^2\) 个这样的已经填入字母 \(I\), \(M\), \(O\) 的 \(9 \times 9\) 方格表. 然后, 按照每行 \(l\) 个, 每列 \(l\) 个这样的 \(9 \times 9\) 方格表排成一个 \(n \times n\) 的方格表.

对这个 \(l\times l\) 方格表, 其每一行(列)是如上的 \(9 \times 9\) 方格表的某一行(列)重复 \(l\) 次, 因此, 这个\(l\times l\) 方格表, 其每一行(列)有同样数目的字母 \(I\), \(M\), \(O\).

这个 \(l\times l\) 方格表的任一条数目是三的倍数的对角线穿过了一些 \(9 \times 9\) 方格表. 既然小方格 \((i,j)\) 在有三的倍数个数的小方格的某条对角线上, 当且仅当 \(i\equiv j\pmod 3\) 或 \(i+j\equiv 1\pmod 3\), 于是此 \(l\times l\) 方格表的对角线在这样的一个 \(9 \times 9\) 方格表内的部分恰是这 \(9 \times 9\) 方格表的一条数目是三的倍数的对角线, 因此这部分, 进而这个 \(l\times l\) 方格表的任一条数目是三的倍数的对角线, 有同样数目的字母 \(I\), \(M\), \(O\).

综上所述, 我们寻找的所有符合要求的正整数 \(n\) 恰是 \(9\) 的倍数的全体正整数.

Problem 3 ( Russia)

这是本届赛事最难的题, 只有 10 份考卷写出了正确的答案.

这个题的路途是有多种工具, 尤其如果允许稍微一点点的代数数论.

结果可以稍微加强:

设圆内接多边形 \(P=A_1A_2\dotsm A_k\) 的面积为 \(S\), 且对于任意三角形 \(A_iA_jA_l\)(\(1\leqslant i\lt j\lt l\leqslant k\)), 其面积 \(S_{\triangle A_iA_jA_l}\) 满足 \(2S_{\triangle A_iA_jA_l}\) 是正整数. 设 \(n\) 是一个正奇数, 满足 \(P\) 的每条边的长度的平方是被 \(n\) 整除的正整数, 且 \(P\) 的每条对角线长度的平方是正整数. 那么, \(2S\) 是正整数, 且被 \(n\) 整除.

只要指出, 对于 \(n=p^\alpha\), 结论为真即可(\(p\) 为奇质数, \(\alpha\) 是正整数).

对 \( k\) 进行归纳.

在 \( k=3\) 的时刻, 记 \(P\) 的边长为 \(a\), \(b\), \(c\). 根据 \(n\mid(a^2, b^2, c^2)\) 以及

\[16S^2=2a^2b^2+2b^2c^2+2c^2a^2-a^4-b^4-c^4\]

得 \(n^2\mid 16S^2\), 也就是 \(n^2\mid (4S)^2\). 于是 \(n\mid (4S)\), 进而 \(n\mid (2S)\).

假定当 \(k\) 是满足 \(3\leqslant k\lt m\) 时 (\(m\geqslant4\) 是正整数), \(n\mid (2S)\). 我们来考察 \(k=m\).

\[A_iA_j^2=p^{\alpha_{ij}}z_{ij},\;\alpha_{ij}\in\Bbb N,\; z_{ij}\in\Bbb N, \;\big(z_{ij}, p\big)=1, \; 1\leqslant i\lt j\leqslant m,\]

这里 \(\Bbb N\) 为全部非负整数组成的集合. 于是, 当 \(j=i+1\) 时, \(\alpha_{ij}\geqslant \alpha\). 这里, 我们认为 \(A_{m+1}=A_1\).

\[u=\max\{\alpha_{ij}, \; 1\leqslant i\lt j\leqslant m,\; j-i\gt1\}.\]

我们指出, 必有 \(u\geqslant \alpha\).

如若不然, \(0\leqslant u\lt \alpha\). 记 \(v=\min\{\alpha_{ij}, \; 1\leqslant i\lt j\leqslant m,\; j-i\gt1\}\). 选择两个符合 \(1\leqslant i\lt j\leqslant m\), \(j-i\gt1\) 的正整数 \(i\), \(j\), 使得 \(p^v\parallel A_iA_j^2\). 观察四边形 \(A_{i-1}A_iA_{i+1}A_j\)(约定 \(A_0=A_m\)):

IMO 2016

IMO 2016 Problem 3 Proof 1

Ptolemy 定理给出

\[ab+cd=ef.\]

两端平方

\[a^2b^2+c^2d^2+2abcd=e^2f^2.\]

可见, \(2abcd\) 是正整数. 注意,

\[2abcd=2\sqrt{p^{\alpha_{(i-1)i}+\alpha_{(i+1)j}+\alpha_{i(i+1)}+\alpha_{(i-1)j}}z_{(i-1)i}z_{(i+1)j}z_{i(i+1)}z_{(i-1)j}}=2p^{\alpha+v}\sqrt z, \]

这里 \(z=p^{\alpha_{(i-1)i}+\alpha_{(i+1)j}+\alpha_{i(i+1)}+\alpha_{(i-1)j}-2\alpha-2v}z_{(i-1)i}z_{(i+1)j}z_{i(i+1)}z_{(i-1)j}\) 是正整数. 于是,  正整数的算术平方根 \(\sqrt z\) 是有理数, 进而, 是正整数. 从而 \(p^{\alpha+v}\mid 2abcd\).

显而易见, \(p^{\alpha+v}\mid a^2b^2\), \(p^{\alpha+v}\mid c^2d^2\) 蕴涵 \(p^{\alpha+v}\mid e^2f^2\). 这是不可能的: \(p^v\parallel f^2\), \(a_{(i-1)(i+1)}\lt\alpha\).

既然 \(u\geqslant \alpha\), 也就是说 \(P\) 的至少一条对角线长度的平方是被 \(p^\alpha\) 整除. 于是, 这对角线把 \(P\) 分为两个小的圆内接多边形 \(P_1\) 和 \(P_2\). 记 \(P_1\) 和 \(P_2\) 的面积分别 \(S_1\) 和 \(S_2\). 于是 \(p^\alpha\mid (2S_1)\), \(p^\alpha\mid (2S_2)\). 然后 \(p^\alpha\mid (2S_1+2S_2)\), 此即 \(p^\alpha\mid (2S)\). 至此, 我们完成了理想.

Problem 4 (Luxembourg)

当 \(n\in\Bbb N\), 则

  1. \(\big(P(n),P(n+1)\big)=1\);
  2. \(\big(P(n),P(n+2)\big)\mid7;\;\big(P(n),P(n+2)\big)=7 \iff   n\equiv 2\pmod 7\);
  3. \(\big(P(n),P(n+3)\big)\mid3;\;\big(P(n),P(n+3)\big)=3 \iff  n \equiv 1 \pmod3\);
  4. \(\big(P(n),P(n+4)\big)\mid19;\;\big(P(n),P(n+4)\big) = 19 \iff  n \equiv 7 \pmod{19}\).

选择正整数 \(a\), 使得

\[a \equiv 7\pmod{19},\; a+1 \equiv 2\pmod7,\;  a+2 \equiv 1\pmod 3,\]

这样的 \(a\) 可以

\[\big(P(a),P(a+4)\big)=19,\; \big(P(a+1),P(a+3)\big)=7,\; \big(P(a+2),P(a+5)\big)=3.\]

于是, \(b=6\) 符合要求.

事实 1 不仅表示 \(b\gt2\), 也说明 \(b=3\) 不可能: \(P(a+1)\), \(P(a+2)\), \(P(a+3)\) 中的 \(P(a+2)\) 与另外两个元素都互素.

\(P(a+1)\), \(P(a+2)\), \(P(a+3)\), \(P(a+4)\), 因为 \(\big(P(a+1),P(a+3)\big)=7\) 与 \(\big(P(a+2),P(a+4)\big)=7\) 不能同时成立, 故 \(b=4\) 不可能存在非负整数 \(a\) 满足要求.

对于 \(P(a+1)\), \(P(a+2)\), \(P(a+3)\), \(P(a+4)\), \(P(a+5)\), 由于 \(P(a+3)\) 与 \(P(a+2)\) 以及 \(P(a+4)\) 都互素, 如果 \(P(a+3)\) 与 \(P(a+1)\) 以及 \(P(a+5)\) 的一个不互素, 则必定 \(7\mid P(a+3)\), \(P(a+2)\) 以及 \(P(a+4)\) 都不是 \(7\) 的倍数, 进而 \(\big(P(a+2),P(a+4)\big)=1\). 注意

\[ \big(P(a+2),P(a+5)\big)=3,\; \big(P(a+1),P(a+4)\big)=3\]

不能同时为真, 因此 \(b=5\) 不可能存在非负整数 \(a\) 满足要求.

Lemma 1   当 \(n\) 为正整数, \(9\not\mid P(n) \).

事实上, 注意

\[4(n^2+n+1)=(2n+1)^2+3,\]

无论 \(3\mid (2n+1) \) 与否, 都有 \(9\not\mid \big((2n+1)^2+3\big) \). 因此, \(9\not\mid P(n) \).

Lemma 2   当 \(n\), \(m\) 都是正整数,  \(\big(P(n),P(n+m)\big)\mid (m^3+3m)\).

首先, \(P(n+m)-P(n)=m^2+2nm+m\), 以及

\begin{equation}\begin{split}n\big(P(n+m)-P(n)\big)-2mP(n)&=\big(2mn^2+(m^2+m)n\big)-\big(2mn^2+2mn+2m\big)\\&=\big(m^2-m\big)n-2m.\end{split}\end{equation}

于是 \(\big(P(n),P(n+m)\big)\mid \big(X, Y\big)\), 这里 \(X=m^2+2nm+m\), \(Y=\big(m^2-m\big)n-2m\). 然后

\[\big(m-1\big)X-2Y=\big(m-1\big)(m^2+2nm+m)-2\Big(\big(m^2-m\big)n-2m\Big)=m^3+3m.\]

Lemma 3  命 \(p\) 为素数. 同余方程

\[x^2+a_1x+a_0\equiv 0\pmod p\]

之解数 \(\leqslant 2\).

Lemma 4  当整数 \(t \equiv n, n^2\pmod{P(n)}\), 必定 \(P(t) \equiv 0 \pmod{P(n)}\).

事实上, 在 \(t \equiv n^2 \pmod {P(n)}\) 时,

\[P(t)\equiv n^4 + n^2 + 1 =  (n^2-n+1)  (n^2+n+1) \equiv 0  \pmod {P(n)}.\]

于是,
\(n \equiv 1 \pmod 3\), 则 \(P(n) \equiv 0 \pmod 3\);
\(n \equiv 2,4 \pmod 7\), 则 \( P(n)\equiv 0 \pmod 7\);
\(n\equiv7, 49\pmod{57}\), 则 \( P(n)\equiv 0\pmod {57}\). 这导致当 \(n\equiv 7, 11\pmod {19}\) 时, 有 \(P(n)\equiv0\pmod{19}\)

至此, 结合 Lemma 3, 并且注意 \(n \equiv 0, 2 \pmod 3\) 蕴涵 \(3\not\mid P(n) \), 以及 Leamma 1, 2 揭示 \(\big(P(n),P(n+1)\big)=1\), \(\big(P(n),P(n+2)\big)\mid7\),\(\big(P(n),P(n+3)\big)\mid3\), \(\big(P(n),P(n+4)\big)\mid19\). 断言事实 1, 2, 3, 4 为真.

Problem 5 ( Russia)

既然 \(x-1\), \(x-2\), \(\dotsc\), \(x-2016\) 都在方程两边恰出现一次, 因此, 欲使得到的方程无实数解, 这 \(2016\) 个一次因式中的每个至多只能在两边出现一次, 即等号两边要擦去至少这 \(2016\) 个一次因式各一次. 故此, \(k\geqslant2016\).

下面我们来指出: 擦去左边所有形如 \(x-(4t-2)\), \(x-(4t-1)\), 右边所有形如 \(x-4t\), \(x-(4t-3)\)(即 \(t=1\), \(2\), \(\dotsc\), \(504\)) 的因式后, 得到的方程

\begin{equation}\begin{split}&\hspace3.25ex(x-1)(x-4)(x-5)(x-8)\dotsm(x-2013)(x-2016)\\&=(x-2)(x-3)(x-6)(x-7)\dotsm(x-2014)(x-2015)\end{split}\end{equation}

无实数根.

事实上, 注意下列 \(504\) 个不等式都是对任意实数 \(x\) 为真:

\begin{equation}\begin{split}
(x-1)(x-4)&\lt(x-2)(x-3);\\
(x-5)(x-8)&\lt(x-6)(x-7);\\
&\vdots\\
(x-2013)(x-2016)&\lt(x-2014)(x-2015).\end{split}\end{equation}

当 \(x\lt1\), \(x\gt2016\), 或存在正整数 \(m\)(\(1\leqslant m\leqslant503\)), 使得 \(4m\lt x\lt4m+1\), 这三种情况之一为真, 上面的 \(504\) 个不等式的两边都为正, 当然 \(x\) 不是方程 \((3)\) 的实数根; 当 \(x\in\{1, 2, 3, \dotsc, 2016\}\) 之时, \((3)\) 的一边为 \(0\), 一边非 \(0\), 因此 \(x\) 不是实数根; 当存在正整数 \(n\)(\(1\leqslant n\leqslant504\)), 使得 \(4n-3\lt x\lt4n-2\) 或 \(4n-1\lt x\lt4n\), 上面的第 \(n\) 个不等式的左边为负, 右边为正, 其余的 \(503\) 个不等式的两边都为正, 因此 \(x\) 不是方程 \((3)\) 的实数根.

剩下的任务, 是解释当 \(x\) 满足 \(4n-2\lt x\lt4n-1\)(\(n\) 是符合 \(1\leqslant n\leqslant504\) 的正整数)时, \(x\) 依旧不是方程 \((3)\) 的根.

注意到下列 \(503\) 个不等式都是对任意实数 \(x\) 为真:

\begin{equation}\begin{split}
(x-4)(x-5)&\gt(x-3)(x-6);\\
(x-8)(x-9)&\gt(x-7)(x-10);\\
&\vdots\\
(x-2012)(x-2013)&\gt(x-2011)(x-2014).\end{split}\end{equation}

当 \(x\) 符合 \(2\leqslant 4n-2\lt x\lt4n-1\leqslant2015\)(\(1\leqslant n\leqslant504\)) 时, (\(5\)) 中的 \(503\) 个不等式的两边都为正, 并且

\[ x-1\gt x-2\gt0,\]

\[-(x-2016)\gt-(x-2015)\gt0.\]

进而, 我们发现

\begin{equation*}-(x-1)(x-4)(x-5)(x-8)\dotsm(x-2013)(x-2016)\gt-(x-2)(x-3)(x-6)(x-7)\dotsm(x-2014)(x-2015)\end{equation*}

因此, 满足 \(4n-2\lt x\lt4n-1\)(\(n\) 是符合 \(1\leqslant n\leqslant504\) 的正整数) 的 \(x\) 不是方程 \((3)\) 的根.

综合起来, 符合要求的正整数 \(k\) 的最小值为 \(2016\).

Problem 6 (The Czech Republic)

可以认为这 \(n\) 条线段是圆的 \(n\) 条弦, 这些弦两两在圆内相交, 任三条弦不交于同一点(否则, 取一个足够大的圆, 使得全部的 \(n\) 条线段都在圆内. 用这些线段所在的直线被这个圆所截的弦来代替这 \(n\) 条线段).

把这 \(n\) 条弦的所有端点依逆时针记为 \(P_1\), \(P_2\), \(\dotsc\), \(P_{2n}\)(下面, 当整数 \(x\), \(y\) 满足 \(x\equiv y\pmod{2n}\) 时, \(P_x\), \(P_y\) 是同一点).

注意, \(P_i\), \(P_{i+n}\) 是同一条弦的两个端点, \(i=1\), \(2\), \(\dotsc\), \(n\).

这是因为, 对于任意两条相交弦, 任意一条的两个端点一定不在另一条的同一侧. 于是, 对于这 \(n\) 条弦的任意一条, 其一侧恰有剩下的 \(n-1\) 条弦的每条弦的一个端点, 另一侧亦有其余的这 \(n-1\) 条弦的每条弦的一个端点. 从而, 任意一条弦的任一侧恰有剩下的 \(n-1\) 条弦的全部 \(2(n-1)\) 个端点中的 \(n-1\) 个, 即线段 \(P_iP_{i+n}\) 是这 \(n\) 条弦中之一.

(a) 在 \(n\) 为奇数, 把青蛙放在 \(P_1\), \(P_3\), \(\dotsc\), \(P_{2n-1}\), 可以实现他的愿望.

首先, 这 \(n\) 个点中的任意两个, 不可能是同一条弦的两个端点. 因为当且仅当整数 \(x\), \(y\) 满足 \(x\equiv y\pmod n\) 时, \(P_x\), \(P_y\) 是同一条弦的端点(包括重合). 在正整数 \(i\), \(j\in\{1, 3, 5, \dotsc, 2n-1\}\), \(i\ne j\), 必定 \(i-j\ne0\), \(-2n\lt i-j\lt2n\). \(i-j\) 是偶数, \(n\) 为奇数蕴涵 \(i-j\ne n\), \(-n\). 故而 \(i\not\equiv j\pmod n\), 即 \(P_i\), \(P_j\) 不是同一条弦的两个端点.

杰夫能实现他的愿意.

事实上, 记 \(P_i\), \(P_j\) 是 \(P_1\), \(P_3\), \(\dotsc\), \(P_{2n-1}\) 中的任意两点. 设弦 \(P_iP_{i+n}\) 与 \(P_jP_{j+n}\) 的交点为 \(A\).

\(P_i\), \(P_j\) 之间有奇数个点(不包括这两点本身). 这奇数个点组成集合 \(S\). 不以 \(S\) 中的点为端点的弦如果与线段 \(P_iA\), \(P_jA\) 中的一个相交, 则必定也与另一个相交, 因为此弦的端点不属于 \(S\), 即不能在\(P_i\), \(P_j\) 之间; 以 \(S\) 中的点为端点的弦必定与线段 \(P_iA\), \(P_jA\) 中的恰好一个相交. \(S\) 有奇数个点, 这表明线段 \(P_iA\), \(P_jA\) 与所有的 \(n\) 条弦的交点个数的奇偶性不同. 进而, 从 \(P_i\), \(P_j\) 出发的青蛙, 任何时刻都不会落在同一个交点.

(b) 杰夫想实现他的理想的话, 青蛙不能放在圆上相邻的端点.

事实上, 记 \(P_i\), \(P_{i+1}\) 是 \(P_1\), \(P_2\), \(\dotsc\), \(P_{2n}\) 中相邻的两点, 即 \(i\in\{1, 2, 3, \dotsc, 2n\}\). 设弦 \(P_iP_{i+n}\) 与 \(P_{i+1}P_{i+1+n}\) 的交点为 \(B\).

所有的 \(n\) 条弦的任意的一条, 如果与线段 \(P_iB\), \(P_{i+1}B\) 中的一个相交, 则必定也与另一个相交, 鉴于此弦的端点不能在\(P_i\), \(P_{i+1}\) 之间. 于是, 线段 \(P_iB\), \(P_{i+1}B\) 与所有的 \(n\) 条弦的交点个数相同. 进而, 从 \(P_i\), \(P_{i+1}\) 出发的青蛙, 会在某个时刻落在同一个交点.

既然青蛙不能放在圆上相邻的端点, 于是, 青蛙只能全部放在 \(P_1\), \(P_3\), \(\dotsc\), \(P_{2n-1}\) 或 \(P_2\), \(P_4\), \(\dotsc\), \(P_{2n}\). 记住 \(n\) 是偶数, 在前一种情况, \(P_1\), \(P_{n+1}\) 有青蛙; 在后一种情况, \(P_2\), \(P_{n+2}\) 有青蛙. 不幸的悲剧是,  \(P_1\), \(P_{n+1}\) 或 \(P_2\), \(P_{n+2}\) 都是一条弦的两个端点.

Annotations

  1. 今年的题, 如果时间充裕一点, 应该都能做出来
  2. 又一次的证明, 出现精彩万分的数论题是多么不容易.
  3. 最好的题是第 3 题, 毫无疑问. 本题需要一点智慧. 如果知道一点代数数论, 本题是有好几种突破口, 请参看续集 IMO 2016 solutions II.
  4. 题 6 不适合作为 Q3 或 Q6, 难度不够, 似乎比 Q2 容易.
 Posted by at 2:44 pm  Tagged with:
Jul 112016
 

                                      Day \(1\)

 Monday, July 11, 2016

Problem 1. Triangle \(BCF\) has a right angle at \(B\). Let \(A\) be the point on line \(CF\) such that \(FA=FB\) and \(F\) lies between \(A\) and \(C\). Point \(D\) is chosen so that \(DA=DC\) and \(AC\) is the bisector of \(\angle DAB\). Point \(E\) is chosen so that \(EA=ED\) and \(AD\) is the bisector of \(\angle EAC\). Let \(M\) be the midpoint of \(CF\). Let \(X\) be the point such that \(AMXE\) is a parallelogram(where \(AM\parallel EX\) and \(AE\parallel MX\)). Prove that \(BD\), \(FX\) and \(ME\) are concurrent.

Problem 2. Find all positive integers \(n\) for which each cell of \(n \times n\) table can be filled with one of the letters \(I\), \(M\) and \(O\) in such a way that:

  • in each row and each column, one third of the entries are \(I\), one third are \(M\) and one third are \(O\); and
  • in any diagonal, if the number of entries on the diagonal is a multiple of three, then one third of the entries are \(I\), one third are \(M\) and one third are \(O\).

Note. The rows and columns of an \(n\times n\) table are each labelled \(1\) to \(n\) in a natural order. Thus each cell corresponds to a pair of positive integer \((i\), \(j)\) with \(1 \leqslant i\), \(j\leqslant n\). For \(n\gt 1\), the table has \(4n-2\) diagonals of two types. A diagonal of first type consists all cells \((i\), \(j)\) for which \(i+j\) is a constant, and the diagonal of this second type consists all cells \((i\), \(j)\) for which \(i-j\) is constant.

Problem 3. Let \(P=A_1A_2\dotsm A_k\) be a convex polygon in the plane. The vertices \(A_1\), \(A_2\), \(\dotsc\), \(A_k\) have integral coordinates and lie on a circle. Let \(S\) be the area of \(P\). An odd positive integer \(n\) is given such that the squares of the side lengths of \(P\) are integers divisible by \(n\). Prove that \(2S\) is an integer divisible by \(n\).

                                      Day \(2\)

 Tuesday, July 12, 2016

Problem 4. A set of postive integers is called fragrant if it contains at least two elements and each of its elements has a prime factor in common with at least one of the other elements. Let \(P(n)=n^2+n+1\). What is the least possible positive integer value of \(b\) such that there exists a non-negative integer \(a\) for which the set

\[\{P(a+1),P(a+2),\dotsc,P(a+b)\}\]

is fragrant?

Problem 5. The equation

\[(x-1)(x-2)\dotsm(x-2016)=(x-1)(x-2)\dotsm (x-2016)\]

is written on the board, with \(2016\) linear factors on each side. What is the least possible value of \(k\) for which it is possible to erase exactly \(k\) of these \(4032\) linear factors so that at least one factor remains on each side and the resulting equation has no real solutions?

Problem 6. There are \(n\geqslant 2\) line segments in the plane such that every two segments cross, and no three segments meet at a point. Geoff has to choose an endpoint of each segment and place a frog on it, facing the other endpoint. Then he will clap his hands \(n-1\) times. Every time he claps, each frog will immediately jump forward to the next intersection point on its segment. Frogs never change the direction of their jumps. Geoff wishes to place the frogs in such a way that no two of them will every occupy the same intersection point at the same time.

(a) Prove that Geoff can always fulfill his wish if \(n\) is odd.

(b) Prove that Geoff can never fulfill his wish if \(n\) is even.

 Posted by at 2:04 pm  Tagged with:
Aug 032015
 

第一篇文章有 Problem 3 的几个证明. 第三个证明利用了调和四边形的一些很基本的性质. 第五个证明,  \(M\) 是三角形 \(HYK\) 的外接圆的切线的交点以及 \(F\) 是 \(HY\) 的中点这两件事导出

\[\angle MKH=\angle YKF.\]

这是需要证明的, 并不容易. 不过, 这个结果已经很流行了. 田廷彦在他的”圆”的第三讲有一个例题对锐角三角形的情形给出了两个证明, 但都不能让人满意, 因为都用到了三角函数.

虽然这些知识不是参加竞赛必须掌握, 但如果参赛者想在考场上取得好的分数, 应该不仅仅是记得一些常用的结论, 还要对证明也很熟练.

 Posted by at 12:31 pm  Tagged with:
Jul 232015
 

这个续集只聊第 \(6\) 题. 这个问题和 Siteswap 有关.

一个杂耍师在表演一种抛球的杂技. 表演开始, 杂技师往空中抛出一个球. 球在第 \(1\) 秒爬升到 \(a_1\) 的高度. 以后, 每过 \(1\) 秒, 这个球高度降低 \(1\). 那么, 球离开杂技师 \(a_1\) 秒之后, 也就是在表演开始后的第 \(1+a_1\) 秒, 这个球将回到杂耍师手中. 第一个球回到杂耍师的时间记为 \(d_1\), 即 \(d_1=1+a_1\).

杂耍师在抛出第一个球之后, 每过 \(1\) 秒, 他都要抛出一个球.
如果 \(1+a_1=2\), 即 \(a_1=1\) 之时, 第一个球在第 \(2\) 秒回到他的手中. 于是, 杂耍师可以把这个球再次的抛向高空.
如果 \(1+a_1\gt2\), 即 \(a_1\gt1\) 之时, 第一个球在第 \(2\) 秒不能回到他的手中. 这时, 杂耍师需要一个新球, 并且把这个新球往空中抛出.
无论杂技师在第 \(2\) 秒抛出的是第一个球还是新球, 这个球都会飞速在第 \(2\) 秒到达海拔 \(a_2\). 以后, 这个球的高度每过 \(1\) 秒降低 \(1\), 因此将在第 \(2+a_2\) 秒回到他的手中. 记 \(d_2=2+a_2\). \(d_2\ne d_1\) 蕴涵前两次抛出的球不会同时落地, 因此当然不在同一高度.

杂耍师在第 \(3\) 秒要抛出一个球.
如果 \(d_1=3\) 或 \(d_2=3\), 第一次或第二次抛出的球此时会回到杂耍师手中, 因此, 他可以把回来的球抛出.
如果 \(d_1\ne3\) 并且 \(d_2\ne3\), 没有球回来, 杂耍师把一个新球抛出.
无论杂技师在第 \(3\) 秒抛出的是旧球还是新球, 这个球都会在第 \(3\) 秒飞速到达海拔 \(a_3\). 以后, 这个球的高度每过 \(1\) 秒降低 \(1\), 因此将在第 \(3+a_3\) 秒回到他的手中. 记 \(d_3=3+a_3\). \(d_1\),\(d_2\), \(d_3\) 互不相等蕴涵空中的球不会同时落地, 因此当然不在同一高度.

杂耍师的表演一直这样继续, 直至海枯石烂. 他在第 \(k\) 秒要抛出一个球, 这里 \(k\) 是正整数.
记 \(d_j=a_j+j\), \(j=1\), \(2\), \(\dotsc\). 注意, \(d_1\), \(d_2\), \(\dotsc\) 两两不等.
如果有某个正整数 \(j\lt k\) 使得 \(d_j=k\), 第 \(j\) 秒抛出的球此时会回到杂耍师手中. 因此, 他可以把回来的球抛出. 否则, 没有球回来, 杂耍师把一个新球抛出.
无论杂技师在第 \(k\) 秒抛出的是旧球还是新球, 这个球都会在第 \(k\) 秒飞速到达海拔 \(a_k\). 以后, 这个球的高度每过 \(1\) 秒降低 \(1\), 因此将在第 \(k+a_k\) 秒回到他的手中. \(d_1\),\(d_2\), \(\dotsc\), \(d_k\) 互不相等表明空中的球不会同时落地, 因此当然不在同一高度: 如果 \(d_j\geqslant k\)(\(1\leqslant j\leqslant k\)), 第 \(j\) 秒抛出的球在第 \(k\) 秒的高度是 \(a_j-(k-j)=a_j+j-k\)(高度是 \(0\) 的意思是球回到杂耍师手上).

杂耍师不会需要无穷多个新球. 实际上, 他至多需要 \(2015\) 个球就可以永远站在舞台上卖力表演. 这是因为空中抛出的球的高度都不超过 \(2015\) 并且互不相同, 每个球经过至多 \(2015\) 秒就会回到他的手中.
设杂耍师用了 \(b\) 个球. 当然, \(1\leqslant b\leqslant2015\). 把这 \(b\) 个球的初次被抛出的时间记为 \(t_1\), \(t_2\), \(\dotsc\), \(t_b\). 于是, \(t_1\), \(t_2\), \(\dotsc\), \(t_b\) 恰是 \(d_1\), \(d_2\), \(\dotsc\) 不能取到的全部正整数.

我们用 \(S_j\) 表示第 \(j\) 秒空中所有的球的高度之和(第 \(j\) 秒, 杂耍师抛出的球已经到达海拔 \(a_j\). 在 \(j\geq2\), 第 \(j-1\) 秒高度为 \(1\) 的球在第 \(j\) 秒已经回到杂技师手中并且已被抛到高度 \(a_j\), 第 \(j-1\) 秒高度不低于 \(2\) 的球的高度在第 \(j\) 秒都已降低 \(1\)), \(j=1\), \(2\), \(3\), \(\dotsc\). 注意 \(S_1=a_1\).

取定一个正整数 \(N\geqslant\max\{t_1, t_2, \dotsc, t_b\}\).

当 \(j\geqslant N\), 在第 \(j\) 秒, 杂耍师完成把一个球抛到海拔 \(a_j\) 后, 空中有 \(b\) 个球, 这些球的高度互不相同, 并且恰好有一个球的高度是 \(1\), 因为第 \(j+1\) 秒恰好有一个球回到杂耍师手中(就是第 \(i\) 秒抛出的那个球, \(i\) 使得 \(d_i=j+1\)). 于是, \(S_j\) 是 \(b\) 个互不相同的数的和: 有一个是 \(1\), 有 \(b-1\) 个属于 \(\{2, 3, 4, \dotsc, 2015\}\).

既然第 \(j\) 秒, 高度是 \(1\) 的球会在第 \(j+1\) 秒被抛到海拔 \(a_{j+1}\), 高度 \(\gt1\) 的 \(b-1\) 个球都在第 \(j+1\) 秒海拔降低 \(1\), 因此

\begin{equation}S_{j+1}-S_j=a_{j+1}-1-\left(b-1\right)=a_{j+1}-b.\end{equation}

至此, 对于任意满足 \(n\gt m\geqslant N\) 的正整数 \(m\) 和 \(n\), 有

\begin{equation}S_n-S_m=\sum_{j=m+1}^n\Big(a_j-b\Big).\end{equation}

注意, \(S_n\) 和 \(S_m\) 都是 \(\{1, 2, 3,\dotsc,2015\}\) 中包括 \(1\) 在内的 \(b\) 个互不相同的数的和, 所以

\begin{equation}\begin{split}
\left|S_n-S_m\right|&\leqslant\Big(1+2015+2014+\dotsb+(2017-b)\Big)-\Big(1+2+3+\dotsb+b\Big)\\&=\Big(2015-b\Big)\Big(b-1\Big)\leqslant1007^2.\end{split}\end{equation}

我们下面来把这个证明改写成”纯”, “完全彻底” 的数学论证. 有几个选择, 不过繁简有微小差别, 虽然实质一样.

解答三

对每个整数 \(j\geq1\), 令

\begin{equation}\mathfrak A_j=\{a_k+k-j\mid1\leq k\leq j,\;a_k+k\gt j\}.\end{equation}

显然, \(a_j\in \mathfrak A_j\).

注意, \(1\leq k\leq j\) 时,

\[a_k+k-j\leq a_k\leq2015\]

蕴涵 \(1\leq|\mathfrak A_j|\leq 2015\).

另一方面, \(1\leq k\leq j\) 时,

\[\Big(a_k+k-j\Big)-1=\Big(a_k+k\Big)-\Big(j+1\Big)\ne a_{j+1}\]

蕴涵 \(a_{j+1}\notin\{x-1\mid x\in \mathfrak A_j\}\).

当 \(1\notin \mathfrak A_j\) 时,

\[\mathfrak A_{j+1}=\{x-1\mid x\in \mathfrak A_j\}\cup\{a_{j+1}\}.\]

此时, \(|\mathfrak A_{j+1}|= |\mathfrak A_j|+1\).

当 \(1\in \mathfrak A_j\) 时,

\[\mathfrak A_{j+1}=\{x-1\mid x\gt1,\; x\in \mathfrak A_j\}\cup\{a_{j+1}\}.\]

此时, \(|\mathfrak A_{j+1}|= |\mathfrak A_j|\).

无论如何, \(|\mathfrak A_{j+1}|\geq |\mathfrak A_j|\) 为真. 于是, 存在正整数 \(N\), 使得对任意整数 \(j\geq N\), \(|\mathfrak A_j|\) 都是同一个数. 记这个不变的数是 \(b\), 即 \(b=|\mathfrak A_N|\). 注意, \(j\geq N\), \(|\mathfrak A_j|\) 不变蕴涵 \(1\in\mathfrak A_j\).

考察 \(S_j=\sum\limits_{h\in\mathfrak A_j}\)h, \(j\geq1\).

当 \(j\geq N\), 照样有 \((1)\),  \((2)\),  \((3)\).

解答四

考察 \(d_j=a_j+j\),  \(j=1\), \(2\), \(\dotsc\). 于是, 正整数序列 \(d_1\), \(d_2\), \(\dotsc\) 互不相同, 并且对每个正整数 \(j\geqslant1\), 有 \(j+1\leqslant d_j\leqslant j+2015\).

显然, 肯定有正整数不会在序列 \(\{d_j\}\) 中出现, 比如 \(1\). 我们指出, 至多有 \(2015\) 个正整数 \(t\), 使得不存在正整数 \(j\), 满足 \(d_j=t\). 换句话说, 集合 \(\{1, 2, 3, \dotsc\}\setminus\{d_1, d_2,\dotsc\}\) 的元素个数 \(b\), 成立 \(1\leqslant b\leqslant 2015\).

设 \(t_1\), \(t_2\), \(\dotsc\), \(t_c\) 是没有在序列 \(\{d_j\}\) 中出现的 \(c\) 个正整数, 这里 \(c\) 是正整数. 对每一个 \(t_i\), \(1\leqslant i\leqslant c\), 考察如下的正整数序列

\begin{equation}x_0=t_i,\; x_j=d_{x_{j-1}},\; j\geqslant1. \end{equation}

我们把这个序列称为由 \(t_i\) 出发的 \(d\) 序列. 如此一来, 这样的 \(d\) 序列有 \(c\) 个. 序列 \(d_1\), \(d_2\), \(\dotsc\) 互不相同说明任意两个 \(d\) 序列不会出现相同的项.

显然, 对每个正整数 \(j\geqslant1\), \(x_j\) 会在序列 \(\{d_j\}\) 中出现, 并且 \(x_j=d_{x_{j-1}}\gt x_{j-1}\) 表明序列 \(\{x_j\}\) 严格递增, 以及

\begin{equation}x_j=d_{x_{j-1}}\leqslant x_{j-1}+2015.\end{equation}

对于任意的正整数 \(T\gt t_i\), 设 \(g_i\) 是使得 \(x_{g_i+1}\gt T\) 成立的最小非负整数. 换句话说, \((5)\) 中的序列 \(\{x_j\}\) 中的项 \(x_1\), \(x_2\), \(\dotsc\), \(x_{g_i}\) 都是不超过 \(T\) 的正整数, 并且这 \(g_i\) 项都在序列 \(\{d_j\}\) 中出现(\(g_i=0\) 的意思是 \(x_1\), \(x_2\), \(x_3\), \(\dotsc\) 都大于 \(T\)). 我们指出

\begin{equation}g_i\gt\frac{T-t_i}{2015}-1.\end{equation}

事实上, 记得 \((6)\), 于是

\[T\lt x_{g_i+1}\leqslant t_i+2015(g_i+1).\]

这就是 \((7)\).

取定一个正整数 \(A\gt\max\{t_1, t_2, \dotsc, t_c\}\). 根据 \((7)\), 当 \(T\) 是任意的满足 \(T\gt A\) 的正整数时, 序列 \(\{d_j\}\) 中不超过 \(T\) 的项至少有

\begin{equation}g_1+g_2+\dotsb+g_c\gt\sum_{i=1}^c\left(\frac{T-t_i}{2015}-1\right)\gt\sum_{i=1}^c\left(\frac{T-A}{2015}-1\right)=c\left(\frac{T-A}{2015}-1\right)\end{equation}

个.

显然, 序列 \(\{d_j\}\) 中不超过 \(T\) 的项少于 \(T\) 个. 于是

\begin{equation}T\gt c\left(\frac{T-A}{2015}-1\right).\end{equation}

这个式子要对大于 \(A\) 的所有正整数 \(T\) 为真, 必定 \(c\leqslant2015\).

至此, 我们证明了 \(1\leqslant b\leqslant 2015\).

设 \(Y=\{t_1, t_2, \dotsc, t_b\}\) 是所有的没有在序列 \(\{d_j\}\) 中出现的 \(b\) 个正整数组成的集合. 于是, 有由 \(t_1\), \(t_2\), \(\dotsc\), \(t_b\) 出发的 \(b\) 个 \(d\) 序列; \(Y\cup\{d_1, d_2, d_3\dotsc\}\) 恰好就是全部正整数形成的集合.

记 \(\mathfrak D=\{d_1, d_2, d_3\dotsc\}\).

我们指出, \(\mathfrak D\) 中的每个元素在一个 \(d\) 序列中出现一次, 并且只在一个 \(d\) 序列中出现. 于是, \(b\) 个 \(d\) 序列的所有项不重复不遗漏的恰好是全部的正整数.

事实上, 设 \(d_{j_1}\) 是 \(\mathfrak D\) 中的任何一个元素.

如果 \(j_1\notin \mathfrak D\), 那么 \(d_{j_1}\) 恰是由 \(j_1\) 出发的 \(d\) 序列的第 \(2\) 项. 如果 \(j_1\in \mathfrak D\), 必有 \(j_2\lt j_1 \) 使得 \(d_{j_2}=j_1\).

如果 \(j_2\notin \mathfrak D\), 那么 \(d_{j_1}\) 恰是由 \(j_2\) 出发的 \(d\) 序列的第 \(3\) 项. 如果 \(j_2\in \mathfrak D\), 必有 \(j_3\lt j_2 \) 使得 \(d_{j_3}=j_2\).

如此下去. 这个过程不可能无限进行下去. 恰有惟一的正整数 \(l\), 使得

\[ j_l\notin \mathfrak D,\;  j_{l-1},\;  j_{l-2},\;\dotsc,\;  j_2,\; j_1\in \mathfrak D,\; j_l\lt j_{l-1}\lt j_{l-2}\lt\dotsb\lt j_2\lt j_1, \]

\[d_{j_l}=j_{l-1},\; d_{j_{l-1}}=j_{l-2},\;\dotsc,\; d_{j_2}=j_1.\]

\(d_{j_1}\) 恰是由 \(j_l\) 出发的 \(d\) 序列的第 \(l+1\) 项.

取定一个正整数 \(N\gt\max\{t_1, t_2, \dotsc, t_b\}\).

设 \(n\) 和 \(m\) 是任意的满足 \(n\gt m\geq N\) 的整数. \(d_{m+1}\), \(d_{m+2}\), \(\dotsc\), \(d_n\) 会分布在所有的这 \(b\) 个 \(d\) 序列中. 每一个 \(d\) 序列的下标都是严格递增的(\(d_k\) 与 \(d_l\) 都是同一个 \(d\) 序列中的项, 且 \(d_k\) 在 \(d_l\) 前面, 那么 \(k\lt l\)), 因此, \(d_{m+1}\), \(d_{m+2}\), \(\dotsc\), \(d_n\) 在同一个 \(d\) 序列中出现的项一定是这个 \(d\) 序列中的连续若干项.

考虑由 \(t_i\)(\(1\leq i\leq b\)) 出发的 \(d\) 序列中的连续项

\begin{equation}x_u,\; x_{u+1},\;x_{u+2},\;\dotsc,\; x_{u+v},\; x_{u+v+1},\end{equation}

这里 \(u\) 是正整数, \(v\) 是非负整数, 并且

\begin{equation}x_u\lt m+1\leq x_{u+1}\lt x_{u+2}\lt\dotsb \lt x_{u+v}\leq n\lt  x_{u+v+1}.\end{equation}

换句话说, \(d_{m+1}\), \(d_{m+2}\), \(\dotsc\), \(d_n\) 在 \(t_i\)(\(1\leq i\leq b\)) 出发的 \(d\) 序列中出现的所有的项恰好就是下面这 \(v\) 项(\(v=0\) 就是此 \(d\) 序列不包括 \(d_{m+1}\), \(d_{m+2}\), \(\dotsc\), \(d_n\) 中的任意一项)

\begin{equation}d_{x_{u+1}},\;d_{x_{u+2}}\,\;\dotsc,\;d_{x_{u+v}}.\end{equation}

注意

\begin{equation}x_{u+1}=d_{x_u},\;x_{u+2}=d_{x_{u+1}},\;x_{u+3}=d_{x_{u+2}}\,\;\dotsc,\;x_{u+v+1}=d_{x_{u+v}},\end{equation}

我们有

\begin{equation}\sum_{k=1}^v\Big(d_{x_{u+k}}-x_{u+k}\Big)=\sum_{k=1}^v\Big(x_{u+k+1}-x_{u+k}\Big)=x_{u+v+1}-x_{u+1}=d_{x_{u+v}}-d_{x_u}.\end{equation}

于是

\begin{equation}\sum_{k=1}^v\Big(d_{x_{u+k}}-x_{u+k}\Big)-\Big(n-m\Big)=\Big(d_{x_{u+v}}-n\Big)-\Big(d_{x_u}-m\Big).\end{equation}

注意

\begin{equation}d_{x_u}-m=\Big(x_u+a_{x_u}\Big)-m=a_{x_u}-\Big(m-x_u\Big)\end{equation}

说明 \(1\leq d_{x_u}-m\leq2015\). 同样的道理, \(1\leq d_{x_{u+v}}-n\leq2015\).

我们记  \(h=d_{x_u}-m\), \(H=d_{x_{u+v}}-n\). 则

\begin{equation}\sum_{k=1}^v\Big(d_{x_{u+k}}-x_{u+k}\Big)-\Big(n-m\Big)=H-h,\end{equation}

这里, \(1\leq h,\; H\leq2015\).

把 \(t_i\) 相应的 \(u\), \(v\), \(h\), \(H\) 记为 \(u_i\), \(v_i\), \(h_i\), \(H_i\), \(1\leq i\leq b\). 注意, \(h_i\) 互不相同, \(H_i\) 也是互不相同.

当 \(i\) 跑遍 \(1\), \(2\), \(\dotsc\), \(b\) 时,

\begin{equation}\sum_{i=1}^b\Big(\sum_{k=1}^{v_i}(d_{x_{u_i+k}}-x_{u_i+k})-(n-m)\Big)=\sum_{i=1}^b\Big(H_i-h_i\Big)=\sum_{i=1}^b H_i-\sum_{i=1}^b h_i.\end{equation}

\(d_{x_{u_i+1}}\), \(d_{x_{u_i+2}}\), \(\dotsc\), \(d_{x_{u_i+v_i}}\) 是 \(d_{m+1}\), \(d_{m+2}\), \(\dotsc\), \(d_n\) 在由 \(t_i\)(\(1\leq i\leq b\)) 出发的 \(d\) 序列中出现的所有的项. 当 \(i\) 跑遍 \(1\), \(2\), \(\dotsc\), \(b\) 时, \(d_{x_{u_i+1}}\), \(d_{x_{u_i+2}}\), \(\dotsc\), \(d_{x_{u_i+v_i}}\) 不重复不遗漏恰好就是 \(d_{m+1}\), \(d_{m+2}\), \(\dotsc\), \(d_n\). 我们有

\begin{equation}\sum_{k=m+1}^n\Big(d_k-k\Big)=\sum_{i=1}^b\sum_{k=1}^{v_i}\Big(d_{x_{u_i+k}}-x_{u_i+k}\Big).\end{equation}

\(d_k-k=a_k\) 表明

\begin{equation}\begin{split}\sum_{k=m+1}^n\Big(a_k-b\Big)&=\sum_{k=m+1}^n a_k-b\Big(n-m\Big)\\&=\sum_{i=1}^b\Big(\sum_{k=1}^{v_i}(d_{x_{u_i+k}}-x_{u_i+k})-(n-m)\Big)\\&=\sum_{i=1}^b H_i-\sum_{i=1}^b h_i.\end{split}\end{equation}

注意, 一定恰有惟一的 \(i\)(\(1\leq i\leq b\)), 使得 \(x_{u_i+1}=m+1\); 恰有惟一的 \(j\)(\(1\leq j\leq b\)), 使得 \(x_{u_j+v_j+1}=n+1\). 此时

\begin{equation}h_i=d_{x_{u_i}}-m=x_{u_i+1}-m=1,\; H_j=d_{x_{u_j+v_j}}-n=x_{u_j+v_j+1}-n=1.\end{equation}

\(h_1\), \(h_2\), \(\dotsc\), \(h_b\) 是 \(\{1, 2, 3,\dotsc,2015\}\) 中包括 \(1\) 在内的 \(b\) 个互不相同的元素, \(H_1\), \(H_2\), \(\dotsc\), \(H_b\) 亦然. 故而

\begin{equation}\begin{split}
\left|\sum_{k=m+1}^n\Big(a_k-b\Big)\right|&\leqslant\Big(1+2015+2014+\dotsb+(2017-b)\Big)-\Big(1+2+3+\dotsb+b\Big)\\&=\Big(2015-b\Big)\Big(b-1\Big)\leqslant1007^2.\end{split}\end{equation}

看到我们的魂牵梦绕.

最后的式子泄漏了本性: 与上两个解法的本质是一样的!

解答五

这个主意是本题供题人之一的 Ivan Guo 给出的. 背后的想法倒不是多复杂, 要写清楚要仔细的挑选.

令 \(d_j=a_j+j\), \(j=1\), \(2\), \(\dotsc\). 于是, 正整数序列 \(d_1\), \(d_2\), \(\dotsc\) 互不相同, 并且对每个正整数 \(j\geqslant1\), 有 \(j+1\leqslant d_j\leqslant j+2015\).

\begin{equation}d_1,\; d_2,\; d_3, \;\dotsc\end{equation}

按照从小到大的顺序排列成 \(d_{i_1}\), \(d_{i_2}\), \(d_{i_3}\), \(\dotsc\). 即, \(i_1\), \(i_2\), \(i_3\), \(\dotsc\) 是全体正整数的一个排列, 且

\begin{equation}d_{i_1}\lt d_{i_2}\lt d_{i_3}\lt\dotsb.\end{equation}

把一个序列中的某两项对调位置, 而其余的项不动, 得到另一个序列的变换称为一个对换. 需要强调的是, 这里的对换, 允许对调位置的两项重合. 也就是说, 一个对换可以不变动任何一项的位置.

令 \(\pi_0\) 和 \(\pi\) 分别就是\((23)\) 中的序列 \(\{d_j\}\) 和 \((24)\) 中的序列.

从 \(\pi_0\) 开始, 通过有限次的对换, 我们可以得到最前面若干项与 \(\pi\) 相同, 并且只有有限项与 \(\pi_0\) 不同的序列. 具体来说, 设 \(\pi_1\) 是通过交换 \(\pi_0\) 的两项 \(d_1\) 与 \(d_{i_1}\) 的位置得到的序列. 如果 \(d_1=d_{i_1}\), \(\pi_1\) 与 \(\pi_0\) 是同一个序列. \(\pi_1\) 的首项即是 \(d_{i_1}\). 设 \(\pi_2\) 是通过交换 \(\pi_1\) 的第 \(2\) 项与 \(d_{i_2}\) 的位置得到的序列. \(\pi_2\) 的前 \(2\) 项即是 \(d_{i_1}\), \(d_{i_2}\). 一般地, 设 \(\pi_j\) 是通过交换 \(\pi_{j-1}\) 的第 \(j\) 项与 \(d_{i_j}\) 的位置得到的序列, \(j\) 是正整数. \(\pi_j\) 可能与 \(\pi_{j-1}\) 是同一个序列. \(\pi_j\) 的前 \(j\) 项即是 \(d_{i_1}\), \(d_{i_2}\), \(\dotsc\), \(d_{i_j}\); \(\pi_j\) 至多有 \(2j\) 项与 \(\pi_0\) 不同.

令 \(e_j=d_{i_j}-j\), \(j=1\), \(2\), \(\dotsc\).

首先指出, 序列 \(e_1\), \(e_2\), \(e_3\), \(\dotsc\) 单调递增, 但不是严格单调, 并且对每个整数 \(j\geq1\),

\begin{equation}1+j\leq d_{i_j}\leq2015+j,\;1\leq e_j\leq2015.\end{equation}

于是, 存在两个正整数 \(b\) 和 \(M\), \(1\leq b\leq2015\), 对所有满足 \(j\geq M\) 的整数 \(j\), \(e_j=b\) 成立.

事实上, \(d_{i_1}=i_1+a_{i_1}\geq2\). 于是

\[d_{i_j}\geq d_{i_1}+\Big(j-1\Big)\geq2+\Big(j-1\Big)=j+1.\]

\(d_{i_j}\) 是 \(\pi_0\) 按照从小到大排序的第 \(j\) 项, 所以

\[d_{i_j}\leq\max\{d_1,\;d_2,\;\dotsc,\;d_j\}\leq j+2015.\]

此时, 当然应当有

\[1\leq e_j=d_{i_j}-j\leq2015.\]

此外,

\[e_{j+1}-e_j=\Big(d_{i_{j+1}}-(j+1)\Big)-\Big(d_{i_j}-j\Big)=d_{i_{j+1}}-d_{i_j}-1\geq0\]

表明 \(e_{j+1}\geq e_j\).

\(j\) 是非负整数, \(k\) 是正整数. 设 \(\pi_j\) 的第 \(k\) 项是 \(d_{j,\, k}\), 即 \(\pi_j\) 是如下的序列

\begin{equation}d_{j,\, 1},\; d_{j,\, 2},\; d_{j,\,3},\;\dotsc,\; d_{j,\, k},\;\dotsc.\end{equation}

于是当 \(j\geq1\) 时, \(d_{j,\, 1}=d_{i_1}\), \(d_{j,\, 2}=d_{i_2}\), \(\dotsc\), \(d_{j,\, j}=d_{i_j}\).

我们判定, 对所有的非负整数 \(j\) 和正整数 \(k\), 成立

\begin{equation}1+k\leq d_{j,\,k}\leq2015+k.\end{equation}

我们对 \(j\) 进行归纳.

\(d_{0,\,k}=d_k\) 表明奠基显然.

对正整数 \(j\) 和 \(k\), \(k\gt j\), \(\pi_j\) 是通过交换 \(\pi_{j-1}\) 的第 \(j\) 项与第 \(k\) 项的位置得到的序列. \(\pi_{j-1}\) 的第 \(j\) 项必定是 \(d_{j,\,k}\), 第 \(k\) 项必定是 \(d_{i_j}\), 且 \(d_{j,\,k}\gt d_{i_j}=d_{j,\, j}\). 于是

\[d_{j,\,k}\gt d_{i_j}=d_{j-1,\,k}\geq 1+k.\]

\[d_{j,\,k}= d_{j-1,\,j}\leq 2015+j\lt2015+k.\]

至此, 我们验证了 \((27)\) 的真实性.

当 \(j\geq M\), \(d_{i_j}=j+b\). 故,  \(j\geq M\) 时,

\begin{equation}d_{j,\, M}=M+b,\; d_{j,\, M+1}=M+1+b,\; d_{j,\, M+2}=M+2+b,\;\dotsc,\; d_{j,\, j}=j+b.\end{equation}

接下来, 我们来证明: 正整数 \(x\geq M\). 交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\), \(x+1\lt y\). 那么

\begin{equation}1\leq y-\Big(x+1\Big)\leq b-1,\; 0\lt d_{x,\, x+1}-d_{x,\, y}\leq2015-b.\end{equation}

事实上,  \(d_{x,\,y}=d_{x+1,\, x+1}=x+1+b\), 于是

\begin{equation}0\lt d_{x,\, x+1}-d_{x,\, y}=d_{x,\, x+1}-d_{x+1,\, x+1}\leq\Big(x+1+2015\Big)-\Big(x+1+b\Big)=2015-b.\end{equation}

又因为 \(d_{x,\,y}\geq y+1\), \(x+1\lt y\), 所以

\begin{equation}x+1+b\geq y+1\end{equation}

定出 \(b-1\geq y-(x+1)\geq1\).

设 \(x\geq0\) 是整数. 交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\), \(x+1\leq y\). 那么

\begin{equation}0\leq y-\Big(x+1\Big)\leq2014.\end{equation}

事实上,  \(d_{x+1,\, x+1}=d_{x,\,y}\), 于是

\begin{equation}\Big(x+1\Big)+2015\geq d_{x+1,\, x+1}=d_{x,\,y}\geq1+y\end{equation}

从而 \(0\leq y-(x+1)\leq 2014\).

这表明, 我们所做的每一个的对换, 把一个序列的某两项对调位置(允许这两项同一), 此序列在这两项之间至多还有 \(2013\) 项. 于是, 设 \(x\) 是整数, \(0\leq x\leq M\), \(x+1\leq y\), 并且交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\). 那么 \(y\leq M+2015\).

取正整数 \(N\), \(N\gt M+2015\). 于是, 如果通过交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\), 且 \(y\geq N\), 那么必定 \(x\gt M\), 进而 \(d_{x,\,y}=d_{x+1,\,x+1}=x+1+b\).

设整数 \(m\) 和 \(n\) 适合 \(n\gt m\geq N\).

考察

\begin{equation}s_j=\sum_{k=m+1}^n d_{j,\,k},\;j=0,\,1,\,2,\,\dotsc, n.\end{equation}

我们来观察对换 \(\pi_x\) 的第 \(x+1\) 项与 \(d_{i_{x+1}}\) 的位置对 \(s_x\) 的影响, 即估计 \(s_{x+1}-s_x\), 这里 \(0\leq x\lt n\).

当 \(x+1\lt m+1\leq y\), 交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\). 注意 \(d_{x+1,\, y}=d_{x,\, x+1}\), 于是

\begin{equation}0\lt d_{x+1,\, y}-d_{x,\, y}=d_{x,\, x+1}-d_{x,\, y}\leq2015-b.\end{equation}

在 \(y\leq n\) 成立之时, \(s_{x+1}-s_x=d_{x+1,\, y}-d_{x,\, y}\); 在 \(y\gt n\), \(s_{x+1}=s_x\). 故而

\begin{equation}0\leq s_{x+1}-s_x\leq2015-b.\end{equation}

现在来考虑有多少个 \(x\), 使得交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\), 且 \(x+1\lt m+1\leq y\). 由 \(b-1\geq y-(x+1)\geq1\), 于是

\begin{equation}b-1\geq m+1-\Big(x+1\Big)\geq1.\end{equation}

从而这样的 \(x\) 不超过 \(b-1\) 个.

同样的道理, 交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\), 且 \(x+1\leq n\lt y\). \(d_{x+1,\, x+1}=d_{x,\, y}\) 蕴涵

\begin{equation}0\gt d_{x+1,\, x+1}-d_{x,\, x+1}=d_{x,\, y}-d_{x,\, x+1}\geq-\Big(2015-b\Big).\end{equation}

在 \(x+1\geq m+1\) 成立之时, \(s_{x+1}-s_x=d_{x+1,\, x+1}-d_{x,\, x+1}\); 在 \(x+1\leq m\), \(s_{x+1}=s_x\). 故而

\begin{equation}-\Big(2015-b\Big)\leq s_{x+1}-s_x\leq0.\end{equation}

现在来考虑有多少个 \(x\), 使得交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\), 且 \(x+1\leq n\lt y\). 由 \(b-1\geq y-(x+1)\geq1\), 于是

\begin{equation}b-1\geq n-x\geq1.\end{equation}

至多有 \(b-1\) 个这样的 \(x\).

如果交换 \(\pi_x\) 的第 \(x+1\) 项与第 \(y\) 项的位置得到 \(\pi_{x+1}\), 当 \(x+1\leq y\lt m+1\) 或 \(m+1\leq x+1\leq y\leq n\) 时, \(s_{x+1}=s_x\) 皆为真.

至此, \(0\leq x\lt n\), \(s_{x+1}-s_x\) 至多有 \(2(b-1)\) 个不是 \(0\): 至多 \(b-1\) 个正数, 每个都不超过 \(2015-b\); 至多 \(b-1\) 个负数, 每个都不小于 \(-(2015-b)\). 于是

\begin{equation}-\Big(2015-b\Big)\Big(b-1\Big)\leq s_n-s_0\leq\Big(2015-b\Big)\Big(b-1\Big).\end{equation}

注意

\begin{equation}\begin{split}s_0-s_n&=\sum_{k=m+1}^n d_k-\sum_{k=m+1}^n d_{n,\,k}\\&=\sum_{k=m+1}^n \Big(a_k+k\Big)-\sum_{k=m+1}^n\Big(b+k\Big)\\&=\sum_{k=m+1}^n \Big(a_k-b\Big).\end{split}\end{equation}

最后, 我们辛苦一生的梦想握在了手中

\begin{equation}\left|\sum_{k=m+1}^n\Big(a_k-b\Big)\right|\leqslant\Big(2015-b\Big)\Big(b-1\Big)\leqslant1007^2.\end{equation}

 Posted by at 5:03 pm  Tagged with: