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*}\begin{split}&\hspace2.5ex-(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{split}\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:
Jul 112015
 

2015 第 56 届 IMO 解答

Problem 1 (Netherlands 荷兰)

(a)  \(n\) 是奇数.

考察一个周长为 \(n\) 的圆 \(\omega\). 这圆上均匀分布的 \(n\) 个点, 即把圆分成 \(n\) 个长为 \(1\) 的圆弧, 构成点集 \(\mathcal S\). 换句话说, \(\mathcal S\) 的元素即是内接于该圆的正 \(n\) 边形的 \(n\) 个顶点.

我们断言: \(\mathcal S\) 是平衡且无中心的点集.

事实上, \(\mathcal S\) 中任意两个不同的点 \(A\), \(B\) 把圆分成的两个圆弧的弧长都是正整数, 并且两个弧长之和就是圆的周长 \(n\). 既然 \(n\) 为奇数, 这两个圆弧的弧长恰有一个偶数. 于是, 弧长是偶数的那个圆弧的中点 \(C\) 属于 \(\mathcal S\). 此时 \(AC=BC\) 是理所当然. 因而, \(\mathcal S\) 是平衡的.

\(\mathcal S\) 亦是无中心的. \(\mathcal S\) 中任意三个不同的点 \(A\), \(B\), \(C\) 形成的三角形的外心即是 \(\omega\) 的中心. \(\omega\) 的中心显然不在 \(\omega\) 上, 当然也就不在 \(\mathcal S\) 中.

\(n\) 是偶数, 记 \(n=2k+2\), 这里 \(k\) 是正整数.

设 \(\odot O\) 是任意的一个圆. 在这个圆上依逆时针方向选取三点 \(A_1\), \(B_1\), \(C\),  使得 \(\triangle OA_1B_1\) 和 \(\triangle OB_1C\) 都是等边三角形; 再在 \(\widehat{A_1B_1}\) 和 \(\widehat{B_1C}\) 上分别依逆时针方向各选取 \(k-1\) 个点 \(A_2\), \(A_3\), \(\dotsc\), \(A_k\) 和 \(B_2\), \(B_3\), \(\dotsc\), \(B_k\), 使得 \(\triangle OA_iB_i\) 都是等边三角形, \(i=2\), \(3\), \(\dotsc\), \(k\).

\[\mathcal S=\{O, A_1, A_2, \dotsc, A_k, B_1, B_2, \dotsc, B_k, C\}.\]

我们断言: \(\mathcal S\) 是 \(2k+2\) 个点构成的平衡点集.

事实上, \(\mathcal S\) 中的两点如果都落在 \(\odot O\) 上, 则 \(O\) 到这两点的距离相等. 对于 \(O\) 和 \(\mathcal S\) 中的落在 \(\odot O\) 上的一点, 必有 \(\mathcal S\) 的落在 \(\odot O\) 上的第二个点与前两个点构成等边三角形, 进而第二个点到前两个点的距离相等.

(b) 先指出, 若 \(n\gt3\) 为偶数, 不存在由 \(n\) 个点构成的平衡且无中心的点集.

假定 \(\mathcal S\) 是由 \(n\) 个点构成的平衡且无中心的点集. \(\mathcal S\) 中任意两个不同的点 \(A\), \(B\), 都有 \(\mathcal S\) 中的点 \(C\), 满足 \(AC=BC\). 也就是说, 线段 \(AB\) 的中垂线经过 \(C\). 我们把这样的点 \(C\) 称为等腰顶点.

恰有 \(\dbinom n2\) 个互不相同的线段的端点落在 \(\mathcal S\) 中, 于是必定有 \(\dbinom n2\) 个等腰顶点 (一个等腰顶点可能多次计数). 故而, 必定有

\[\frac1n\dbinom n2=\frac{n-1}2\]

等腰顶点其实是 \(\mathcal S\) 中的同一个点. 考虑到 \(n-1\) 是奇数, 必有 \(\dfrac n2\) 个等腰顶点是 \(\mathcal S\) 中的同一点 \(U\), 即有 \(\dfrac n2\) 个线段的中垂线都经过 \(U\). 记这些线段是

\[X_1Y_1, X_2Y_2, \dotsc , X_{\frac n2}Y_{\frac n2}.\]

既然这 \(\dfrac n2\) 个线段的端点都肯定不能是 \(U\), 必有 \(i\), \(j\), \(1\leq i\lt j\leq \dfrac n2\), 使得线段 \(X_iY_i, X_jY_j\) 的端点有重合. 于是, 线段 \(X_iY_i, X_jY_j\) 的端点实际只有三个点互不相同. \(U\) 到这三个点的距离都相同. 这说明, \(\mathcal S\) 不是无中心的.

(a) 已经说明对所有不小于 \(3\) 的奇数 \(n\), 存在由 \(n\) 个点构成的平衡且无中心的点集.

综合起来, 找寻的所有整数即为所有不小于 \(3\) 的奇数.

Problem 2 (Serbia 塞尔维亚)

容易看见的事实是: \(a\), \(b\), \(c\) 都不可能为 \(1\). 因为 \(a=1\) 给出 \(b-c\) 和 \(c-b\) 都是正整数.

如果 \(a\), \(b\), \(c\) 中有相等者, 无妨 \(a=b\), 那么 \(a^2-c\), \(ac-a\) 都是 \(2\) 的方幂. 注意 \(ac-a=a(c-1)\), 因此 \(a\) 和 \(c-1\) 也都是 \(2\) 的方幂. 可设

\begin{equation}a^2-c=2^u,\end{equation}

\begin{equation}a=2^v,\end{equation}

\begin{equation}c=2^w+1,\end{equation}

这里 \(u\), \(v\), \(w\) 都是非负整数. \(a\gt1\) 定出 \(v\gt0\), \(a\) 是偶数.

若 \(u\gt0\), 则 \((1)\) 表明 \(c\) 是偶数, 进而 \((3)\) 表明 \(w=0\). 于是, \(c=2\). 把 \((2)\) 带入 \((1)\)

\begin{equation}2^{2v}-2=2^u.\end{equation}

\(2^u\equiv2\pmod4\) 定出 \(u=1\), 进而 \(v=1\). 于是 \(a=2\), \(b=a=2\).

在 \(u=0\), 则 \((1)\) 成为

\begin{equation}2^{2v}-c=1.\end{equation}

把 \((3)\) 带入上式, 有

\begin{equation}2^{2v}=2^w+2.\end{equation}

\(2^w\equiv2\pmod4\) 定出 \(w=1\), \(c=2^1+1=3\), 进而 \(v=1\).  于是 \(a=2\), \(b=a=2\).

在 \(a\), \(b\), \(c\) 互不相等, 无妨 \(a\gt b\gt c\).

\begin{equation}ab-c=2^x,\;ca-b=2^y,\;bc-a=2^z\end{equation}

这里 \(x\), \(y\), \(z\) 都是非负整数.

\[2^x-2^y=(ab-c)-(ca-b)=(b-c)(a+1)\]

说明 \(ab-c\gt ca-b\), \(x\gt y\), 进而

\begin{equation}2^y\mid(b-c)(a+1).\end{equation}

类似的道理, \(y\gt z\).

然后

\[2^x+2^y=(ab-c)+(ca-b)=(b+c)(a-1)\]

说明

\begin{equation}2^y\mid(b+c)(a-1).\end{equation}

\(a-1\), \(a+1\) 是两个相差 \(2\) 的正整数, 至少有一个不是 \(4\) 的倍数.

如果 \(4\nmid(a+1)\), 则 \(2^y\mid2(b-c)\), 于是 \(2^y\leqslant2(b-c)\). 如果 \(4\nmid(a-1)\), 则 \(2^y\mid2(b+c)\), 于是 \(2^y\leqslant2(b+c)\). 无论哪一种情况, \(2^y\leqslant2(b+c)\) 必真.

\[c(b+1)\leqslant ca=2^y+b\leqslant 2(b+c)+b\]

给出

\[bc\lt3b+c\lt4b,\]

故而 \(c\lt4\).

\(c=2\).

若 \(a\), \(b\) 至少有一个奇数. 我们断定 \(b\) 是奇数, \(a\) 是偶数绝无可能同时发生. 否则, \(ac-b=2a-b\geqslant a\) 表明 \(2a-b\) 是大于 \(1\) 的奇数.

在 \(a\) 是奇数,  则 \(cb-a=2b-a\) 是奇数,  必定 \(2b-a=1\). 因此 \(a=2b-1\).

此时 \(ab-c=b(2b-1)-2=2b^2-b-2\), \(ca-b=2(2b-1)-b=3b-2\) 都是 \(2\) 的方幂. \(b\geqslant2\) 说明 \(2b^2-b-2 \geqslant4b-b-2= 3b-2\), 因此 \(3b-2\) 整除 \(2b^2-b-2\). 然后

\[9(2b^2-b-2)=(3b-2)(6b+1)-16\]

定出 \((3b-2)\mid16\). 从而 \(3b-2\) 可能是 \(2\), \(4\), \(8\), \(16\). \(3b-2\equiv1\pmod3 \) 蕴涵 \(3b-2\) 只可能是 \(4\), \(16\). 此时, \(b=2\), \(6\). 相应地, \(a=3\), \(11\).

在 \(a\), \(b\) 都是偶数.  \(ab-2\equiv2\pmod4\).  但是 \(ab-2\) 是 \(2\) 的方幂, 因此 \(ab-2=2\), \(ab=4\). 所以 \(a=b=2\).

\(c=3\).

\(2^x=ab-3\gt3^2-3\gt4\) 定出 \(x\gt2\), 并且 \(ab-3\) 是偶数, 从而 \(ab\) 是, 进而 \(a\), \(b\) 都是, 奇数.  \(2^x\), \(2^y\), \(2^z\) 都是偶数, 从而 \(x\), \(y\), \(z\) 都是正整数, \(x\gt y\gt z\geqslant1\).

\begin{equation}(3a-b)+(3b-a)=2^y+2^z\end{equation}

得 \(2(a+b)\lt2^{y+1}\), 故 \(a+b\lt2^y\), \(a\lt2^y-b\lt2^y-3\), 进而 \(a-1\lt a+1\lt2^y-b\lt2^y\).

\(2^y=3a-b\gt2a\) 说明 \(a\lt2^{y-1}\).

\((8)\), \((9)\) 表明

\[2^y\mid(b-3)(a+1),\;2^y\mid(b+3)(a-1).\]

\(b\) 为奇数, 所以 \(b-3\), \(b+3\) 恰有一个不被 \(4\) 整除.

在 \(2\parallel(b-3)\) 时, 则 \(2^y\mid2(a+1)\), 即 \(2^{y-1}\mid(a+1)\). 结合 \(a+1\lt2^y\), 导出 \(a+1=2^{y-1}\), 故 \(a=2^{y-1}-1\).

在 \(2\parallel(b+3)\) 时, 则 \(2^y\mid2(a-1)\), 即 \(2^{y-1}\mid(a-1)\). 结合 \(a-1\lt2^y\), 导出 \(a-1=2^{y-1}\), 故 \(a=2^{y-1}+1\). \(a\lt2^{y-1}\) 表示这种情况不会出现.

既然 \(a=2^{y-1}-1\), \(3a-b=2^y\), 因之 \(b=3a-2^y=3(2^{y-1}-1)-2^y=2^{y-1}-3\). 结合 \(3b-a=2^z\), 我们有 \(3(2^{y-1}-3)-(2^{y-1}-1)=2^z\), 即

\[2^y-2^z=8.\]

这也就是

\[2^z(2^{y-z}-1)=8.\]

\(z\), \(y-z\) 都是正整数, 因此 \(2^z=8\), \(2^{y-z}-1=1\). 所以 \(z=3\), \(y-z=1\). 后一式说明 \(y=4\). 于是

\[a=2^{4-1}-1=7,\;b=2^{4-1}-3=5.\]

综上所述, 所有符合要求的正整数解是 \((2,2,2)\), \((3,2,2)\), \((11,6,2)\), \((7,5,3)\), 以及这些解的所有排列.

解答二

把 \(a=2^v\), \(c=2^w+1\) 带入 \(a^2-c=2^u\) 得

\[(2^v)^2-(2^w+1)=2^u.\]

我们看到

\[2^{2v}=2^w+1+2^u.\]

\(v\geqslant1\) 说明

\[2^w+1+2^u\equiv0\pmod4.\]

\(2^w+2^u\) 为奇数表明 \(w\), \(u\) 一个是 \(0\), 另一个大于 \(0\).

\(w=0\) 导出 \(4\mid (1+1+2^u)\), 进而 \(2^u\) 是偶数但不被 \(4\) 整除, 于是 \(u=1\). 此时 \(v=1\),

\[a=2,\; b=a=2,\; c=2^0+1=2.\]

类似, \(u=0\) 给出 \(4\mid (2^w+1+1)\), 进而 \(2^w\) 是偶数但不被 \(4\) 整除, \(w=1\). 此时 \(v=1\),

\[a=2,\; b=a=2,\; c=2^1+1=3.\]

Problem 3 (Ukraine 乌克兰)

这个题比较棘手. 中国队载在这题上了, 只有 1 个队员做出来, 本题一共才得 12 分.

本题的平均分 0.653, 一共有 31 个队员在考场上做出: 得 7 分有 30 人, 得 6 分仅 1 人.

鉴于此, 这里在这个问题多花点笔墨.

记 \(\Gamma\) 的中心是 \(O\). 设 \(AX\) 为 \(\Gamma\) 的直径.

这个问题所有的证明, 也许, 都需要这个事实: \(Q\), \(H\), \(M\), \(X\) 四点共线.

\(AX\) 是 \(\Gamma\) 的直径蕴涵 \(\angle AQX = 90^{\circ}\). \(\angle AQH = 90^{\circ}\) 表明 \(\angle AQX = \angle AQH\), 进而 \(Q\), \(H\), \(X\) 三点共线.

\(AX\) 是 \(\Gamma\) 的直径蕴涵 \(XB\), \(XC\) 分别与 \(AB\), \(AC\) 垂直. \(H\) 是 \(\triangle ABC\) 的垂心宣示 \(HC\), \(HB\) 分别与 \(AB\), \(AC\) 垂直. 因此, 四边形 \(BXCH\) 是平行四边形. \(M\) 是 \(BC\), 进而也是 \(XH\), 的中点. 从而, \(X\), \(M\), \(H\) 三点共线.

综合起来, 我们知道 \(Q\), \(H\), \(M\), \(X\) 四点共线.

不证明四边形 \(BXCH\) 是平行四边形也是可以说明 \(M\) 是 \(XH\) 的中点. 从而, \(X\), \(M\), \(H\) 三点共线.

事实上, 对任何一个三角形 \(ABC\) 的垂心 \(H\), 外心 \(O\), 以及 \(BC\) 的中点 \(M\), 熟知的一个性质是 \(OM\parallel AH\), 且 \(OM=\dfrac12AH\).

这性质很直接很强烈的表达了 \(M\) 就是 \(XH\) 的中点.

IMO 2015 Problem 3 Proof 1

IMO 2015 Problem 3 Proof 1

延长 \(AF\) 交 \(\Gamma\) 于 \(Y\). 注意

\[\angle HKQ=\angle HYX=\angle HFM= 90^{\circ},\]

于是三角形 \(HKQ\) 的外接圆, 三角形 \(HXY\) 的外接圆与三角形 \(HMF\) 的外接圆在 \(H\) 点相切.

\(QK\) 与 \(XY\) 的延长线交于点 \(V\). 于是

\[VQ\cdot VK=VX\cdot VY.\]

故而, \(V\) 在三角形 \(HKQ\) 的外接圆与三角形 \(HXY\) 的外接圆的根轴上. 这个根轴就是 \(VH\), 并且 \(VH\) 是三角形 \(HKQ\) 的外接圆, 三角形 \(HXY\) 的外接圆与三角形 \(HMF\) 的外接圆的公切线. \(VH\perp QX\).

\(AX\) 为 \(\Gamma\) 的直径蕴涵 \(XY\perp AY\). 于是 \(BC\perp AF\) 表明 \(BC\parallel XY\). 设 \(U\) 是 \(VH\) 与 \(BC\) 的交点. \(H\) 是 \(\triangle ABC\) 的垂心揭示 \(F\) 是 \(HY\) 的中点. 至此, \(U\) 是 \(HV\) 的中点. \(\angle HKV= 90^{\circ}\) 蕴涵 \(UK=UH\). \(UH\) 与三角形 \(HKQ\) 的外接圆相切, 故而 \(UK\) 也与三角形 \(HKQ\) 的外接圆相切.

\(U\) 在三角形 \(HMF\) 的外接圆与三角形 \(FKM\) 的外接圆的根轴 \(MF\) 上. \(UH\) 与三角形 \(HMF\) 的外接圆相切. 然后, \(UK=UH\) 蕴涵 \(UK\) 是三角形 \(FKM\) 的外接圆的切线. 于是 \(HKQ\) 的外接圆与三角形 \(FKM\) 的外接圆相切, 因为这两个圆都与 \(UK\) 切于点 \(K\).

解答二
IMO 2015 Problem 3 Proof 2

IMO 2015 Problem 3 Proof 2

延长 \(AF\) 交 \(\Gamma\) 于 \(Y\).

在三角形 \( KQH\) 与 \( KAX\) 中, \(\angle HKQ = \angle XKA= 90^{\circ}\), \(\angle HQK = \angle XQK =\angle XAK\), 于是,

\[\angle KHQ = \angle KXA =\angle KYA=\angle KYH.\]

这说明 \(QX\) 与三角形 \(HYK\) 的外接圆相切.

设 \(U\) 是三角形 \(HYK\) 的外心. \(U\) 在 \(HY\) 在中垂线 \(BC\) 上. \(QX\) 是三角形 \(HYK\) 的外接圆的切线, 所以 \(UH\perp QH\). 于是 \(UH\) 与三角形 \(HKQ\) 的外接圆相切. \(UK=UH\) 说明 \(UK\) 也与三角形 \(HKQ\) 的外接圆相切.

\(UH\perp HM\), \(HF\perp MU\), 根据射影定理

\[UK^2=UH^2=UF\cdot UM.\]

这导出 \(UK\) 是三角形 \(FKM\) 的外接圆的切线. 既然 \(UK\) 是\(HKQ\) 的外接圆与三角形 \(FKM\) 的外接圆的公切线, 从而 \(HKQ\) 的外接圆与三角形 \(FKM\) 的外接圆相切.

解答三
IMO 2015 Problem 3 Proof 3

IMO 2015 Problem 3 Proof 3

延长 \(AF\) 交 \(\Gamma\) 于 \(Y\).

\(H\) 是 \(\triangle ABC\) 的垂心揭示 \(\angle QMC = \angle YMC\), 于是,  四边形 \(BYCQ\) 是调和四边形, 由此 \(\angle QBY = \angle QMC\).

设 \(QZ\) 为 \(\Gamma\) 的直径. 于是 \(\angle QKZ = 90^{\circ}\). \(\angle QKH = 90^{\circ}\) 表明 \(\angle QKZ = \angle QKH\), 进而 \(K\), \(H\), \(Z\) 三点共线.

\(ZQ\) 为 \(\Gamma\) 的直径, 于是  \(\angle ZKY+\angle QBY= 90^{\circ}\). 故此

\[\angle HKY=\angle ZKY= 90^{\circ}-\angle QBY=90^{\circ}-\angle QMC=\angle MHY,\]

这说明 \(XQ\) 与三角形 \(HYK\) 的外接圆相切.

解答四
IMO 2015 Problem 3 Proof 4

IMO 2015 Problem 3 Proof 4

\(QK\) 与 \(BC\) 的延长线交于点 \(W\). 既然 \(HK\perp KW\), \(HF\perp FW\), 于是 \(H\), \(F\), \(W\), \(K\) 四点共圆. 故而

\[\angle KFW=\angle KHW.\]

注意, 三角形 \(ABC\), \(HBC\) 的外接圆的根轴是 \(BC\); 三角形 \(ABC\), \(KQH\) 的外接圆的根轴是 \(QK\). 既然 \(W\) 是 \(BC\) 与 \(QK\) 的交点, 因此 \(W\) 是三个三角形 \(ABC\), \(HBC\), \(KQH\) 的外接圆的根心, 进而 \(HW\) 即是三角形 \(HBC\), \(KQH\) 的外接圆的根轴. 设三角形 \(HBC\), \(KQH\) 的外接圆的 \(H\) 之外的另一个交点是 \(S\), 则 \(S\) 在 \(HW\) 上.

设三角形 \(KQH\) 的外接圆与 \(KF\) 的 \(K\) 之外的另一个交点是 \(T\); \(MS\) 的延长线交三角形 \(ABC\) 的外接圆于 \(K^\prime\);  \(S\) 关于 \(M\) 的对称点是 \(S^\prime\).  注意, \(S^\prime\) 在三角形 \(ABC\) 的外接圆上. 于是

\[\angle QHS=180^{\circ}-\angle MHS=180^{\circ}-\angle MXS^\prime=180^{\circ}-\angle QK^\prime S.\]

故此, \(Q\), \(H\), \(S\), \(K^\prime\) 四点共圆. 因而, \(K\) 与 \(K^\prime\) 重合. 这也就是说, \(M\), \(S\), \(K\) 三点共线.

由于 \(H\), \(S\), \(T\), \(K\) 四点共圆, 于是

\[\angle KFM=180^{\circ}-\angle KFW=180^{\circ}-\angle KHW=\angle KTS.\]

这表明 \(ST\parallel MF \). 进而, 三角形 \(KST\) 与 \(KMF\) 位似, \(K\) 是位似中心. 这也就说明了, \(KST\) 的外接圆与三角形 \(KMF\) 的外接圆在 \(K\) 点相切.

解答五
IMO 2015 Problem 3 Proof 5

IMO 2015 Problem 3 Proof 5

解答三的 \(K\), \(H\), \(Z\) 三点共线, 以及 \(\widehat{XZ}=\widehat{AQ}\), 所以

\[\angle KHQ=\angle HQZ+\angle HZQ=\angle AYQ+\angle QYK=\angle AYK.\]

或者稍微变通一下, \(AX\) 是 \(\Gamma\) 的直径, 因此 \(\widehat{AKX}\) 恰是一个半圆. 因此

\[\angle XQK+\angle AYK=90^{\circ}.\]

注意 \(\angle HKQ=90^{\circ}\), 于是

\[\angle KHQ=90^{\circ}-\angle KQH=\angle HYK.\]

因此, \(QH\) 是三角形 \(HYK\) 的外接圆的切线. 所以 \(\angle QHK=\angle HYK\). 又因为 \(MF\) 是 \(HY\) 的中垂线, 故而

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

于是, 我们得出了

\[\angle QHK+\angle MKH=\angle HYK+\angle YKF=\angle HFK.\]

\(QK\perp HK\), \(HF\perp FC\) 给出 \(\angle QHK=90^{\circ}-\angle KQH\),  \(\angle HFK=90^{\circ}-\angle KFC\),  我们有

\[(90^{\circ}-\angle KQH)+\angle MKH=90^{\circ}-\angle KFC.\]

换言之

\[\angle KFC+\angle MKH=\angle KQH.\]

这说明, \(KQH\) 的外接圆与三角形 \(KMF\) 的外接圆在 \(K\) 点相切.

解答六

Problem 4 (Vaggelis Psychas&Silouanos Brazitikos , Greece 希腊)

IMO 2015 Problem 4 Proof 1

IMO 2015 Problem 4 Proof 1

记 \(FG\) 与 \(AC\) 的交点是 \(R\). 连结 \(AG\), \(GC\), \(DF\).

\(FG\) 是 \(\Gamma\) 和 \(\Omega\) 的公共弦蕴涵 \(AO\) 是 \(FG\) 的中垂线. 于是, \(\widehat{AF}=\widehat{AG}\), 进而

\[\angle AGR=\angle AGF=\angle ACF=\angle ACG.\]

这表明 \(\triangle AGR\sim\triangle ACG\). 结合 \(A\), \(B\), \(C\), \(G\) 四点共圆, 我们可有

\[\angle GRC=180^{\circ}-\angle ARG=180^{\circ}-\angle AGC=\angle ABC=\angle KFD.\]

连结 \(FC\), \(EG\). 注意 \(F\), \(D\), \(E\), \(G\) 四点都在圆 \(\Gamma\) 上, 故

\[\angle GFD=\angle GEC=\angle GLC=\angle GLR.\]

至此, 我们得出

\[\angle XGF=\angle GRC-\angle GLR=\angle KFD-\angle GFD=\angle XFG.\]

这说明 \(XG=XF\). 换句话说, \(X\) 在 \(FG\) 的中垂线 \(AO\) 上.

解答二

Problem 5 (Dorlir Ahmeti,Albania 阿尔巴尼亚)

\begin{equation}f(x+f(x+y))+f(xy)=x+f(x+y)+yf(x).\end{equation}

在 \((11)\), 令 \(x=y=0\), 记 \(f(0)=a\), 得

\[f(0+a)+a=0+a.\]

由此 \(f(a)=0\).

在 \((11)\), 令 \(x=0\), \(y=a\), 得

\[f(f(a))+f(0)=0+f(a)+af(0).\]

此即 \(2a=a^2\). 于是 \(a=0\) 或 \(2\).

在 \(a=0\), 即 \(f(0)=0\) 时.

在 \((11)\), 令 \(y=0\), 得

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

在 \((11)\), 令 \(y=1\), 得

\[f(x+f(x+1))+f(x)=x+f(x+1)+f(x).\]

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

在 \((11)\), 令 \(y=-x\), 得

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

在 \((14)\), 令 \(x=-1\), 得 \(f(-1)+f(-1)=-1+f(-1)\). 于是

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

在 \((14)\), 令 \(x=1\), 得 \(f(1)+f(-1)=1-f(1)\). 利用 \((15)\), 得 \(f(1)-1=1-f(1)\). 因而

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

在 \((11)\), 令 \(x=1\), \(y=x-1+f(x)\), 注意 \((16)\), 得

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

结合 \((12)\),\((13)\), 此即

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

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

在 \((11)\), 令 \(y=-1\), 得

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

结合 \((17)\), 此即

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

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

在 \((11)\), 将 \(x\) 换成 \(-x\), \(y\) 换成 \(x\), 得

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

\((14)\), \((19)\) 两式相减, 得

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

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

\((18)\) 说明这就是 \(2f(x)=2x\). 所以, \(f(x)=x\).

在 \(a=2\), 即 \(f(0)=2\) 时.

在 \((11)\), 令 \(y=1\), 得

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

在 \((11)\), 令 \(x=0\), \(y=x-1+f(x)\), 得

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

利用 \((20)\), 此即

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

故而, \(f(x)=2-x\).

经检验, \(f(x)=2-x\) 和 \(f(x)=x\) 确实符合要求.

综上所述, 所有的寻找的函数即是 \(f(x)=x\) 以及 \(f(x)=2-x\).

Problem 6 (Ross Atkins&Ivan Guo, Australia 澳大利亚)

考察 \(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\) 个正整数 \(z\), 使得不存在正整数 \(j\), 满足 \(d_j=z\). 换句话说, 集合 \(\{1, 2, 3, \dotsc\}\setminus\{d_1, d_2,\dotsc\}\) 的元素个数 \(b\), 成立 \(1\leqslant b\leqslant 2015\).

对每个正整数 \(j\geqslant1\), 记

\[N_j=\{1, 2, 3, \dotsc, j\},\;D_j=\{d_1, d_2, d_3, \dotsc, d_j\}.\]

设 \(L\gt2015\) 是任意的正整数. 对任意的正整数 \(j\), \(1\leqslant j\leqslant L-2015\),

\[d_j\leqslant j+2015\leqslant(L-2015)+2015=L,\]

于是, \(d_j\in N_L\). 注意 \(d_1\), \(d_2\), \(\dotsc\), \(d_{L-2015}\) 是 \(L-2015\) 个互不相同的正整数, 于是 \(N_L\cap\{d_1, d_2,\dotsc\}\) 的元素个数 \(\geqslant L-2015\). \(N_L\setminus\{d_1, d_2,\dotsc\}\), 进而 \(\{1, 2, 3, \dotsc\}\setminus\{d_1, d_2,\dotsc\}\), 的元素个数 \(\leqslant2015\).

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

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

取定一个正整数 \(N\gt\max\{z_1, z_2, \dotsc, z_b\}\).

设 \(n\) 和 \(m\) 是任意的满足 \(n\gt m\geqslant N\) 的整数.

\(Y\) 中的元素小于 \(N\), 当然更小于 \( m+2015\); \(D_m\) 中的元素 \(d_k\)(\(k\leqslant m\)) 必定 \(d_k\leqslant k+2015\leqslant m+2015\), 因此 \(Y\cup D_m\subset N_{m+2015}\). 此外, 当 \(k\leqslant m+1\) 时, \(k\) 要么属于 \(Y\), 要么存在正整数 \(t\lt k\), 使得 \(d_t=k\). 因此, \(N_{m+1}\subset Y\cup D_m\), \(Y\cup D_m\) 恰有 \(b-1\) 个元素属于 \(N_{m+2015}\setminus N_{m+1}\). 于是

\begin{equation}\sum_{k=1}^{m+b}k\leqslant\sum_{k=1}^md_k+\sum_{k=1}^bz_k\leqslant\sum_{k=1}^{m+1}k+\sum_{k=m+2017-b}^{m+2015}k.\end{equation}

当然, \((21)\) 中的 \(m\) 换成 \(n\) 也是成立的.

当 \(b=1\) 时,

\begin{equation}\sum_{k=1}^md_k+\sum_{k=1}^bz_k=\sum_{k=1}^{m+1}k,\end{equation}

\begin{equation}\sum_{k=1}^nd_k+\sum_{k=1}^bz_k=\sum_{k=1}^{n+1}k.\end{equation}

于是

\begin{equation}\sum_{k=m+1}^nd_k=\sum_{k=m+2}^{n+1}k.\end{equation}

\begin{equation}\sum_{k=m+1}^nd_k=\sum_{k=m+1}^n\Big(k+1\Big).\end{equation}

因 \(d_k=a_k+k\), \(b=1\), 这就是

\begin{equation}\sum_{k=m+1}^n\Big(a_k-b\Big)=0.\end{equation}

下面, 我们假定 \(b\geq2\).  由 \((21)\), 我们可有

\begin{equation}\left(\sum_{k=1}^nd_k+\sum_{k=1}^bz_k\right)-\left(\sum_{k=1}^md_k+\sum_{k=1}^bz_k\right)\geqslant\sum_{k=1}^{n+b}k-\left(\sum_{k=1}^{m+1}k+\sum_{k=m+2017-b}^{m+2015}k\right),\end{equation}

\begin{equation}\left(\sum_{k=1}^nd_k+\sum_{k=1}^bz_k\right)-\left(\sum_{k=1}^md_k+\sum_{k=1}^bz_k\right)\leqslant\left(\sum_{k=1}^{n+1}k+\sum_{k=n+2017-b}^{n+2015}k\right)-\sum_{k=1}^{m+b}k.\end{equation}

\((27)\) 即

\begin{equation}\sum_{k=m+1}^nd_k\geqslant\sum_{k=m+2}^{n+b}k-\sum_{k=m+2017-b}^{m+2015}k.\end{equation}

注意

\begin{equation}\sum_{k=m+2}^{n+b}k=\sum_{k=m+2}^{m+b}k+\sum_{k=m+b+1}^{n+b}k=\sum_{k=2}^b\Big(k+m\Big)+\sum_{k=m+1}^n\Big(k+b\Big).\end{equation}

\begin{equation}\sum_{k=m+2017-b}^{m+2015}k=\sum_{k=2}^b\Big(k+m+2015-b\Big)=\sum_{k=2}^b\Big(k+m\Big)+\sum_{k=2}^b\Big(2015-b\Big).\end{equation}

\((29)\) 就是

\begin{equation}\sum_{k=m+1}^nd_k\geqslant\sum_{k=m+1}^n\Big(k+b\Big)-\sum_{k=2}^b\Big(2015-b\Big).\end{equation}

\begin{equation}\sum_{k=m+1}^n\Big(d_k-k-b\Big)\geqslant-\sum_{k=2}^b\Big(2015-b\Big).\end{equation}

因为 \(d_k=a_k+k\), 所以

\begin{equation}\sum_{k=m+1}^n\Big(a_k-b\Big)\geqslant-\Big(b-1\Big)\Big(2015-b\Big).\end{equation}

类似的道理, \((28)\) 即, 当 \(n+1\geq m+b\) 时

\begin{equation}\sum_{k=m+1}^nd_k\leqslant\sum_{k=n+2017-b}^{n+2015}k+\sum_{k=m+b+1}^{n+1}k;\end{equation}

或, 当 \(n+1\lt m+b\) 时

\begin{equation}\sum_{k=m+1}^nd_k\leqslant\sum_{k=n+2017-b}^{n+2015}k-\sum_{k=n+2}^{m+b}k.\end{equation}

注意

\begin{equation}\begin{split}\sum_{k=n+2017-b}^{n+2015}k&=\sum_{k=2}^b\Big(k+n+2015-b\Big)\\&=\sum_{k=2}^b\Big(k+n\Big)+\sum_{k=2}^b\Big(2015-b\Big)\\&=\sum_{k=n+2}^{n+b}k+\sum_{k=2}^b\Big(2015-b\Big),\end{split}\end{equation}

于是, 当 \(n+1\geq m+b\) 时

\begin{equation}\begin{split}\sum_{k=m+1}^nd_k&\leqslant\sum_{k=m+b+1}^{n+1}k+\sum_{k=n+2}^{n+b}k+\sum_{k=2}^b\Big(2015-b\Big)\\&=\sum_{k=m+b+1}^{n+b}k+\sum_{k=2}^b\Big(2015-b\Big)\\&=\sum_{k=m+1}^n\Big(k+b\Big)+\sum_{k=2}^b\Big(2015-b\Big);\end{split}\end{equation}

当 \(n+1\lt m+b\) 时

\begin{equation}\begin{split}\sum_{k=m+1}^nd_k&\leqslant\sum_{k=n+2}^{n+b}k+\sum_{k=2}^b\Big(2015-b\Big)-\sum_{k=n+2}^{m+b}k\\&=\sum_{k=m+b+1}^{n+b}k+\sum_{k=2}^b\Big(2015-b\Big)\\&=\sum_{k=m+1}^n\Big(k+b\Big)+\sum_{k=2}^b\Big(2015-b\Big).\end{split}\end{equation}

故此, 无论哪一种情况, 因为 \(d_k=a_k+k\), 所以

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

综合 \((34)\), \((40)\), 利用算术几何平均不等式,

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

看到我们的魂牵梦绕.

Annotations

  1. 本届 IMO 其实不是最难, 恰恰相反, 应该是史上最简单, 大概与 1989 年相当. 分数低与训练有关, 不完全真实反映试题的难易.
  2. 题 1(a) 是陈题, 已经多次出现; 把 (a) 中对偶数 \(2k+2\) 构造的平衡点集的点 \(C\) 去掉, 得到的 \(2k+1\) 个点形成的点集亦是平衡的; 找出 (a) 所有符合要求的构造可能是困难的. 也就是说, 对整数 \(n\geq3\), 希望找出所有的由 \(n\) 个点构成的平衡点集.
  3. 题 3 的几何, 其实比最近几年的以 3 或 6 出现的几何简单很多. 通常, 如果考察的是三角形一些常见的点及其外接圆的性质, 不应当有太多人做不出的.
  4. 题 5 是函数方程. 一般来说, 一个函数方程可能是真正有难度的问题, 如果任何解法都避不了某关键的性质, 诸如特定集合的一个非常特殊的性质, 或者必须使用不等式.
 Posted by at 4:10 pm  Tagged with:
Jul 112015
 

                                      Day \(1\)

 Friday, July 10, 2015

Problem 1. We say that a finite set \(\mathcal S\) of points in the plane is balanced if, for any two different points \(A\) and \(B\) in \(\mathcal{S}\), there is a point \(C\) in \(\mathcal{S}\) such that \(AC=BC\). We say that \(\mathcal{S}\) is centre-free if for any three different points \(A\), \(B\) and \(C\) in \(\mathcal{S}\), there is no points \(P\) in \(\mathcal{S}\) such that \(PA=PB=PC\).

(a) Show that for all integers \(n\ge 3\), there exists a balanced set consisting of \(n\) points.

(b) Determine all integers \(n\ge 3\) for which there exists a balanced centre-free set consisting of \(n\) points.

Problem 2.  Determine all triples \((a, b, c)\) of positive integers such that each of the numbers

\[ab-c,\;bc-a, \;ca-b\]

is a power of \(2\).

(A power of \(2\) is an integer of the form \(2^n\), where \(n\) is a non-negative integer. )

Problem 3. Let \(ABC\) be an acute triangle with \(AB \gt AC\). Let \(\Gamma\) be its cirumcircle, \(H\) its orthocenter, and \(F\) the foot of the altitude from \(A\). Let \(M\) be the midpoint of \(BC\). Let \(Q\) be the point on \(\Gamma\) such that \(\angle HQA = 90^{\circ}\) and let \(K\) be the point on \(\Gamma\) such that \(\angle HKQ = 90^{\circ}\). Assume that the points \(A\), \(B\), \(C\), \(K\) and \(Q\) are all different, and lie on \(\Gamma\) in this order.

Prove that the circumcircles of triangles \(KQH\) and \(FKM\) are tangent to each other.

                                      Day \(2\)

 Saturday, July 11, 2015

Problem 4. Triangle \(ABC\) has circumcircle \(\Omega\) and circumcenter \(O\). A circle \(\Gamma\) with center \(A\) intersects the segment \(BC\) at points \(D\) and \(E\), such that \(B\), \(D\), \(E\), and \(C\) are all different and lie on line \(BC\) in this order. Let \(F\) and \(G\) be the points of intersection of \(\Gamma\) and \(\Omega\), such that \(A\), \(F\), \(B\), \(C\), and \(G\) lie on \(\Omega\) in this order. Let \(K\) be the second point of intersection of the circumcircle of triangle \(BDF\) and the segment \(AB\). Let \(L\) be the second point of intersection of the circumcircle of triangle \(CGE\) and the segment \(CA\).

Suppose that the lines \(FK\) and \(GL\) are different and intersect at the point \(X\). Prove that \(X\) lies on the line \(AO\).

Problem 5. Let \(\Bbb R\) be the set of real numbers. Determine all functions \(f\colon\Bbb R\to\Bbb R\) satisfying the equation

\[f(x+f(x+y))+f(xy)=x+f(x+y)+yf(x)\]

for all real numbers \(x\) and \(y\).

Problem 6. The sequence \(a_1,a_2,\dotsc\) of integers satisfies the following conditions:

(i) \(1\leqslant a_j\leqslant2015\) for all \(j\geqslant1\);

(ii) \(k+a_k\neq \ell+a_\ell\) for all \(1\leqslant k\lt \ell\).

Prove that there exist two positive integers \(b\) and \(N\) such that

\[\left\vert\sum_{j=m+1}^n(a_j-b)\right\vert\leqslant1007^2\]

for all integers \(m\) and \(n\) satisfying \(n\gt m\geqslant N\).

 Posted by at 4:00 pm  Tagged with:
Jul 232014
 

2014 第 55 届 IMO 评注

楔子

第一次用超过一篇文章写 IMO 的解答. 前文 IMO 2014 solutions 已经很长, 不妨重新开始.

这续集不能仅仅只是解答, 希望有背景的讨论和更深入的研究. 要完成这样的目标, 我们需要查阅相关课题的研究文献, 也需要思考.

陶哲轩在 1999-2012 期间, 四个 mini-polymath discussions, 每年挑选一道当年的 IMO 试题, 供大家各抒己见. 这道题不一定是最难的(虽然常常如此), 但一定是最有 “内涵” 的. 去年夏天, 陶已经有两个 polymath projects 在进行, 所以没有继续讨论 IMO.

19 日, 1998 年的 Fields Medal 得主 Timothy Gowers 在他的 wordpress 博客开了一个 Mini-monomath, 讨论今年 IMO 的一道题. 很遗憾, Gowers 品尝的是第一题.

Problem 1

先看看 Gower 的解法. But frankly, it is difficult to understand what he said.

Without loss of generality, 可以假定 \(a_0=1\).

Problem 5

2000 IMO Problem 3

2000 年第 41 届 IMO 是在韩国(Republic of Korea)大田举办的. 这届赛事的第三题是这样的:

Problem 3. \(k\) is a positive real. \(N\) is an integer greater than \(1\). \(N\) points are placed on a line, not all coincident. A move is carried out as follows. Pick any two points \(A\) and \(B\) which are not coincident. Suppose that \(A\) lies to the right of \(B\). Replace \(B\) by another point \(B^\prime\) to the right of \(A\) such that \(AB^\prime = kBA\). For what values of \(k\) can we move the points arbitrarily far to the right by repeated moves?

3. 设 \(n\geqslant2\) 为正整数. 开始时,在一条直线上有 \(n\) 只跳蚤, 且它们不全在同一点. 对任意给定的一个正实数 \(\lambda\), 可以定义如下的一种 “移动”:
(1) 选取任意两只跳蚤, 设它们分别位于点 \(A\) 和 \(B\), 且 \(A\) 位于 \(B\) 的左边;
(2) 令位于点 \(A\) 的跳蚤跳到该直线上位于点 \(B\) 右边的点 \(C\), 使得 \(\dfrac{BC}{AB}=\lambda\).
试确定所有可能的正实数\(\lambda\), 使得对于直线上任意给定的点 \(M\) 以及这 \(n\) 只跳蚤的任意初始位置, 总能够经过有限多个移动之后令所有的跳蚤都位于 \(M\) 的右边.

中等数学 2000 年第 5 期的解答是比较长的. 我没有看过多少最近出版的竞赛辅导书, 剪刀浆糊写书的人估计都会复制这个答案. 单墫在修订他的 “数学竞赛研究教程”(应该是他最厚的书了)的时候, 把这题收录为最后的 50 个综合习题的第 19 道. 单老师在这书给的是另一种解法, 但我不得不说, 这解答很难认为是完美的: 我最初第一眼看到这题进行的尝试就是这种做法. 但我思考良久, 认为此种思路难以说的清清楚楚明明白白, 最终抛弃这个做法.

这个题其实有一个两句话的办法. 为什么是两句话, 而不是一句?

2014 IMO 题 5 的解答一为什么那么复杂?

提起 14 年前的考题, 意欲何为?

Lemma 4  设 \(m\)(\(\leq 2l\)) 是正整数, 把 \(m\) 表成 \(m=2^a\cdot b\), 这里 \(a\) 是非负整数, \(b\gt0\) 是奇数, 则 \(a\leq l\), \(b\leq 2l-1\).

首先说明, 若 \(x\) 是一个整数, 则

  • \(2^x\geq x+1\);
  • \(2^x\geq2x\).

这两个不等式实际是同一件事. 我们先看第一个:

在 \(x\leq-1\) 时, \(2^x\gt0\geq x+1\);

在 \(x=0\) 时,  不等式的等号成立: \(2^x=2^0=1\), \(x+1=0+1=1\);

若 \(x\gt0\), 据二项式定理

\[2^x=\dbinom x0+\dbinom x1+\dbinom x2+\dotsb+\dbinom xx\geq\dbinom x0+\dbinom x1=x+1.\]

第二个不等式容易由第一个推得: 第一个不等式的两边乘以 \(2\), 得

\[2\cdot2^x=2^{x+1}\geq2(x+1).\]

把 \(x\) 换成 \(x-1\), 可得第二个不等式.

现在,

\[2l\geq m=2^a\cdot b\geq2^a\geq2a\]

定出 \(l\geq a\).

然后,

\[2l\geq m=2^a\cdot b\geq b,\]

结合 \(b\) 是奇数, 即可导出 \(b\leq 2l-1\).

 Posted by at 5:34 pm  Tagged with: