这个续集只聊第 \(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 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\) 整除的整数.

解答四

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

                                      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.