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

2014 第 55 届 IMO 解答

Problem 1 (Austria)

记 \(b_k=\sum\limits_{i=0}^ka_i-ka_k\), \(k=1\), \(2\), \(\dotsc\).

注意 \(\dfrac{a_0+a_1+a_2+\dotsb+a_n}n\gt a_n\) 就是 \(\sum\limits_{i=0}^na_i-na_n\gt0\). 后者显然即 \(b_n\gt0\).

然后, \(\dfrac{a_0+a_1+a_2+\dotsb+a_n}n\leq a_{n+1} \) 的另一面目 \(\sum\limits_{i=0}^{n+1}a_i\leq (n+1)a_{n+1}\) 就是 \(b_{n+1}\leq0\). 从而, 我们只需指出有惟一的正整数 \(n\), 使得

\begin{equation}b_n\gt0\geq b_{n+1}.\end{equation}

显而易见, \(b_1=a_0\gt0\). 从

\[b_k-b_{k+1}=\Big(\sum_{i=0}^ka_i-ka_k\Big)-\Big(\sum_{i=0}^{k+1}a_i-(k+1)a_{k+1}\Big)=k(a_{k+1}-a_k)\geq k\]

(\(k=1\), \(2\), \(\dotsc\)) 知道 \(b_k\) 是严格单调递减的整数列. 至此, 我们断言恰有惟一的正整数 \(n\) 使得 \((1)\) 成为事实.

Problem 2 (Tonći Kokan, Croatia)

问题本身其实非常简单, 难度 C, 只有资格成为 Q1 或者 Q4. 但, 要把证明写的完整没有漏洞, 确是要伤不少脑细胞.

写这个答案, 容易出现的问题有:

  • 默认(而不证明) \(k\) 是随  \(n\) 的增加而(不严格)增加;
  • 忘记了当 \(n\) 不是完全平方时的构造;
  • 只给出了构造, 没有证明你的构造符合要求. 所以, 如何构造也很关键: 构造不简洁, 证明也会麻烦.

要找寻的最大的正整数 \(k=\left\lceil\sqrt n\right\rceil-1\).

把位于第 \(i\) 行第 \(j\) 列的单位正方形记为 \((i, j)\). 以下为论述方便, 把 “车” 用其所在的单位正方形来标记. 此外, 左上角的单位正方形是 \((i, j)\) 的 \(m\times m\) 的正方形记为 \(A_{i, j}(m)\).

记正整数 \(q\) 使得 \(q^2\lt n\leq (q+1)^2\).

首先, 对于任何一种和平放置 \(n\) 个 “车” 的方案, 都存在一个 \(q\times q\) 的正方形, 它的 \(q^2\) 个单位正方形里都没有”车”.

事实上, 对于一种和平放置 \(n\) 个 “车” 的方案, 设第 \(n\) 行的 “车” 是 \((n,a)\), 这里 \(1\leq a\leq n\). 任取棋盘的 \(q\) 个连续的列, 无妨记为第 \(b\), \(b+1\), \(b+2\), \(\dotsc\), \(b+q-1\) 列, \(1\leq b\leq b+q-1\leq n\), 仅仅要求第 \(a\) 列是这 \(q\) 列中的一员, 即 \(b\leq a\leq b+q-1\).

考虑棋盘的第 \(1\), \(2\), \(\dotsc\), \(q^2\) 行, 第 \(b\), \(b+1\), \(\dotsc\), \(b+q-1\) 列交叉点处的 \(q^3\) 个单位正方形组成的一个 \(q^2\times q\) 的长方形. 这长方形可以分为 \(q\) 个 \(q\times q\) 的正方形: \(A_{1, b}(q)\), \(A_{1+q, b}(q)\), \(A_{1+2q, b}(q)\), \(\dotsc\), \(A_{1+q(q-1), b}(q)\).

\(q^2\lt n\) 蕴含这 \(q\) 个 \(q\times q\) 的正方形中的 \(q^3\) 单位正方形都绝然不会落在棋盘的第 \(n\) 行.

既然棋盘每一列上都恰好有一个 “车”, 并且第 \(a\) 列的 “车” 在第 \(n\) 行, 那么棋盘每一列的前 \(q^2\) 行最多只有一个”车”, 并且第 \(a\) 列的前 \(q^2\) 行绝然没有 “车”. 由此, 我们断言: 至多有 \(q-1\) 个”车” 放置在这 \(q\) 个 \(q\times q\) 的正方形中. 故而, 必有 \(l\)(\(0\leq l\leq q-1\)), 使得 \(A_{1+lq, b}(q)\) 的 \(q^2\) 个单位正方形里都没有”车”. 换言之, 对一种和平放置 \(n\) 个 “车” 的方案, 必存在一个 \(q\times q\) 的正方形, 它的 \(q^2\) 个单位正方形里都没有”车”.

至此, 我们知道: \(k\geq q\).

为了找出一种和平放置 \(n\) 个 “车” 的方案, 使得对于任意一个 \((q+1)\times (q+1)\) 的正方形, 它的 \((q+1)^2\) 个单位正方形里至少有一个”车”, 我们先建立下面的

Lemma 1 \(a\), \(b\) 跑遍 \(1\), \(2\), \(\dotsc\), \(q+1\) 时, \((a-1)(q+1)+b\) 不重复不遗漏列出 \(1\), \(2\), \(\dotsc\), \((q+1)^2\).

首先断言, 对两个不同的有序整数对 \((a, b)\) 与 \((a^\prime, b^\prime)\)(\(1\leq a\), \(b\) , \(a^\prime\), \(b^\prime\leq q+1\)), 必有

\[(a-1)(q+1)+b\ne(a^\prime-1)(q+1)+b^\prime.\]

因此, 当 \(a\), \(b\) 跑遍 \(1\), \(2\), \(\dotsc\), \(q+1\) 时, \((a-1)(q+1)+b\) 恰有 \(\big(q+1\big)\big(q+1\big)=\big(q+1\big)^2\) 种不同的值.

事实上, 若有

\[(a-1)(q+1)+b=(a^\prime-1)(q+1)+b^\prime. \]

则 \((q+1)|(b-b^\prime)\). 由于 \(1\leq b\) , \(b^\prime\leq q+1\), 故 \(-q\leq b-b^\prime\leq q\). 至此, 我们可有 \(b=b^\prime\). 进而, \(a=a^\prime\).

然后,  注意

\[1\leq (a-1)(q+1)+b\leq \big((q+1)-1\big)\big(q+1\big)+\big(q+1\big)=\big(q+1\big)^2,\]

于是, \((a-1)(q+1)+b\) 的 \((q+1)^2\) 种不同的值恰好就是: \(1\), \(2\), \(\dotsc\), \((q+1)^2\).

Lemma 2 设 \(n\geq2\) 是一个整数. 考虑由 \(n^2\) 个单位正方形组成的一个 \(n\times n\) 棋盘. 一种放置 \(m\)(\(0\leq m\leq n\))个棋子”车” 的方案被称为是可和平的, 如果可以再放置 \(n-m\) 个棋子”车”, 得到一种和平的方案, 即每一行和每一列上都恰好有一个”车”. 那么, 一种放置 \(m\)(\(0\leq m\leq n\))个棋子”车” 的方案, 如果每一行和每一列上都至多有一个”车”, 则此种方案是可和平的.

事实上, 设第 \(i_1\), \(i_2\), \(\dotsc\), \(i_{n-m}\) 行, 第 \(j_1\), \(j_2\), \(\dotsc\), \(j_{n-m}\) 列没有”车”, 且 \(1\leq i_1\lt i_2\lt\dotsb\lt i_{n-m}\leq n\), \(1\leq j_1\lt j_2\lt \dotsb\lt j_{n-m}\leq n\). 只要在 \((i_1, j_1)\), \((i_2, j_2)\), \(\dotsc\), \((i_{n-m}, j_{n-m})\) 这 \(n-m\) 个单位正方形放置”车” 即可.

Lemma 2 表明, 只要找到 \(n\times n\) 棋盘的一种放置 \(\leq n\) 个棋子 “车” 的可和平的方案, 使得在任意一个 \((q+1)\times (q+1)\) 的正方形, 它的 \((q+1)^2\) 个单位正方形里至少有一个”车”.

这是因为, 在一个已经放置了一些”车”, 使得每一个 \((q+1)\times (q+1)\) 的正方形里有”车”, 的 \(n\times n\) 棋盘再放进一些新棋子 “车”, 其任意一个 \((q+1)\times (q+1)\) 的正方形的 \((q+1)^2\) 个单位正方形里, 既然有新棋子”车”之外的旧棋子”车”, 必定依然有”车”.

进一步, 我们只需要指出 \((q+1)^2\times (q+1)^2\) 棋盘的一种放置 \((q+1)^2\) 个棋子 “车” 的和平方案, 使得对于任意一个 \((q+1)\times (q+1)\) 的正方形, 它的 \((q+1)^2\) 个单位正方形里都有”车”.

这是因为, 此时这 \((q+1)^2\times (q+1)^2\) 棋盘左上角的 \(n\times n\) 的正方形放置 “车” 的方案是可和平的, 并且在这 \(n\times n\) 正方形的任意一个 \((q+1)\times (q+1)\) 的正方形, 它的 \((q+1)^2\) 个单位正方形里必定有”车”.

事实上, 既然这个 \((q+1)^2\times (q+1)^2\) 棋盘的每一行和每一列上都恰有一个 ”车”, 其左上角的 \(n\times n\) 的正方形棋盘的每一行和每一列上显然都至多只有一个”车”. 于是, Lemma 2 表明这个 \(n\times n\) 棋盘放置 “车” 的方案是可和平的. 其次, 既然这个 \(n\times n\) 棋盘的任意一个 \((q+1)\times (q+1)\) 的正方形亦是此 \((q+1)^2\times (q+1)^2\) 棋盘的一个 \((q+1)\times (q+1)\) 正方形, 它的 \((q+1)^2\) 个单位正方形里当然都有”车”.

考虑由 \((q+1)^4\) 个单位正方形组成的一个 \((q+1)^2\times (q+1)^2\) 棋盘.

我们仔细揣摩集合

\begin{equation}\color{red}{S=\bigg\{\Big((a-1)(q+1)+b, (b-1)(q+1)+a\Big)| a, b=1, 2, \dotsc, q+1\bigg\}}.\end{equation}

Lemma 1 说明 \(S\) 是这个 \((q+1)^2\times (q+1)^2\) 棋盘的 \((q+1)^4\) 个单位正方形组成的集合的子集, 并且这棋盘的每行恰有一个 \(S\) 中的单位正方形, 每列亦恰一个\(S\) 中的单位正方形. 故而, \(S\) 中的单位正方形恰好有 \((q+1)^2\) 个. 我们在 \(S\) 中的每个单位正方形各放置一个棋子 “车”, 即在棋盘的 \((q+1)^2\) 个单位正方形 \(\big((a-1)(q+1)+b, (b-1)(q+1)+a\big)\) 各放置一个 “车”, \(a\), \(b=1\), \(2\), \(\dotsc\), \(q+1\), 那么这种放置 \((q+1)^2\) 个棋子 “车” 的方案是和平的.

其次, 在 \(1\leq i\), \(j\leq (q+1)^2-q\) 时, \(A_{i, j}(q+1)\) 的 \((q+1)^2\) 个单位正方形里至少有一个”车”.

事实上, 必定有整数 \(\color{red}s\), \(\color{red}t\), 适合 \(\color{red}{0\leq s}\), \(\color{red}{t\leq q}\), 使得 \(\color{red}{(i+s, j+t)\in S}\).

Lemma 1 表明 \(i\), \(j\) 可以表成 \(i=(a-1)(q+1)+b\), \(j=(a^\prime-1)(q+1)+b^\prime\), 这里 \(1\leq a\), \(b\) , \(a^\prime\), \(b^\prime\leq q+1\).

要注意的是: 如果 \(b\geq2\), 必定 \(a\leq q\); 如果 \(b^\prime\geq2\), 必定 \(a^\prime\leq q\).

这是因为, 在 \(b\geq 2\) 为真的情形下,

\[(q+1)^2-q\geq i=(a-1)(q+1)+b\geq (a-1)(q+1)+2.\]

换言之, 有 \(q(q+1)-1\geq (a-1)(q+1)\), 进而

\[q(q+1)\gt(a-1)(q+1).\]

于是, \(q\gt a-1\). 我们已经得到 \(a\lt q+1\).

类似, \(b^\prime\geq2\) 蕴含 \(a^\prime\leq q\).

当 \(b\leq a^\prime\), \(b^\prime\leq  a\) 时, 令 \(s=a^\prime-b\), \(t=a-b^\prime\). 显然 \(0\leq s\), \(t\leq q\). 于是

\[i+s=(a-1)(q+1)+a^\prime, \quad j+t=(a^\prime-1)(q+1)+a.\]

当 \(b\gt a^\prime\), \(b^\prime\leq  a+1\) 时,  令 \(s=(q+1)-(b-a^\prime)\), \(t=(a+1)-b^\prime\). 显然 \(0\leq s\leq q\). 注意, \(b\gt a^\prime\geq1\) 说明 \(b\geq2\), 故此 \(a\leq q\), 进而 \(0\leq t\leq q\). 于是

\[i+s=a(q+1)+a^\prime,\quad j+t=(a^\prime-1)(q+1)+(a+1).\]

当 \(b\leq a^\prime+1\), \(b^\prime\gt  a\), 令 \(s=(a^\prime+1)-b\), \(t=(q+1)-(b^\prime-a)\). 显然 \(0\leq t\leq q\). 注意, \(b^\prime\gt a\geq1\) 说明 \(b^\prime\geq2\), 故此 \(a^\prime\leq q\), 进而 \(0\leq s\leq q\). 于是

\[i+s=(a-1)(q+1)+(a^\prime+1), \quad j+t=a^\prime(q+1)+a.\]

当 \(b\geq a^\prime+2\), \(b^\prime\geq  a+2\), 令 \(s=(q+1)-(b-a^\prime-1)\), \(t=(q+1)-(b^\prime-a-1)\). 显然 \(0\leq s\), \(t\leq q\). 此时 \(b\gt2\), \(b^\prime\gt2\) 定出 \(a\leq q\), \(a^\prime\leq q\). 于是

\[i+s=a(q+1)+(a^\prime+1),\quad j+t=a^\prime(q+1)+(a+1).\]

无论哪一种情况, 我们都可以看到 \((i+s, j+t)\in S\).

至此, 我们断定 \(k\lt q+1\).

综合起来, \(k=q=\left\lfloor\sqrt{n-1}\right\rfloor\).

Problem 3 (Iran)

这个第一天的压轴题, 平均分 \(0.505\), 考场上有 \(32\) 人做出: \(28\) 人得 \(7\) 分, \(4\) 人得 \(6\) 分. 这个不是本届 IMO 最难的, 比第二天的最后一题简单.

平面几何通常会有很多解答. 我们试着找出几个. 第一个解答的入选准则是

  • 几何味道纯正浓烈. 换言之, 不使用代数办法, 不使用余弦定理, 尽可能不出现平方, 想法设法避免使用勾股定理, 正弦定理和相似三角形的比例;
  • 只使用教科书的定理, 竞赛选手都知道的公式;
  • 解答简单, 优美.

注意, 我们把简单漂亮的标准仅仅排第三.

IMO 2014 Problem 3 Proof 1

IMO 2014 Problem 3 Proof 1

设点 \(C\) 关于 \(B\), \(D\) 的对称点分别为 \(E\), \(F\). \(EF\) 的中点记为 \(M\).

\(\angle ABC=\angle ADC=90^\circ\) 说明 \(AB\), \(AD\) 分别是线段 \(CE\), \(CF\) 的中垂线. 进而, \(A\) 是 \(\triangle ECF\) 的外心, \(MA\) 是 \(EF\) 的中垂线, \(SE=SC\), \(TC=TF\), 以及 \(\angle SEC=\angle SCE\), \(\angle TCF=\angle TFC\).

\(BD\) 是 \(\triangle ECF\) 的中位线, 所以 \(BD\parallel EF\). 结合 \(AM\perp EF\), \(AH\perp BD\) 导出 \(M\), \(A\), \(H\) 三点共线. \(HM\) 是 \(EF\) 的中垂线说明 \(HE=HF\).

然后,

\[\angle CHS=\angle CSB+90^\circ=\angle CSB+\angle SBC=180^\circ-\angle SCB=180^\circ-\angle SEC\]

给出 \(E\), \(C\), \(H\), \(S\) 四点共圆. 类似, \(H\), \(C\), \(F\), \(T\) 亦四点共圆. 于是

\begin{equation*}\begin{split}\angle SHT &=360^\circ-\angle CHS-\angle CHT\\&=360^\circ-(180^\circ-\angle SEC)-(180^\circ-\angle TFC)\\&=\angle SEC+\angle TFC\\&=\angle SCE+\angle TCF\\&=\angle SHE+\angle THF\\&=\angle EHF-\angle SHT,\end{split}\end{equation*}

我们可有

\[\angle SHT=\frac12\angle EHF.\]

另一方面, \(HE=HF\), \(HM\perp EF\) 蕴含 \(\angle MHE=\dfrac12\angle EHF\). 故此, \(\angle SHT=\angle MHE\), 即

\[\angle SHA+\angle THA=\angle SHA+\angle SHE.\]

这可得到

\begin{equation}\color{red}{\angle THA=\angle SHE=\angle SCE}.\end{equation}

这是一个紧要之处!

在 \(HC\) 的延长线上取点 \(N\), 使得 \(HN=HE=HF\). \(H\) 是 \(\triangle NEF\) 的外心, 故

\[\angle FNE=\frac12\angle EHF.\]

从而

\begin{equation}\color{red}{\angle FNE=\angle SHT}.\end{equation}

注意 \(\triangle HEN\) 与 \(\triangle SEC\) 都是等腰三角形, 并且顶角相等: \(\angle EHN=\angle ESC\). 于是

\begin{equation}\color{red}{\angle CNE=\angle SCE}=\angle SHE.\end{equation}

然后, 由 \(E\), \(C\), \(H\), \(S\) 四点共圆, 得知 \(\angle ECN=\angle ESH\). 现在可以断定 \(\triangle NEC\sim\triangle HES\). 顺水推舟的,

\[\frac{NE}{NC}=\frac{HE}{HS}.\]

类似, \(\triangle NFC\sim\triangle HFT\) 导出

\[\frac{NF}{NC}=\frac{HF}{HT}.\]

至此

\[\frac{\frac{NE}{NC}}{\frac{NF}{NC}}=\frac{\frac{HE}{HS}}{\frac{HF}{HT}}.\]

再结合 \(HE=HF\) 可看到

\[\frac{NE}{NF}=\frac{HT}{HS}.\]

这说明

\begin{equation}\triangle NEF\sim\triangle HTS.\end{equation}

既然 \(\triangle NEF\) 的外心 \(H\) 落在 \(NC\) 上, 以及早已知道的 \(\angle ENC=\angle SCE\) 和 \(\angle THA=\angle SCE\) 的可以立刻写下的水到渠成的

\begin{equation}\color{red}{\angle ENC=\angle THA},\end{equation}

我们可断言 \(\triangle HTS\) 的外心必定位于 \(HA\) 上. 然后, 从 \(AH\perp BD\) 可以判定直线 \(BD\) 与三角形 \(TSH\) 的外接圆相切.

Problem 4 (Georgia)

这个就要简单的多了. 复数, 向量, 解析, 这些考虑, 不是我们的关心对象.

这个证明甚至不需要辅助线.

IMO 2014 Problem 4 Proof 1

IMO 2014 Problem 4 Proof 1

由 \(\angle PAB=\angle QCA\) 断定

\[\angle APB=180^\circ-\angle PAB-\angle ABP=180^\circ-\angle QCA-\angle ABP=\angle BAC.\]

又因为 \(\angle ABP=\angle CAQ\) , 故 \(\triangle PAB\sim\triangle QCA\). 于是

\[\frac{PA}{PB}=\frac{QC}{QA}.\]

因为 \(PA=PM\), \(QA=QN\), 于是

\[\frac{PM}{PB}=\frac{QC}{QN}.\]

\[\angle MPB=\angle PAB+\angle ABP=\angle QCA+\angle CAQ=\angle CQN,\]

得知  \(\triangle MPB\sim\triangle CQN\). 进而, \(\angle BMP=\angle NCQ\).

若设直线 \(BM\) 和 \(CN\) 的交点是 \(D\), 则

\[\angle MDC =\angle DBC+\angle DCB=\angle DBC+\angle BMP=\angle APB=\angle BAC,\]

这便得出了 \(A\), \(B\), \(D\), \(C\) 四点共圆.

Problem 5 (Luxembourg)

这个, 一般使用数学归纳法.

这个题的难度仅次于题 3 和题 6. 考试的成绩, 这个第 5 题, 平均分 \(1.709\), 考场上有 \(95\) 人做出: \(84\) 人得 \(7\) 分, \(11\) 人得 \(6\) 分. 在总分前五的国家(地区)中, 没有做出来的队员有 \(9\) 人: 中国的黄一山得了 \(0\) 分; 美国有一个 \(2\) 分, 一个 \(1\) 分; 台湾有一个 \(2\) 分, 一个 \(0\) 分; 俄罗斯有一个 \(1\) 分, 一个 \(0\) 分, 一个 \(2\) 分; 日本有一个 \(2\) 分.

中国国家集训队曾经出现过类似的题. 2006 年中国国家队选拔考试题 2, 出自陈永高之手, 是这样的:

给定正整数 \(n\), 求最大的实数 \(C\), 满足: 若一组大于 \(1\) 的整数(可以有相同的)的倒数之和小于 \(C\), 则一定可以将这一组数分成不超过 \(n\) 组, 使得每一组数的倒数之和都小于 \(1\).

标准答案使用的是数学归纳法.

眼前的这个 IMO 题, 也是这个做法. 先将命题一般化. 这是数学归纳法的常见技巧. 苏淳在他的小册子”漫话数学归纳法”(这书刚出道, 以”漫话数学归纳法的应用技巧” 为面目示人)专门用一节讲解这个方法.

我们来证明: \(l\) 是一个正整数. 那么, 给定总额不超过 \(l-\dfrac12\) 的有限多个这样的硬币(面值不必两两不同), 可以把它们分为至多 \(l\) 组, 使得每一组中硬币的面值之和最多是 \(1\).

如何写这个解答, 尽管比第 2 题简单, 也需一些细心的权衡.

对 \(l\) 进行归纳.

奠基显然: \(l=1\) 时, 这些硬币的面值总额不超过 \(\dfrac12\), 更小于 \(1\).

假定总可以把总额不超过 \(l-\dfrac32\) 的有限多个这样的硬币(面值不必两两不同)分为至多 \(l-1\) 组, 使得每一组中硬币的面值之和最多是 \(1\), 这里正整数 \(l\geq2\). 我们来考虑任意给定的总额不超过 \(l-\dfrac12\) 的有限多个这样的硬币(面值不必两两不同).

设在这给定的有限多个硬币中, 面值为 \(\dfrac1n\) 的硬币有 \(T(n)\) 个, \(n=1\), \(2\), \(\dotsc\).

取正整数 \(N\), 使得这些硬币中的任何一个的面值都 \(\gt\dfrac1{2^N}\).

对任一适合 \(1\leq k\leq l\) 的正整数 \(k\), 记这些硬币中面值为 \(\dfrac1{2k-1}\) 的硬币, 面值为 \(\dfrac1{2(2k-1)}\) 的硬币, 面值为 \(\dfrac1{2^2(2k-1)}\) 的硬币, \(\dotsc\), 面值为 \(\dfrac1{2^N(2k-1)}\) 的所有硬币组成的集合是 \(C_k\).

注意, 当 \(T(n)\gt0\) 时, 设 \(n=2^a\cdot b\), 这里 \(a\) 是非负整数, \(b\gt0\) 是奇数, 则 \(\dfrac1n\gt\dfrac1{2^N}\) 即

\[n=2^a\cdot b\lt2^N,\]

于是 \(2^a\lt2^N\), 进而 \(a\lt N\). 此外, 不超过 \(2l\) 的奇数有 \(l\) 个: \(1\), \(3\), \(\dotsc\), \(2l-1\). 故此, 在 \(T(n)\gt0\) 且 \(n\leq2l\) 时, 必有整数 \(k\), \(a\), 适合 \(1\leq k\leq l\), \(0\leq a\lt N\), 使得

\[n=2^a(2k-1),\]

进而面值为 \(\dfrac1n\) 的硬币全部在 \(C_k\) 中. 换言之, 任一面值为 \(\dfrac1n\)(\(n\leq2l\)) 的硬币必定在 \(C_1\), \(C_2\), \(\dotsc\), \(C_l\) 中的一个.

\(C_k\) 中的硬币的面值之和是

\[V_k=\sum_{i=0}^N\frac{T\big(2^i(2k-1)\big)}{2^i(2k-1)}=\frac1{2k-1}\sum_{i=0}^N\frac{T\big(2^i(2k-1)\big)}{2^i}.\]

  • 如果有某个 \(V_k\geq1\), \(1\leq k\leq l\);

我们来证明: 必有一些硬币的面值总额恰好为 \(1\).

在 \(T(2k-1)\geq2k-1\) 的情形下, \(2k-1\) 个面值为 \(\dfrac1{2k-1}\) 的硬币的面值之和是 \(1\).

相反的情况, 即 \(T(2k-1)\lt2k-1\) 时, 注意

\[\frac{T\big(2k-1\big)}{2k-1}\lt1, \quad V_k=\frac1{2k-1}\sum_{i=0}^N\frac{T\big(2^i(2k-1)\big)}{2^i}\geq1.\]

从而, 存在惟一的 \(j\), 满足 \(0\leq j\lt N\), 使得

\[\frac1{2k-1}\sum_{i=0}^j\frac{T\big(2^i(2k-1)\big)}{2^i}\lt1\leq\frac1{2k-1}\sum_{i=0}^{j+1}\frac{T\big(2^i(2k-1)\big)}{2^i}.\]

\[\sum_{i=0}^j\frac{T\big(2^i(2k-1)\big)}{2^i}\lt2k-1\leq\sum_{i=0}^{j+1}\frac{T\big(2^i(2k-1)\big)}{2^i}.\]

进而, 我们有

\[0\lt\big(2k-1\big)-\sum_{i=0}^j\frac{T\big(2^i(2k-1)\big)}{2^i}\leq \frac{T\big(2^{j+1}(2k-1)\big)}{2^{j+1}},\]

\[0\lt2^{j+1}\big(2k-1\big)-\sum_{i=0}^j2^{j+1-i}T\big(2^i(2k-1)\big)\leq T\big(2^{j+1}(2k-1)\big).\]

令 \(s=2^{j+1}\big(2k-1\big)-\sum\limits_{i=0}^j2^{j+1-i}T\big(2^i(2k-1)\big)\), 则 \(0\lt s \leq T\big(2^{j+1}(2k-1)\big)\), 并且

\[\frac s{2^{j+1}}=\big(2k-1\big)-\sum_{i=0}^j\frac{T\big(2^i(2k-1)\big)}{2^i}.\]

换言之,

\begin{equation}\color{red}{\frac1{2k-1}\sum_{i=0}^j\frac{T\big(2^i(2k-1)\big)}{2^i}+\frac s{2^{j+1}(2k-1)}=1}.\end{equation}

这等式表明: \(T\big(2k-1\big)\) 个面值为 \(\dfrac1{2k-1}\) 的硬币, \(T\big(2(2k-1)\big)\) 个面值为 \(\dfrac1{2(2k-1)}\) 的硬币, \(T\big(2^2(2k-1)\big)\) 个面值为 \(\dfrac1{2^2(2k-1)}\) 的硬币, \(\dotsc\), \(T\big(2^j(2k-1)\big)\) 个面值为 \(\dfrac1{2^j(2k-1)}\) 的硬币, 和 \(s\) 个面值为 \(\dfrac1{2^{j+1}(2k-1)}\) 的硬币的面值之和恰好是 \(1\).

把这些面值之和为 \(1\) 的硬币分为一组, 然后, 剩下的总额不超过 \(l-\dfrac32\) 的有限多个硬币, 据归纳假设, 可以分成至多 \(l-1\) 组, 使得每一组中硬币的面值之和最多是 \(1\). 如此我们就把所有的硬币分为了至多 \(l\) 组, 使得每一组中硬币的面值之和最多是 \(1\).

  • 如果所有的 \(V_k\lt1\), \(k=1\), \(2\), \(\dotsc\), \(l\).

Lemma 3  给定总额不超过 \(l-\dfrac12\) 的分为 \(l\) 组的硬币, 并且每一组中硬币的面值之和最多是 \(1\). 那么, 对于再拿来的一个面值为 \(\dfrac1a\) (\(a\gt 2l\)) 的新硬币, 必定存在一组, 使得这组中的所有硬币的面值与这个新硬币的面值的和仍然最多是 \(1\).

事实上, 既然这 \(l\) 组硬币的总额不超过 \(l-\dfrac12\), 必有一组中的硬币的面值之和

\[\leq\frac1l\Big(l-\dfrac12\Big)=1-\frac1{2l}.\]

从而, 这组中的所有硬币的面值与新硬币的面值之和

\[\leq\Big(1-\frac1{2l}\Big)+\frac1a\lt\Big(1-\frac1{2l}\Big)+\frac1{2l}=1.\]

这便完成了引理 3 的证明.

我们来考察不属于任意一个 \(C_k\) 的硬币, \(k=1\), \(2\), \(\dotsc\), \(l\).

这个硬币的面值小于 \(\dfrac1{2l}\). 根据 Lemma 3, 我们确定: 必定至少存在一个 \(C_k\)(\(1\leq k\leq l\)), 使得这枚硬币的面值与 \(C_k\) 中的所有硬币的面值的和仍然最多是 \(1\). 把这枚硬币放进 \(C_k\), 得到的新的集合不妨还是记为 \(C_k\), 其所有硬币的面值之和依旧 \(\leq1\).

我们用同样的办法依次考察没有放进 \(C_1\), \(C_2\), \(\dotsc\), \(C_l\) 中任何一个集合的硬币. 因为所有硬币的面值总额不超过 \(l-\dfrac12\), 故而, 我们每次总可以把一个面值小于 \(\dfrac1{2l}\) 的硬币送进某个 \(C_k\)(\(1\leq k\leq l\)), 并且使得 \(C_1\), \(C_2\), \(\dotsc\), \(C_l\) 每一组中硬币的面值之和始终最多是 \(1\). 既然面值小于 \(\dfrac1{ 2l}\) 的硬币有限, 因之, 我们可以把全部硬币分为至多 \(l\) 组, 使得每一组中硬币的面值之和最多是 \(1\).

Problem 6 (Austria/USA, Gerhard Woeginger/Po-Shen)

今年貌似组合题太多了, 居然有 3 道. 领队的口味应该不会有大的变化呀! 可能没有出现什么好的数论预选题.

这个是本届 IMO 最难的题. 考试的结果, 本题平均分 \(0.339\), 有 \(16\) 个参赛队员做出: \(15\) 个 \(7\) 分, \(1\) 个 \(6\) 分. 至于中国队嘛, 得到了一半多 \(3\) 的分, 其中有 \(3\) 个 \(7\) 分.

这个问题, 真的有那么难吗? 其实不然. 如同第 5 题, 使用归纳法也是可以解决的. 但, 种种偏爱, 我们先单刀赴会的思量, 归纳法有点不那么受人待见. 况且对于本题, 归纳法或许总是可以抛弃的: 归纳的途径来进行染色, 可以改头换面来的更直接!

对于任意的正整数 \(n\), 都可以把其中至少 \(\sqrt n\) 条直线染成蓝色, 使得每一个有限区域的边界都不全是蓝色.

实际上, 到底是哪些直线被染成了蓝色, 是无关紧要的. 只要我们把一些直线染成蓝色, 使得每一个有限区域的边界都不全是蓝色, 并且如果把没有染色的直线中的任意一条染成蓝色, 都会使得至少一个有限区域的边界全是蓝色, 那么, 染成蓝色的直线条数 \(\geq\sqrt n\).

记这 \(n\) 条直线是 \(l_1\), \(l_2\), \(\dotsc\), \(l_n\).

我们将从 \(l_1\) 开始, 依次考察这 \(n\) 条直线, 然后会决定把哪些直线染成蓝色.

假定已经有一些直线染成了蓝色, 对一条未染色的直线进行的如下行为称为对这条直线的一次操作: 如果把这直线染成蓝色, 不会使任意一个有限区域的边界全是蓝色, 就把这直线染成蓝色; 否则这直线不染色.

我们这样来对这 \(n\) 条直线染色: 先把 \(l_1\) 和 \(l_2\) 染成蓝色, 然后依次对 \(l_3\), \(l_4\), \(\dotsc\), \(l_n\) 进行操作.

因为每次对一条直线进行操作, 都不会使任意一个有限区域的边界全是蓝色, 所以全部操作完毕之后, 不可能存在有限区域的边界全是蓝色的.

设一共有 \(k\) 条直线染成了蓝色. 下面的任务是指出: \(k\geq\sqrt n\).

我们的手法是: 赋值. 这个, “高级” 武器, 实际操作, 难度相当大, 很不容易实现. 单墫的”数学竞赛研究教程”最早的版本, 有几个例题是关于这个办法的. 不知怎么, 修订版反倒去掉了.

有 \(n-k\) 条直线是没有染色的. 也就是说, 把这 \(n-k\) 条直线中的任意一条染成蓝色, 都会使得至少一个有限区域的边界全是蓝色. 于是, 对于任意一条没有染色的直线, 有这样一个有限区域, 无妨把这样的区域称为缺一门, 使得这个区域除了一条没有染色的边落在这条直线上, 其余的边界都是蓝色.

对于任意一条没染色的直线, 我们选取一个, 并且只选取一个对应的缺一门. 故而, 选择的缺一门一共是 \(n-k\) 个. 既然每个缺一门恰有一条边没有染色, 因此, 一个缺一门必定是其没有染色的边所在直线对应的缺一门, 并且这 \(n-k\) 个缺一门是互不相同的区域.

蓝色直线的交点称为蓝点. 显而易见, 蓝点有 \(\dbinom k2\) 个.

对任意一个缺一门, 设其边界有 \(v\) 个蓝点. 对这 \(v\) 个蓝点的每一个, 赋值 \(\dfrac1v\). 于是, 这个缺一门的边界上的全部蓝点的赋值之和是 \(1\). 故此, \(n-k\) 个缺一门的边界上的蓝点的赋值的总和是 \(n-k\).

一个蓝点可能落在多个缺一门的边界, 进而, 可能被赋值几次. 我们把一个蓝点的多次赋值全部加起来, 称为这个蓝点的全赋值. 显而易见, 所有进行过赋值的蓝点的全赋值的总和是 \(n-k\).

另一方面, 我们断言: 一个蓝点的全赋值必定不超过 \(2\).

事实上, 考虑一个进行过赋值的蓝点 \(O\). \(O\) 是 \(4\) 个区域(包括面积不是有限的区域)的公共顶点, 因此, \(O\) 落在至多 \(4\) 个缺一门的边界. 如果对于这不超过 \(4\) 个缺一门的任何一个而言, 其边界都有至少 \(2\) 个蓝点(包括 \(O\)), 那么, \(O\) 点的全赋值, 也就是多次赋值全部相加

\[\leq\frac12+\frac12+\frac12+\frac12=2.\]

每个缺一门恰好有一边所在直线没有染色, 因此恰好有 \(2\) 个顶点不是蓝点. 我们判定, 若存在缺一门以 \(O\) 为惟一蓝色顶点, 这个缺一门必是三角形区域. 这个三角形区域的一条没染色的边记为 \(l\).

IMO 2014 Problem 6 Proof 1

IMO 2014 Problem 6 Proof 1

考察以 \(O\) 为一顶点的 \(2\) 个区域 \(\rm I\) 和 \(\rm II\), 其各与这个三角形区域恰有一条公共边.

注意, 区域 \(\rm I\) 的边 \(AC\), 区域 \(\rm II\) 的边 \(BD\) 都落在 \(l\) 上, 于是都没有染色. \(l\) 已有一个对应的缺一门, 即三角形区域 \(OAB\), 所以 \(\rm I\) 与 \(\rm II\) 断然不是 \(l\) 对应的, 进而都绝然不能是, 缺一门. 从而, \(O\) 点的全赋值

\[\leq1+1=2.\]

总而言之, \(O\) 点的全赋值 \(\leq2\).

现在, 既然蓝点有 \(\dbinom k2\) 个, 因之, 所有进行过赋值的蓝点的全赋值的总和

\[\leq2\dbinom k2=k(k-1).\]

所有赋值过的蓝点的全赋值的总和为 \(n-k\). 我们断言

\begin{equation}\color{red}{k(k-1)\geq n-k}.\end{equation}

梦中情人 \(k\geq\sqrt n\) 踏着七色云彩骑着白龙马从天而降在眼前.

Annotations

  1. 本届 IMO 没有出彩的题, 难度很低. 组合题太多, 尽管这里给出的题 6 的第一个解法算是漂亮, 但大同小异林林总总的”平庸”办法的存在使得这题的价值大为降低; 作为压轴的第 3 题几何, 也很稀松平常; 惟一的代数, 第 1 题, 只是热身; 没有数论是为憾事.
  2. 如此低的金牌线 29, 颇让人吃惊. 这样简单的试题, 金牌线 \(\geq35\) 才算正常.
  3. 题 5 和 6 其实是不错的素材, 相关问题的研究方兴未艾, 很是让人激情澎湃.
  4. 题 5 的证明采用了较 “复杂, 啰嗦” 的途径, 是为了逻辑上更清晰: 使用更多的数学公式来进行处理, 而不是更多的文字到达某种“必定存在”的特殊情况.
  5. 第 6 题解的 “缺一门” 一词来自王岳伦 2008 年的电影 “十全九美”. 事实上, 这词传奇于江湖久已—传说中的奇书 “鲁班书” 的小名叫”缺一门”; 麻将有一种牌称为缺一门.
 Posted by at 11:43 am  Tagged with:
Jul 082014
 

                                      Day \(1\)

  2014 年 7 月 8 日, 星期二

第 1 题. 设  \( a_0\lt a_1\lt a_2\lt\dotsb \) 是一个无穷正整数列. 证明: 存在惟一的整数 \(n\geq1\) 使得

\[ a_n \lt\frac{a_0+a_1+a_2+\dotsb+a_n}n\leq a_{n+1}. \]

第 2 题. 设 \(n\geq2\) 是一个整数. 考虑由 \(n^2\) 个单位正方形组成的一个 \(n\times n\) 棋盘. 一种放置 \(n\) 个棋子”车” 的方案被称为是和平的, 如果每一行和每一列上都恰好有一个”车”. 求最大的正整数 \(k\), 使得对于任何一种和平放置 \(n\) 个 “车” 的方案, 都存在一个 \(k\times k\) 的正方形, 它的 \(k^2\) 个单位正方形里都没有”车”.

第 3 题. 在凸四边形 \(ABCD\) 中 \(\angle ABC=\angle CDA=90^\circ\). 点 \(H\) 是 \(A\) 向 \(BD\) 引的垂线的垂足. 点 \(S\) 和点 \(T\) 分别在边 \(AB\) 和边 \(AD\) 上, 使得 \(H\) 在三角形 \(SCT\) 内部, 且

\[ \angle CHS-\angle CSB = 90^\circ,\quad\angle THC-\angle DTC = 90^\circ. \]

证明: 直线 \(BD\) 和三角形 \(TSH\) 的外接圆相切.

                                      Day \(2\)

  2014 年 7 月 9 日, 星期三

第 4 题. 点 \(P\) 和 \(Q\) 在锐角三角形 \(ABC \) 的边 \(BC \) 上, 满足 \(\angle PAB =\angle BCA\) 且 \(\angle CAQ = \angle ABC\). 点 \(M\) 和 \(N\) 分别在直线 \(AP\) 和 \(AQ\) 上, 使得 \(P\) 是 \(AM\) 的中点, 且 \(Q\) 是 \(AN\) 的中点. 证明: 直线 \(BM\) 和 \(CN\) 的交点在三角形 \(ABC\) 的外接圆上.

第 5 题.  对每一个正整数 \(n\), 开普敦银行都发行面值为 \(\dfrac1n\) 的硬币. 给定总额不超过 \(99+\dfrac12\) 的有限多个这样的硬币(面值不必两两不同) , 证明可以把它们分为至多 \(100\) 组, 使得每一组中硬币的面值之和最多是 \(1\).

第 6 题.  平面上的一族直线被称为是处于一般位置的, 如果其中没有两条直线平行, 没有三条直线共点. 一族处于一般位置的直线把平面分割成若干区域, 我们把其中面积有限的区域称为这族直线的有限区域. 证明: 对于充分大的 \(n\) 和任意处于一般位置的 \(n\) 条直线, 我们都可以把其中至少\(\sqrt n\) 条直线染成蓝色, 使得每一个有限区域的边界都不全是蓝色的.

: 如果你的答卷上证明的是 \(c\sqrt n\)(而不是 \(\sqrt n\)) 的情形, 那么将会根据常数 \(c\) 的值给分.

                                    Day \(1\)

 Tuesday, July 8, 2014

Problem 1.  Let \( a_0\lt a_1\lt a_2\lt\dotsb \)  be an infinite sequence of positive integers. Prove that there exists a unique integer \(n\geq1\) such that

\[ a_n \lt\frac{a_0+a_1+a_2+\dotsb+a_n}n\leq a_{n+1}. \]

Problem 2. Let \(n\geq2\) be an integer. Consider an \(n\times n\) chessboard consisting of  \(n^2\) unit squares. A configuration of \(n\) rooks on this board is  peaceful  if every row and every column contains exactly one rook. Find the greatest positive integer \(k\) such that, for each peaceful configuration of \(n\) rooks, there is a \(k\times k\) square which does not contain a rook on any of its  \(k^2\) unit squares.

Problem 3.  Convex quadrilateral \(ABCD\) has \(\angle ABC=\angle CDA=90^\circ\). Point \(H\) is the foot of the perpendicular from \(A\)  to \(BD\). Points \(S\) and \(T\)  lie on sides \(AB\) and \(AD\) respectively, such that \(H\) lies inside triangle \(SCT\) and

\[ \angle CHS-\angle CSB = 90^\circ,\quad\angle THC-\angle DTC = 90^\circ. \]

Prove that line \(BD\) is tangent to the circumcircle of triangle \(TSH\).

                                    Day \(2\)

Wednesday, July 9, 2014

Problem 4. Points \(P\) and \(Q\) lie on side \(BC\) of acute-angled triangle \(ABC\) so that \(\angle PAB=\angle BCA\) and \(\angle CAQ=\angle ABC\). Points \(M\) and \(N\) lie on lines \(AP\) and \(AQ\), respectively, such that \(P\) is the midpoint of \(AM\) and \(Q\) is the midpoint of \(AN\). Prove that lines \(BM\) and \(CN\) intersect on the circumcircle of triangle \(ABC\).

Problem 5. For each positive integer \(n\), the Bank of Cape Town issues coins of denomination \(\frac1n\). Given a finite collection of such coins (of not neccesarily different denominations) with total value at most \(99+\frac12\). Prove that it is possible to split this collection into \(100\) or fewer groups, such that each group has total value at most \(1\).

Problem 6.A set of lines in the plane is in general position if no two are parallel and no three pass through the same point. A set of lines in general position cuts the plane into regions, some of which have finite area; we call these its finite regions. Prove that for all sufficiently large \(n\), in any set of \(n\) lines in general position it is possible to colour at least \(\sqrt n\) of the lines blue in such a way that none of its finite regions has a completely blue boundary.

Note: Results with \(\sqrt n\) replaced by \(c\sqrt n\) will be awarded points depending on the value of the constant \(c\).

 Posted by at 11:49 am  Tagged with: