Mar 172017
 

试题来自贴吧

2017 China IMO team selection

2017 China IMO team selection test 2 day 1

2017 China IMO team selection

2017 China IMO team selection test 2 day 2

这里转一下贴吧网友 1a2b03c 给出的题 6 有关的一个关键, 这网友水平挺高的

\(\alpha\), \(\beta\) 都是无理数,

2017 China IMO team selection test

2017 China IMO team selection test

2017 China IMO team selection test


邓煜的看法:

最后那里可以不用极限来说. 只要证明对任何 \(c\gt0\), 存在 \(n\) 使得\(\{n\beta\}\) 属于 \((b_3, b_4)\) 且 \(\{n\alpha\}\lt c\) 即可. 假设不然, 由引理 3, 取 \(n^\prime\) 和 \(n^{\prime\prime}\) 使得 \(\{n^\prime\beta\}\lt \dfrac{b_4-b_3}2\), \(\{n^\prime\alpha\}=1-p(p<c) \) 和 \(\{n^{\prime\prime}\beta\}>1-\dfrac{b_4-b_3}2\), \(\{n^{\prime\prime}\alpha\}=1-q(q<c)\).

今对任何 \(n\),若\(\{n\beta\}\) 属于 \((b_3, b_4)\),则取决于是否 \(\{n\beta\}<\dfrac{b_3+b_4}2\), 令 \(n_1=n+n^\prime\)或 \(n+n^{\prime\prime}\), 则由于\(\{n\alpha\}\gt c\gt \max(p,q)\),故 \(\{n_1\alpha\}\lt\{n\alpha\}-\max(p,q)\); 因 \(\{n_1\alpha\}\gt c\), 故 \(\{n\alpha\}\gt c+\max(p,q)\). 如此迭代下去即得矛盾.

最后应该是 \(\{n_1\alpha\}\leqslant \{n\alpha\}-\min(p,q)\); 因 \(\{n_1\alpha\}\gt c\), 故 \(\{n\alpha\}\gt c+\min(p, q)\).

 Posted by at 12:23 am
Nov 262016
 

第 32 届中国数学奥林匹克

湖南 长沙

第一天

(2016 年 11 月 24 日    8:00–12:30)

1. 数列 \(\{u_n\}\), \(\{v_n\}\) 满足: \(u_0=u_1=1\), \(u_n=2u_{n-1}-3u_{n-2}(n\geqslant2)\), \(v_0=a\), \(v_1=b\), \(v_2=c\), \(v_n=u_{n-1}-3u_{n-2}+27v_{n-3}(n\geqslant3)\). 已知存在正整数 \(N\), 使得当 \(n\geqslant N\) 时, \(u_n\mid v_n\). 求证: \(3a=2b+c\).

2. 锐角 \(\triangle ABC\) 中, 外心为 \(O\), 内心为 \(I\). 过点 \(B\), \(C\) 作外接圆的切线交于点 \(L\), 内切圆切 \(BC\) 于点 \(D\), \(AY\) 垂直 \(BC\) 于点 \(Y\), \(AO\) 交 \(BC\) 于点 \(X\), \(PQ\) 为过点 \(I\) 的圆 \(O\) 的直径. 求证: \(P\), \(Q\), \(X\), \(Y\) 共圆等价于 \(A\), \(D\), \(L\) 共线.

3. 将矩形 \(R\) 分为 \(2016\) 个小矩形, 每个小矩形的顶点称为结点, 每个小矩形的边和 \(R\) 平行. 若一条线段的两端为结点, 且线段上没有其他结点, 称之为基本线段. 求遍历所有划分方式时, 基本线段数量的最小值个最大值.

第二天

(2016 年 11 月 25 日    8:00–12:30)
CMO 2017

cmo 2017 day 2

 Posted by at 5:14 pm  Tagged with:
Aug 112016
 

集合

\[\{\sqrt n|n\in\Bbb N\; \text{is Square-free integer}\}\]

在有理数域上线性无关.

这其实是非常古老的问题, 早已经有很一般的结果.

先厘清无平方因子整数Square-free integer这个概念: \(1\) 到底是不是无平方因子整数?

wiki 给出的定义是: 不被不是 \(1\) 的完全平方整除的整数称为无平方因子整数. 因此, \(1\) 算无平方因子正整数. 鉴于此, 我们认为: 无平方因子整数定义为”不被质数的平方整除的整数”更为恰当.

下面的证明来自 Iurie Boreico 的文章 Linear Independence of Radicals.

我们把问题写的更清楚一点, 即我们要证明:

\(n_1\), \(n_2\), \(\dotsc\), \(n_k\) 是互不相同的无平方因子正整数; \(a_1\), \(a_2\), \(\dotsc\), \(a_k\) 都是整数. 令

\[S=a_1\sqrt{n_1}+a_2\sqrt{n_2}+\dotsb+a_k\sqrt{n_k},\]

那么 \(S=0\) 当且仅当 \(a_1=a_2=\dotsb=a_k=0\).

第一个办法是指出更精细的结果:

记 \(p_1\), \(p_2\), \(\dotsc\), \(p_N\) 是 \(n_1n_2\dotsm n_k\) 的所有互不相同的质因子. 则存在

\[S^\prime=b_1\sqrt{m_1}+b_2\sqrt{m_2}+\dotsb+b_l\sqrt{m_l},\]

(这里 \(b_1\), \(b_2\), \(\dotsc\), \(b_l\) 都是整数; \(m_1\), \(m_2\), \(\dotsc\), \(m_l\) 都是无平方因子正整数, 并且都没有 \(p_1\), \(p_2\), \(\dotsc\), \(p_N\) 以外的质因子), 使得 \(SS^\prime\ne0\) 是整数. 进而, 顺水推舟, \(S\ne0\).

对 \(N\) 进行归纳.

明显 \(N=0\) 时, 结论为真: 此刻 \(k=1\), \(n_1=1\), 于是 \(S=a_1\ne0\). 令 \(S^\prime=1\) 即可.

 Posted by at 5:04 pm
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: