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