IMO 2013 解答

Problem 1 (Japan)

证明 1

注意到

\begin{equation}\left(1+\frac1{2a}\right)\left(1+\frac1{2a+1}\right)=1+\frac1a,\end{equation}

于是, 我们可以对形如

\begin{equation}\left(1+\dfrac1b\right)\left(1+\dfrac1{b+1}\right)\dotsm\left(1+\dfrac1{b+2^t-2}\right)\end{equation}

的乘积进行操作: 首先把因式按照如下规则配对: 若 \(b\) 是奇数, \(1+\dfrac1b\) 不动, 把 \(1+\dfrac1{b+1}\) 与 \(1+\dfrac1{b+2}\) 配对, \(\dotsc\), \(1+\dfrac1{b+2^t-3}\) 与 \(1+\dfrac1{b+2^t-2}\) 配对; 若 \(b\) 是偶数, 把 \(1+\dfrac1b\) 与 \(1+\dfrac1{b+1}\) 配对, \(\dotsc\),   \(1+\dfrac1{b+2^t-4}\) 与 \(1+\dfrac1{b+2^t-3}\) 配对, \(1+\dfrac1{b+2^t-2}\) 不动. 然后, 把每一对配对的因式按照 \((1)\) 进行计算. 注意, 这样得到的式子依旧形如 \((2)\), 只不过多出一个不动的因式, 一共 \(1+(2^{t-1}-1)\) 个因式. 这完成了一次操作.

下面的式子是显然的:

\[1+\frac{2^k-1}n=\left(1+\frac1n\right)\left(1+\frac1{n+1}\right)\dotsm\left(1+\frac1{n+2^k-2}\right).\]

对这个式子进行一次操作, 得到的式子有 \(1+(2^{k-1}-1)\) 个因式. 然后, 保持第一次不动的因式依旧不动, 对第一次操作得到的形如 \((2)\) 式的式子进行第二次操作, 结果是 \(1+(1+(2^{k-2}-1))=2+(2^{k-2}-1)\) 个因式的乘积. 接下来, 进行下次操作, \(\dotsc\), 如此这般重复. 每次操作, 此前不动的因式依旧不动. 第 \(i\) 次操作得到的式子, 有 \(i+(2^{k-i}-1)\) 个因式. 于是, 进行 \(k-1\) 次操作可得一个只有 \(k\) 个因式的乘积, 这正是我们梦寐以求.

证明 2  

本题最容易想到的做法, 是数学归纳法: 对 \(k\) 进行归纳.  Induction on \(k\).

奠基显然.

若 \(n\) 为偶数,  \(k\gt1\), 注意

\[ 1+\frac{2^k-1}n=\left( 1+\frac{2^{k-1}-1}{\frac n2}\right)\left( 1+\frac1{n+2^k-2}\right). \]

如果 \(n\) 是奇数,  \(k\gt1\), 注意

\[ 1+\frac{2^k-1}n=\left( 1+\frac{2^{k-1}-1}{\frac{n+1}2}\right)\left( 1+\frac1n\right). \]

无论如何, 结果都是显然的.

证明 3

这题目最直接的做法, 是直接构造满足要求的 \(m_1,m_2,\dotsc,m_k\). 采用二进制.

设整数 \(r\) 适合 \(2^{k-1}\mid(n+r), 0\leqslant r\leqslant2^{k-1}-1\). 记 \(s=2^{k-1}-1-r\). 设 \(r,s\) 的二进制表示分别为:

\[ r=2^{a_1}+2^{a_2}+\dotsc+2^{a_u},  s=2^{b_1}+2^{b_2}+\dotsc+2^{b_v}, \]

这里 \(0\leqslant a_1\lt a_2 \lt\dotsc\lt a_u, 0\leqslant b_1 \lt b_2 \lt\dotsc\lt b_v\). 若 \(r,s\) 有一个是 \(0\), 相应地, 令 \(u=0\) 或 \(v=0\).

我们指出 \(u+v=k-1\). 这是因为, \(r,s\) 的二进制表示, 不会发生某一位上的数字相等的事情. 如果不是这样, 从低位往高位看, \(r+s\) 在 \(r,s\) 第一次发生数字相同的那一位的数字, 必定是 \(0\). 由此可见, \(a_1,a_2,\dotsc,a_u,b_1,b_2,\dotsc,b_v\) 恰是 \(0,1,2,\dotsc,k-2\) 的一个排列.

记

\[t_1=2^{a_1},t_2=2^{a_1}+2^{a_2},\dotsc, t_{u-1}=2^{a_1}+2^{a_2}+\dotsc+2^{a_{u-1}},t_u=r,\]

\[t_{u+1}=r+2^{k-1},t_{u+2}=r+2^{k-1}+2^{b_v}, t_{u+3}= r+2^{k-1}+2^{b_v}+2^{b_{v-1}},\dotsc, t_k = 2^k-1.\]

考察

\[ 1+\frac{2^k-1}n=\frac{n+t_1}n\cdot\frac{n+t_2}{n+t_1}\dotsm\frac{n+t_k}{n+t_{k-1}}.\]

现在需要证明: 上式右边的每个因式可以写成 \(1+\frac1{m_i}\). 注意 \( \dfrac{n+t_{i+1}}{n+t_i}= 1+\dfrac{t_{i+1}-t_i}{n+t_i}\), 因之, 我们的目的是指出 \((t_{i+1}-t_i)\mid (n+t_i)\).

当 \(i=u\) 时, \(t_{u+1}-t_u=2^{k-1}, n+t_u=n+r\), 因此, \((t_{u+1}-t_u)\mid (n+t_u)\).

\(i=u-1\) 时, \(t_u-t_{u-1}=2^{a_u}\). 因 \(a_u<k-1\), 由 \((t_{u}-t_{u-1})\mid (n+t_u), n+t_u-(t_u-t_{u-1})=n+t_{u-1}\) 可得 \((t_{u}-t_{u-1})\mid (n+t_{u-1})\).

如此继续, 可完成 \(i\lt u\) 的验证. \(i\gt u\) 的情况, 证明类似.

Problem 2 (Ivan Guo, Australia )

答案是 \(2013\).

首先指出至少需要 \(2013\) 条直线. 考虑正 \(4027\) 边形 \(A_1A_2 \dotsm A_{4027}\): \(A_1,A_3,\dotsc,A_{4027}\) 是蓝色, 别的顶点是红色. 这正多边形的 \(4026\) 条两端颜色不同的边, 是都必须要有直线穿过的. 每条直线最多只能穿过两条边, 因此, 至少 \(\dfrac{4026}2=2013\) 条直线才可能达到目的.

再来, 我们证明总有 \(2013\) 条直线可以完成任务.

引理 1 在平面上的一个由任意三点不共线的有限个点组成的点集中, 任取两点 \(A,B\), 直线 \(AB\) 把平面分成两个半平面 \(\alpha_1,\alpha_2\). 那么, 有直线 \(l_i\subset\alpha_i\), \(l_i\parallel AB\), 并且 \(l_i\) 与 \(AB\) 所夹的区域没有这点集中的任何点(\(i=1,2\)).

设这点集除 \(A,B\) 之外的点是 \(C_1,C_2,\dotsc,C_n\). 记 \(C_i\) 到直线 \(AB\) 的距离是 \(h_i,i=1,2,\dotsc,n\). 只要在 \(\alpha_i\) 内, 作平行于 \(AB\) 的直线 \(l_i\), 使得 \(l_i\) 到 \(AB\) 的距离 \(\lt\min\{h_1,h_2,\dotsc,h_n\}\) 即可(\(i=1,2\)).

引理 2 设 \(AB_1B_2\dotsm B_n\) 是平面上的一个由任意三点不共线的有限个点组成的点集的凸包, 那么, 必有直线 \(l\) 把平面分成两个半平面, 使得其中一个半平面的内部, 仅仅只有这点集的 \(A\) 这一个点.

记 \(B_n\) 关于 \(A\) 的对称点是 \(C\). 在 \(\angle CAB_1\) 的内部随便取一点, 记为 \(B\). 于是, 直线 \(AB\) 把平面分成两个半平面, 凸多边形 \(AB_1B_2\dotsm B_n\) 落在这两个半平面之中的某一个内. 据引理 1, 有落在这半平面内部的直线 \(l\), \(l\parallel AB\), \(l\) 与 \(AB\) 之间没有这点集的其它点. \(l\) 把平面分成的两个半平面, 包含 \(A\) 的那个, 就仅仅只有这点集的 \(A\) 这一个点.

解答 1 

这 \(4027\) 个点的凸包是多边形 \(A_1A_2\dotsm A_k\).如果 \(A_1,A_2,\dotsc,A_k\) 中至少有一个红点, 随便取一个, 不妨 \(A_1\). 于是, 必有直线 \(l\) 把平面分成两个半平面, 并且其中一个半平面仅仅只有 \(A_1\) 这一个点. 记 \(B_1,B_2,\dotsc,B_{2012}\) 是除 \(A_1\) 之外的另 \(2012\) 个红点. 考察直线 \(B_{2i-1}B_{2i}(i=1,2,\dotsc,1006)\), 使用两条平行于 \(B_{2i-1}B_{2i}\) 的直线 \(l_i,l_i^\prime\), 使得  \(l_i,l_i^\prime\) 所夹的区域只有 \(B_{2i-1}, B_{2i}\) 这两个点. 于是 \(l,l_1,l_1^\prime,\dotsc,l_{1006},l_{1006}^\prime\) 这 \(2013\) 直线满足要求.

如果 \(A_1,A_2,\dotsc,A_k\) 全部是蓝点, 必有平行于 \(A_1A_2\) 的直线 \(s\) 把平面分成两个半平面, 并且其中一个半平面仅仅只有 \(A_1,A_2\) 这两点. 记 \(C_1,C_2,\dotsc,C_{2012}\) 是除 \(A_1,A_2\) 之外的另 \(2012\) 个蓝点. 同样的道理, 有平行于 \(C_{2i-1}C_{2i}\) 的直线 \(s_i,s_i^\prime\), 使得 \(s_i,s_i^\prime\) 之间只有 \(C_{2i-1}, C_{2i}\) 这两点, \(i=1,2,\dotsc,1006\). 于是 \(s,s_1,s_1^\prime,\dotsc,s_{1006},s_{1006}^\prime\) 这 \(2013\) 直线达成目标.

解答 2

我们来证明一个更一般的结果: 对于 \(u\) 个红点, \(v\) 个蓝点, 则可用 \(\left[\dfrac{u+v}2\right]\) 条直线把平面分成一些区域, 使得任何一个区域都只有相同颜色的点. (这里 \([x]\) 表示不超过 \(x\) 的最大整数.)

对 \(u+v\) 进行归纳. 奠基显然.

考察 \(u+v\) 个点. 这些点组成集合 \(S\). 记 \(m=\left[\dfrac{u+v-2}2\right]\).

任取 \(S\) 的凸包, 这是一个凸多边形, 的两个相邻顶点 \(A,B\).

如果 \(A, B\) 的颜色不同, 则我们可找到 \(m\) 条不通过 \(A,B\)(必要的时候, 可把直线稍稍移动) 的直线把平面分成一些区域, 使得任何一个区域只有 \(S\setminus\{A,B\}\) 中相同颜色的点. 如果 \(A, B\) 两点落在不同的区域, 再使用一条直线把 \(A, B\) 与其余的点分开. 如果 \(A, B\) 落在相同的一个区域, 记为 \(R\), 则 \(R\) 必定含有某颜色的点只有 \(1\) 个, 并且这个点是 \(A, B\) 之一, 不妨是 \(A\). 再用一条直线把 \(A\) 与其余的点分开. 于是一共 \(m+1=\left[\dfrac{u+v}2\right]\) 条直线得到目的.

如果 \(A, B\) 的颜色相同, 可以先使用一直线把 \(A,B\) 与其余的点分开. 然后, 可找到 \(m\) 条不通过 \(A,B\)(否则, 直线可微小移动)的直线把平面分成一些区域, 使得任何一个区域只有 \(S\setminus\{A,B\}\) 中相同颜色的点. 于是一共 \(1+m=\left[\dfrac{u+v}2\right]\) 条直线实现目的.

综上, 无论如何, 我们总能找到 \(\left[\dfrac{u+v}2\right]\) 条直线符合要求.

Problem 3 (Alexander A. Polyansky, Russia)

证明 1    

三角形 \(A_1B_1C_1\) 是钝角三角形, 因为 \(\triangle A_1B_1C_1\) 的外心在 \(\triangle A_1B_1C_1\) 外. 不妨 \(\angle B_1A_1C_1\gt 90^\circ\), 于是 \(\triangle A_1B_1C_1\) 的外心, \(A_1\) 在 \(B_1C_1\) 异侧.

记 \(\widehat{BAC}\) 的中点为 \(O\), 于是 \(BO=CO\). 注意到 \(\angle OBC_1=\angle OCB_1, BC_1=CB_1\), 因此 \(\triangle OBC_1\cong\triangle OCB_1\), 于是 \(OC_1=OB_1\), \(O\) 在 \(B_1C_1\) 的中垂线上. 结合 \(O\) 在 \(\triangle ABC\) 的外接圆上, 因之 \(O\) 就是 \(\triangle A_1B_1C_1\) 的外心, 于是 \(OA_1=OB_1=OC_1\).

在线段 \(BO\) 内取点 \(D\), 在 \(OC\) 的延长线上取点 \(E\), 使得 \(BD=CE=AO\). 既然

\[\angle DBA_1=\angle OAB_1, BA_1=AB_1,\]

故而 \(\triangle DBA_1\cong\triangle OAB_1\). 同样,

\[\angle OAC_1=\angle ECA_1, AC_1=CA_1\]

给出 \(\triangle OAC_1\cong\triangle ECA_1\). 于是, \(DA_1=OB_1=OC_1=EA_1\).

由

\[\angle DA_1B=\angle OB_1A=180^\circ-\angle OB_1C=180^\circ-\angle OC_1B=\angle OC_1A=\angle EA_1C\]

可得 \(D,A_1,E\) 共线. 结合\(A_1O=A_1D=A_1E\) 推出 \(\angle DOE=90^\circ\). 因为 \(\angle BAC=\angle DOE\), 因此 \(\triangle ABC\) 是直角三角形.

证明 2

记 \(\triangle ABC\) 的顶点 \(A,B,C\) 所对的旁心分别是 \(I_1,I_2,I_3\), 则 \(\triangle ABC\) 是 \(\triangle I_1I_2I_3\) 的垂足三角形. 设 \(U, V, W\) 分别是 \(I_2I_3, I_3I_1, I_1I_2\) 的中点, 结合 \(\triangle I_2I_3B, \triangle I_3I_2C\) 都是直角三角形, 这便导出 \(UB=UC=UI_3=UI_2\). 于是

\[\angle I_3UB=180^\circ-2\angle I_3=180^\circ-2\cdot\frac{\angle BAC+\angle ABC}2=\angle ACB\]

给出 \(U\) 在 \(\triangle ABC\) 的外接圆上, 并且在 \(BC\) 的中垂线上. \(\angle UBC_1=\angle UCB_1, BC_1=CB_1\) 得出 \(\triangle UBC_1\cong\triangle UCB_1\), \(U\) 亦在 \(C_1B_1\) 中垂线上.

类似的, \(V,W\) 分别在 \(C_1A_1, A_1B_1\) 中垂线上, 也都在 \(\triangle ABC\) 的外接圆上. 其实, 这就是九点圆定理, 我们没有直接使用.

\(\triangle A_1B_1C_1\) 的外心在 \(\triangle A_1B_1C_1\) 外, 因之三角形 \(A_1B_1C_1\) 是钝角三角形. 不妨 \(\angle B_1A_1C_1\gt90^\circ\), 于是  \(\triangle A_1B_1C_1\) 的外心, \(A\) 在 \(B_1C_1\) 同侧, 从而 \(U\) 就是 \(\triangle A_1B_1C_1\) 的外心, \(UV, UW\) 分别是 \(A_1C_1, A_1B_1\) 的中垂线. 注意到四边形 \(UVI_1W\) 是平行四边形, 由

\[\angle BAC=\angle  BUC=2\angle VUW=2\angle VI_1W=2\cdot\frac{\angle ABC+\angle ACB}2\]

给出 \(\angle BAC=90^\circ\).

证明 3    

把证明 2 的最后做一点改动.

\(UV\) 是 \(A_1C_1\) 的中垂线, 当然 \(A_1C_1\perp UV\), 于是 \(A_1C_1\perp I_1I_2\). 记 \(I_3C\) 与 \(AB\) 的交点是 \(M\), 则 \(CM\perp I_1I_2\). 于是, \(A_1C_1\parallel CM\), 当然更有

\[\frac{BC_1}{BA_1}=\frac{BM}{BC}.\]

这也就是

\[\frac{\frac{b+c-a}2}{\frac{a+b-c}2}=\frac{\frac{ac}{a+b}}a,\]

此即 \(b^2+c^2=a^2\), 因而 \(\angle BAC=90^\circ\).

Problem 4 (Warut Suksompong and Potcharapol Suteparuk, Thailand )

证明 1   

\(B,C,M\) 和 \(N\) 四点共圆, 这圆记为 \(\omega\). \(\omega\) 与 \(\omega_1\) 的公共弦 \(BN\) 与 \(\omega\) 与 \(\omega_2\) 的公共弦 \(CM\) 的交点是 \(A\), 于是 \(A\) 即为 \(\omega_1, \omega_2\) 和 \(\omega\) 的根心. \(\omega_1, \omega_2\) 的另一个交点 \(U\) 显然在 \(AW\) 上.

因 \(WX\) 和 \(WY\) 分别是 \(\omega_1\) 和 \(\omega_2\) 的直径, 故此 \(WU\perp XU, WU\perp YU\), 进而 \(X,Y\) 和 \(U\) 共线.

\(HM,HN\) 分别与 \(AM,AN\) 垂直, 因此, \(AH\) 是 \(\triangle AMN\) 的外接圆的直径. 此外, 据 Miquel’s theorem, \(U\) 也在 \(\triangle AMN\) 的外接圆上, 故而 \(HU\perp AU\). 于是, \(H\) 亦在直线 \(XY\) 上. 换句话说, \(X,Y,U\) 和 \(H\) 共线.

证明 2    

尝试换个途径实现证明 1 的后半部分.

记 \(AB\) 交 \(XY\) 于点 \(D\), \(AW\) 与 \(CN\) 的交点是 \(E\). \(\angle DUE=\angle DNE=90^\circ\) 导出 \(D,E,U,N\) 四点共圆. 结合 \(B,W,U,N\) 亦是四点共圆, 给出 \(DE\parallel BW\), 进而 \(AH\perp DE\). 又因为 \(EN\perp AD\), 故而 \(H\) 亦是 \(\triangle ADE\) 的垂心, \(DH\perp AE\).

Problem 5 (Nikolai Nikolov, Bulgaria)

证明 1   

首先指出 \(f \) 的 \(5\) 条性质:

1. (i) 中令 \(x=a,y=1\), 得 \(f(a)f(1)\geqslant f(a)\). 再利用 (iii), 有 \(f(1)\geqslant1\);
2. 由 (ii), \(f(nr)\geqslant nf(r), \forall r\in\Bbb Q_{\gt0}, \forall n\in\Bbb N\). 特别, 令 \(r=1\), 得 \(f(n)\geqslant n\);
3. 根据 (i), 注意到 (iii), 可有 \(a^k\geqslant f(a^k),\forall k\in\Bbb N\);
4. \(\forall \frac pq\in\Bbb Q_{\gt0}\), 这里 \(p,q\in\Bbb N\), 因 \(f(\frac pq)f(q)\geqslant f(p)\geqslant p\), 故 \( f(\frac pq)\geqslant \frac p{f(q)}\), 当然更有 \(f(\frac pq)\gt0\);
5. \(\forall x,y\in\Bbb Q_{\gt0}, x\gt y\), 则 \(r=x-y\in\Bbb Q_{\gt0}\). 于是 \(f(x)=f(y+r)\geqslant f(y)+f(r)\gt f(y)\).

任意正整数 \(k\), \(f\left(a^k\right)f\left(\dfrac1{a^k}\right)\geqslant f\left(a^k\cdot\dfrac1{a^k}\right)= f\left(1\right)\geqslant1\) 给出 \(f\left(\dfrac1{a^k}\right)\geqslant\dfrac1{a^k}\).

有理数 \(r\gt0\). 对任意正整数 \(k\), 有

\[f\left(r\right)\geqslant f\left(\frac{\left[a^kr\right]}{a^k}\right)\geqslant\left[a^kr\right] f\left(\frac1{a^k}\right)\geqslant\frac{\left[a^kr\right]}{a^k}\gt\frac{a^kr-1}{a^k}=r-\frac1{a^k}.\]

故 \(f\left(r\right)\geqslant r\).

对任意有理数 \(r\gt0\), 有正整数 \(k\), 使得 \(a^k\gt r\). 于是, 由

\[a^k\geqslant f\left(a^k\right)\geqslant f\left(a^k-r\right)+f\left(r\right)\geqslant a^k-r+f\left(r\right)\]

给出 \(f\left(r\right)\leqslant r\).

证明 2

前一个证明的 \(5\) 条性质依旧是有力的武器. 不过, 需要把性质 3 改进一点:

对于所有的 \(r\in\Bbb Q_{\gt0}, k\in\Bbb N\), 都有 \(f(r)^k\geqslant f(r^k)\).

性质 6   如果有理数 \(r\gt1\), 那么, 对任意正整数 \(k\),

\[f\left(r\right)^k\geqslant f\left(r^k\right)\geqslant f\left(\left[r^k\right]\right)\geqslant \left[r^k\right]\gt r^k-1.\]

于是 \(f\left(r\right)\geqslant r\).

性质 7   如果 \(r\in\Bbb Q_{\gt0}\), 适合 \(f(r)=r\), 由

\[f(r)f(\frac1r)\geqslant f\left(r\cdot\dfrac1r\right)= f\left(1\right)\geqslant1\]

可得 \(f\left(\dfrac1r\right)\geqslant\dfrac1r\).

性质 8   \(x,y\in\Bbb Q_{\gt0},x+y\geqslant f(x+y)\), 且 \(f(x)\geqslant x,f(y)\geqslant y\), 则 \(f(x)=x,f(y)=y\).

性质 9   若有理数 \(r\gt0\), 满足 \(f(r)\geqslant r\), 则 \(f(r)=r\).

事实上, 此时必有正整数 \(k\), 使得 \(a^k-r\gt1\). 性质 6 给出 \(f(a^k-r)\geqslant a^k-r\). 然后, 性质 3 与性质 8 定出 \(f(r)=r\).

性质 10  对于所有 \(r\in\Bbb Q_{\gt0}\), 我们有 \(f(r)=r\).

性质 1, 6 和 9 已经说明, 对于所有有理数 \(r\geqslant1\) 而言, 性质 10 为真. 再根据性质 7 与 9, 可知性质 10 对于任意有理数 \(0\lt r\lt1\), 也是成立的.

证明 3

证明 1 的 5 条性质照旧.

下面证明

\[f(n)=n, \forall n\in\Bbb N.\]

事实上, 如果存在正整数 \(m,q\), 使得 \(f(m)\gt m+\frac1q\), 那么, 由性质 2, 有

\[f(nqm)\geqslant nqf(m)\gt nq(m+\frac1q)=nqm+n,\forall n\in\Bbb N.\]

取定一个正整数 \(n\), 满足 \(n\gt qm\), 并且存在正整数 \(k\), 适合 \(nqm\leqslant a^k\lt (n+1)qm\). 依性质 5, 可得

\[f(nqm)\leqslant f(a^k).\]

再根据我们对 \(n\) 的选择, 以及性质 3, 有

\[nqm+qm\lt nqm+n\lt f(nqm)\leqslant f(a^k)\leqslant a^k\lt (n+1)qm,\]

这是不可能的. 因之, \(\forall n\in\Bbb N,f(n)=n\).

\(\forall r=\frac pq\in\Bbb Q_{\gt0}\), 这里 \(p,q\in\Bbb N\), 据性质 2,

\[p=f(p)=f(q\cdot\frac pq)\geqslant qf(\frac pq),\]

从而 \(f(\frac pq)\leqslant \frac pq\).

另一方面, 依据性质 4, \( f(\frac pq)\geqslant \frac p{f(q)}=\frac pq\).

综合起来, 就得到了 \(\forall r\in\Bbb Q_{\gt 0}, f(r)=r\).

Problem 6 (Alexander S. Golovanov and Mikhail A.Ivanov, Russia)

解答 1  

把一种漂亮的标记方式, 从 \(0\) 开始, 按逆时针方向, 写成一个序列

\begin{equation}a_0=0,a_1,a_2,\dotsc,a_n.\end{equation}

记 \(a_1=a, a_n=b,1\leqslant a,b\leqslant n\).

对非负整数 \(m(0\leqslant m\leqslant n)\), 有唯一的非负整数 \(j\), 使得 \(a_j=m\). 把这个 \(j\) 称为 \(m\) 的指标, 用 \(i(m)\) 表示.

为论述方便, 约定: 我们说 \(x+w=y+z\), 指的是连接标 \(x\) 和 \(w\) 的点的弦与连接标 \(y\) 和 \(z\) 的点的弦相交.

首先指出下述事实为真:

1. \(a+b\gt n\);
2. \(\gcd(a,b)=1\);
3. 若 \(b=n\), 则 \(a_i\equiv ia\pmod n, i=1,2,\dotsc,n-1\);
4. 若 \(0\leqslant x<x+a\leqslant n\), 则 \(i(x+a)=i(x)+1\), 即 \(x\) 右边紧挨的那个数就是 \(x+a\).

事实 \(3\) 与 \(4\) 说明: 一种漂亮的标记方式, 被 \(a\) 和 \(b\) 唯一决定.

事实上, 事实 \(4\) 表明属于 \(\bmod  a\) 的每个剩余类中的标记数, 是从小到大, 在 \((3)\) 中从左到右连续的排在一起; 事实 \(3\) 表明 \(b\) 决定了剩余类的排列顺序: 如果把 \((3)\) 中 \(\gt a\) 的数全部删除(即, 不计 \(0\), 把属于同一剩余类的标记看作一个数), 剩下的数恰是一个由 \(0,1,2,\dotsc,a\) 构成的漂亮的标记方式 \(0,a,\dotsc, c\), 最右边的 \(c\) 由 \(b\equiv c\pmod a\) 决定.

下面是这 \(4\) 件事情的证明:

事实 1 的证明  假若 \(1\leqslant a+b\leqslant n\), 那么必定有某个 \(a_i(1\lt i\lt n)\), 使得 \(a+b=a_i\). 如此一来, \(0+a_i=a+b\). 这不可能.

事实 2 的证明 假如质数 \(p\) 使得 \(p|a,p|b\). 不妨 \(a\lt b\). 此时, \((3)\) 中有一些数 \(\lt b\), 并且都不是 \(p\) 的倍数. 把这些数中, 指标最小的那个记为 \(u\). 那么, \(u-a, u-a+b\) 都不是 \(p\) 的倍数, 并且恰有一个, 记为 \(v\), 是 \(\lt b\) 的正整数. 注意, \(i(u)\lt i(v)\lt i(b)\), 因此, 无论 \(v=u-a\), 此时 \(0+u=a+v\), 还是 \(v=u-a+b\), 此时 \(a+v=u+b\), 都将导致矛盾.

事实 3 的证明  任意满足 \(a_j\equiv a_i+a\pmod n(2\leqslant i,j<n)\) 的 \(a_i,a_j\), 必定 \(i\lt j\). 因为 \(i\gt j\) 导致 \(a_i+a=0+a_j,a_i+a=n+a_j\) 之一发生, 这都是不允许的.

事实 4 的证明   \(i(x)\lt i(x+a)\) 是显然的, 因此, 属于 \(\bmod  a\) 的同一个剩余类中的标记数越大, 其指标越大. 于是, 如果有 \(y\), 使得 \(i(x)\lt i(y)\lt i(x+a)\), 必定 \(y\not\equiv x\pmod a\).

考察 \(x,x+a,x+2a,\dotsc,x^\prime\) 与 \(y,y+a,y+2a,\dotsc,y^\prime\), 这里 \(x^\prime\) 与 \(y^\prime\) 分别是 \(x\) 与 \(y\) 所属剩余类中最大的标记数. 于是, 必有 \(k\) 使得 \(i(x+ka)\lt i(y^\prime)\lt i(x+(k+1)a)\) 或 \(i(y+ka)\lt i(x^\prime)\lt i(y+(k+1)a)\). 不妨是前一种情况.

注意, \(z=y^\prime-(x+ka)\gt0\). 无论 \(i(z)\lt i(y^\prime)\) 导致 \(z+(x+(k+1)a)=a+y^\prime\), 还是 \(i(z)\gt i(y^\prime)\) 导致 \(z+(x+ka)=0+y^\prime\), 都是矛盾.

于是, 一种漂亮的标记方式决定了唯一一对满足下面三个条件的有序正整数对 \((a,b)\):

• \(1\leqslant a,b\leqslant n\);
• \(a+b\gt n\);
• \(\gcd(a,b)=1\).

反过来, 一对适合这三个条件有序正整数对的 \((a,b)\) 也定出了唯一的一种漂亮的标记方式.

事实上, 把下述 \(a\) 个集合, 从左往右排列:

\[P_a,P_{a-1},\dotsc,P_2,P_1,\]

这里的 \(P_i\) 恰好由所有这样一些标记数组成: 与 \(ib\) 属于 \(\bmod  a\) 的同一个剩余类. 然后, 再把 \(P_i\) 的元素依小到大, 从左到右排列, \(i=1,2,\dotsc,a\). 如此, 我们得到的一个形如 \((3)\) 这样的数列

\[0,a,\dotsc,b\]

是漂亮的标记.

如果不是这样, 有符合 \(i(x_1)\lt i(x_2)\lt i(x_3)\lt i(x_4)\) 的 \(x_1,x_2,x_3,x_4\), 使得 \(x_1+x_3=x_2+x_4\). 设 \(x_i\in P_{j_i}, i=1,2,3,4, a\geqslant j_1\geqslant j_2\geqslant j_3\geqslant j_4\geqslant1\). 如此, 则

\[j_1+j_3\equiv j_2+j_4\pmod a.\]

但是

\[0\leqslant (j_1+j_3)-(j_2+j_4)=(j_1-j_2)+(j_3-j_4)\leqslant j_1-j_4\leqslant a-1\]

给出 \(j_1=j_2, j_3=j_4\). 因而, \(x_1\lt x_2,x_3\lt x_4\), 这不可能.

如此, 我们找出了所有漂亮的标记方式.

直角坐标系中, 整点 \((x,y)\) 称为可见点, 如果 \(\gcd(x,y)=1\).

考察以四个整点 \(O, A(n,0),B(n,n)\), 和 \(C(0,n)\) 为顶点的正方形( \(O\) 是坐标原点). 显然, \(\triangle ABC\) 内部与线段 \(AB,BC\)上(不包括 \(A,C\) 两点)的可见点的数目, 一共是 \(M\); \(\triangle OAC\) 的内部的可见点的数目与线段 \(AC\) 内(不包括 \(A, C\) 两点)的可见点的数目, 一共有 \(N\). 因此, 正方形 \(OABC\) 的内部, \(AB,BC\) 两边(不包括 \(A,C\) 两点), 包括的可见点的数目之和 \(Q=M+N\)

另一方面, 一一映射

\[\{(x,y)\in\Bbb N^2|\gcd(x,y)=1,x+y\leqslant n\}\to\{(x,y)\in\Bbb N^2|\gcd(x,y)=1, y\lt x\leqslant n\}\]

\[(x,y)\mapsto (x+y,y)\]

说明 \(\triangle OAB\) 内部与线段 \(AB\) 内(不包括 \(A,B\)) 的可见点的数目, 一共亦是 \(N\)(\(\Bbb N\) 表示正整数集); 当然, \(\triangle OBC\) 内部与线段 \(BC\) 内(不包括 \(B,C\))的可见点的数目, 一共也仍然是 \(N\); 线段 \(OB\) 上只有 \(1\) 个可见点 \((1,1)\). 由此可见, \(Q=2N+1\).

综合两方面, 得到 \(M+N=2N+1\), 进而 \(M=N+1\), 这正是我们魂牵梦绕的物件.

解答 2

继续解答 1 的记号, 最关键的地方换个想法.

令 \(s=a+b\). 把等差数列 \(0,a,2a,\dotsc,(s-1)a\) 的每一项换成 \(\bmod   s\) 的余数, 再把 \(>n\) 的余数去掉, 得到一个新的数列:

\begin{equation}0,a,2a,\dotsc,(s-1)a\pmod s.\end{equation}

我们有: 数列 \((3)\) 和 \((4)\) 是相同的.

我们只要证明下述事情为真:

1. 当 \(0\leqslant x\leqslant n-a\) 时, \(i(x+a)=i(a)+1\);
2. 当 \(n-a<x< b\) 时, \(i(x+a-b)=i(x)+1\);
3. 当 \(b<x\leqslant n\) 时, \(i(x-b)=i(x)+1\).

事情 1 在解答 1 已证, 而事情 3 与事情 1 是一码事, 只不过反方向, 变成顺时针而已: 注意 \(0<x-b\leqslant n-b\) 即可.

只要证明事情 2 就成.

解答 3

把一种漂亮的标记方式, 从 \(0\) 开始, 按逆时针方向, 写成序列 \((3)\). 记 \(a_1=a,1\leqslant a\leqslant n\).

为论述方便, 约定: 我们说 \(x+w=y+z\), 指的是连接标 \(x\) 和 \(w\) 的点的弦与连接标 \(y\) 和 \(z\) 的点的弦相交.

令 \(k=\left[\dfrac na\right]\), 我们指出: \(a_i=ia,i=1,2,\dotsc,k\).

事实上, 若事情不是这样, 设 \(a_l\) 是 \(a_1,a_2,\dotsc,a_k\) 之中第一个使得 \(a_i\ne ia\) 的正整数, 则 \(1<l\leqslant k\).

若 \(a_l>a\), 因为 \(a_l-a\notin\{0,a,2a,\dotsc,(l-1)a\}\), 于是, \(0+a_l=a+(a_l-a)\). 这不可能!

如果 \(a_l<a\), 必有某个 \(j(j> l)\), 使得 \(a_j=la\). 因为 \(a_l+(l-1)a\notin\{0,a_1,a_2,\dotsc,a_l,a_j\}\), 并且 \(a+((l-1)a+a_l)=a_l+a_j\), 所以我们可以认为有某 \(m(m> j)\), 使得 \(a_m=(l-1)a+a_l\).

显然 \(la-a_l\notin\{0,a_1,a_2,\dotsc,a_l,a_j\}\), 并且 \((la-a_l)+a_l=0+a_j\), 可见必有 \(u(l<u<j)\), 使得 \(a_u=la-a_l\). 然而, 此时 \(a_{l-1}+a_j=a_u+a_m\) 导致矛盾.

假定 \(a_{k+1}=b,1\leqslant b\leqslant n\). 同前面一样的道理, \(b<a\). 使用类似于证明 1 中证明事实 2 的手段, 可以说明 \(\gcd(a,b)=1\).

设 \(r\) 是使得 \(ra-b>n\) 成立的最小正整数. 记 \(s=ra-b\). 把等差数列 \(0,a,2a,\dotsc,(s-1)a\) 的每一项换成 \(\bmod   s\) 的余数, 再把 \(\gt n\) 的余数去掉, 得到一个新的数列:

\begin{equation}0,a,2a,\dotsc,(s-1)a\pmod s.\end{equation}

我们有: 数列 \((3)\) 和 \((5)\) 是相同的.

显然 \(r=k+1\) 或 \(k+2\), 因此 \((3)\) 和 \((5)\) 的前 \(k+2\) 项相同. 假定 \(a_j(k+2<j\leqslant n)\) 是 \((3)\) 中不会在第一项

\[M=\varphi(1)+\varphi(2)+\dotsb+\varphi(n).\]

至于

\[N=\varphi(2)+\varphi(3)+\dotsb+\varphi(n),\]

解答 4

一种漂亮的标记方式, 我们从 \(0\) 开始, 按逆时针方向, 写成 \((3)\).

对非负整数 \(m\), 定义 \(m\) 的指标, 用 \(i(m)\) 表示, 为使得 \(a_{i(m)}=m\) 成立的那个下标, \(m=0,1,2,\dotsc,n\).

为论述方便, 约定: 我们说 \(x+w=y+z\), 指的是连接标 \(x\) 和 \(w\) 的点的弦与连接标 \(y\) 和 \(z\) 的点的弦相交.

令 \(A_n=\{(x,y)\in\Bbb N^2\mid x+y>n, \gcd(x,y)=1,1\leqslant x,y\leqslant n\}\). 任取 \((a,b)\in A_n\), 令 \(s=a+b\). 把等差数列 \(0,a,2a,\dotsc,(s-1)a\) 的每一项换成 \(\bmod   s\) 的余数, 得到数列 \((4)\), 记为 \([s-1;a,b]\). 再把 \([s-1;a,b]\) 中 \(>n\) 的项去掉, 得到的数列记为 \((n;a,b)\).

我们的目的是证明, 所有这样的 \((n;a,b)\), 就是所有漂亮的标记方式.

首先, \([s-1;a,b]\) 是漂亮的标记, 导出 \((n;a,b)\) 亦然.

其次, 对 \(n\) 进行归纳, 来证明我们的主要目标.

当 \(n=3\) 时, \((n;a,b)\) 这样的数列只有 \((3;1,3),(3;3,1),(3;2,3),(3;3,2)\) 这 \(4\) 个, 分别对应于仅有的 \(4\) 种漂亮的标记方式 \(0123,0321,0213,0312.\)

设

\begin{equation}0,a_1,a_2,\dotsc,a_{n+1}\end{equation}

是 \(n+1\) 的一种漂亮标记方式, 其项的指标用 \(i^\prime\) 表之. 如果把 \(n+1\) 从 \((6)\) 拿走, 得到 \(n\) 的一种漂亮标记 \((n;a,b)\). 显然的, 对于 \((n;a,b)\) 的项 \(x\), 若 \(0\leqslant x\leqslant n-a\), 则 \(i(x+a)=i(x)+1\); 若  \(0\leqslant x\leqslant n-b\), 则 \(i(x)=i(x+b)+1\).

(i)  若 \(i^\prime(n+1)=1\), 则 \(a+b=n+1\). 若不然, \(a+b>n+1\), 则\((n+1)+(a+b-n-1)=a+b\) 导致矛盾.

如果把 \(n+1+x\) 插在 \((n;a,b)\) 的项 \(x,x+a\) 之间, \(x=0,1,2,\dotsc,b-1\), 得到的 \(0,1,2,\dotsc,n+b\) 的一个排列

\begin{equation}c_0=0,c_1=n+1,c_2=a,\dotsc,c_{n+b}=b\end{equation}

就是 \([n+b;n+1,b]\). 因 \(c_{i+1}\equiv c_i+n+1\pmod {n+1+b},i=0,1,2,\dotsc,n+b-1\). 故而, 此时的 \((6)\) 即是 \((n+1;n+1,b)\).

(ii)  若 \(1\lt i^\prime(n+1)\lt n+1\), 则 \(a+b\gt n+1\).

\(i(n+1-b)=i(n+1-a)+1\), 结合 \(i^\prime(n+1)\gt i^\prime(n+1-a), i^\prime(n+1)\lt i^\prime(n+1-b)\), 定出 \(i^\prime(n+1)-i^\prime(n+1-a)=1, i^\prime(n+1-b)-i^\prime(n+1)=1\).

如果把 \(n+1\) 插在 \((n;a,b)\) 的项 \(n+1-a,n+1-b\) 之间, 得到的即是 \((n+1;a,b)\). 这是因为 \(n+1\equiv (n+1-a)+a\pmod s, n+1-b\equiv (n+1)+a\pmod s\).

(iii)  若 \(i^\prime(n+1)=n+1\), 则 \(a+b=n+1\).

如果把 \(n+1+x\) 插在 \((n;a,b)\) 的项 \(x+b,x\) 之间, \(x=0,1,2,\dotsc,a-1\), 得到的 \(0,1,2,\dotsc,a+n\) 的一个排列

\begin{equation}c_0=0,c_1=a,\dotsc,c_{n+a-1}=b,c_{n+a}=n+1\end{equation}

就是 \([n+a;a,n+1]\). 这是因为 \(c_{i+1}\equiv c_i+a\pmod {n+1+a},i=0,1,2,\dotsc,n+a-1\). 故而, 此时的 \((6)\) 即是 \((n+1;a,n+1)\).

我们还要指出, 若记 \(C_n=\{(n+1,b)\in\Bbb N^2\mid \gcd(n+1,b)=1,1\leqslant b\leqslant n\}\), \(D_n=\{(a,b)\in\Bbb N^2\mid a+b\gt n+1,\gcd(a,b)=1,1\leqslant a,b\leqslant n\}\), \(E_n=\{(a,n+1)\in\Bbb N^2\mid \gcd(a,n+1)=1,1\leqslant a\leqslant n\}\), 那么

\[A_{n+1}=C_n\cup D_n\cup E_n.\]

记 \(x\bmod y\) 表示 \(x\) 除以 \(y\) 得到的余数. 我们来建立集合 \(A_n\setminus\{(1,n),(n,1)\}\) 到 \(B_n=\{(x,y)\in\Bbb N^2|\gcd(x,y)=1,x+y\leqslant n\}\setminus\{(1,1)\}\) 的 一一对应:

\[A_n\setminus\{(1,n),(n,1)\}\to B_n\]

\[(x,y)\mapsto\begin{cases} (x\bmod y, y), &  x>y\\(x, y\bmod x), &  x<y\end{cases}\]

从而 \(|A_n|-2=|B_n|\). 这也就是 \(M-2=N-1\), 即 \(M=N+1\).

Annotations

1. 题 1 的证明 3 是 AoPS Forum 的 crazyfehmy 给出. 此外, 证明 2 最后写出来, 能有这么简洁, 也得益于大家的讨论.
2. 题目 2 的解答 2, 受到了一些网友的启发. 请注意: 对于 \(u\) 个红点, \(v\) 个蓝点组成的任意的哥伦比亚式点集, 总存在 \(\left[\dfrac{u+v}2\right]\) 条直线构成的好直线组, 但 \(\left[\dfrac{u+v}2\right]\) 不一定是最小值.
3. 题 3 的证明 1 也受益于百度数学竞赛吧 XmlSpinner 的证明; 证明 2 的思路出自贴吧 Richard1018 之手. 这方法可能以不同面目出现, 比如说, \(U,V,W\) 是\(\triangle ABC\) 外接圆的弧的中点.
4. 题 4 的证明 2, 使用了一个所谓的 Reim theorem. 这定理是这么说的: \(A,B,C,D\) 四点共圆, \(M,N\) 分别是 \(AC,BD\) 上两点, 则 \(MN\parallel CD\) 当且仅当 \(A,B,N,M\) 四点共圆.
5. 题 6 的证明 2 和 3 没有完成, 都是半成品. 这两个证明, 思路是类似的, 还做一点努力, 应该是可以完成. 证明 4 的部分想法来自水木社区数学版的 Cracker. “中等数学” 第九期给出了两种不一般的解法. 建议认真的看一看. “走向IMO2013” 的解答与”中等数学”是一样的.
6. 这 6 个问题, 尤其题目 3 和 4, 还能找到很多精彩的解答. 题 6, 使用归纳法, 有很多大同小异的手段可以指出 \(n\) 的一部分的漂亮标记有两个位置可以插入 \(n+1\), 剩下的部分只有一个位置可以插人 \(n+1\), 进而得到 \(M(n+1)-M(n)=\varphi(n+1)\), 然后定出 \(M=\varphi(1)+\varphi(2)+\dotsb+\varphi(n)\). 这办法被很多人采用.
7. 战国时期, 宋玉的作品”登徒子好色赋”中的描写女人美貌的名句“增之一分则太长，减之一分则太短，着粉则太白，施朱则太赤”, 其实也适用来成为解答写的好坏的标准之一.