Jul 242013
 

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\).

IMO 2013 Problem 3 Proof 1

IMO 2013 Problem 3 Proof 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\) 的外接圆上. 其实, 这就是九点圆定理, 我们没有直接使用.

IMO 2013 Problem 3 Proof 2

IMO 2013 Problem 3 Proof 2

\(\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 的最后做一点改动.

IMO 2013 Problem 3 Proof 3

IMO 2013 Problem 3 Proof 3

\(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\) 上.

IMO 2013 Problem 4 Proof 1

IMO 2013 Problem 4 Proof 1

因 \(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 的后半部分.

IMO 2013 Problem 4 Proof 2

IMO 2013 Problem 4 Proof 2

记 \(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. 战国时期, 宋玉的作品”登徒子好色赋”中的描写女人美貌的名句“增之一分则太长,减之一分则太短,着粉则太白,施朱则太赤”, 其实也适用来成为解答写的好坏的标准之一.
 Posted by at 6:11 am  Tagged with:
Jul 232013
 

                                       Day \(1\)

  Tuesday, July 23, 2013

Problem 1. Prove that for any pair of  positive integers \(k\) and \(n\), there exist \(k\) positive integers \(m_1,m_2,\dotsc, m_k\)(not necessarily different) such that

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

Problem 2. A configuration of \(4027\) points in the plane is called Colombian if it consists of \(2013\) red points and \(2014\) blue points, and no three of the points of the configuration are collinear. By drawing some lines, the plane is divided into several regions. An arrangement of lines is good for a Colombian con guration if the following two conditions are satisfied:

  • no line passes through any point of the con guration;
  • no region contains points of both colours.

Find the least value of \(k\) such that for any Colombian con guration of \(4027\) points, there is a good arrangement of \( k\) lines.

Problem 3.  Let the excircle of triangle \(ABC\) opposite the vertex \(A\) be tangent to the side \(BC\) at the point \(A_1\). De fine the points \(B_1\) on \(CA\) and \(C_1\) on \(AB\) analogously, using the excircles opposite \(B\) and \(C\), respectively. Suppose that the circumcentre of triangle \(A_1B_1C_1\) lies on the circumcircle of triangle \(ABC\).Prove that triangle \(ABC\) is right-angled.

The excircle of triangle \( ABC\) opposite the vertex\( A\)  is the circle that is tangent to the line segment \(BC\), to the ray \(AB\) beyond \(B\), and to the ray \(AC\) beyond \(C\). The excircles opposite \(B\) and \(C\) are similarly defi ned.

                                      Day \(2\)

Wednesday, July 24, 2013

Problem 4. Let \(ABC\) be an acute-triangle with orthocenter \(H\), and let \(W\) be a point on the side \(BC\), lying strictlybetween \(B\) and \(C\). The points \(M\) and \(N\) are the feet of the altitudes from \(B\) and \(C\), respectively. Denote by \(\omega_1\) the circumcircle of \(BWN\), and let \(X\) be the point on \(\omega_1\) such that \(WX\) is a diameter of \(\omega_1\). Similarly, denote by \(\omega_2\) the circumcircle of triangle \(CWM\), and let \(Y\) be the point on \(\omega_2\) such that \(WY\) is a diameter of \(\omega_2\). Prove that the points \(X, Y\) and \(H\) are collinear.

Problem 5. Let \(\Bbb Q_{>0}\) be the set of positive rational numbers. Let \(f\colon\Bbb Q_{>0}\to\Bbb R\) be a function satisfying the following three conditions:

(i)   for all \(x,y\in\Bbb Q_{>0}\), we have \(f(x)f(y)\geqslant f(xy)\);
(ii)   for all \(x,y\in\Bbb Q_{>0}\), we have \( f(x+y)\geqslant f(x)+f(y)\);
(iii)  there exists a rational number \(a>1\) such that \(f(a)=a\).

Prove  that \(f(x)=x\) for all \(x\in\Bbb Q_{>0}\).

Problem 6. Let \(n\geqslant 3\) be an integer, and consider a circle with \(n+1\) equally spaced points marked on it. Consider all labellings of these points with the numbers \(0,1,\dotsc, n\) such that each label is used exactly once; two such labellings are considered to be the same if one can be obtained from the other by a rotation of the circle. A labelling is called beautiful if, for any four labels \(a<b<c<d\) with \(a+d=b+c\), the chord joining the points labelled \(a\) and \(d\) does not intersect the chord joining the points labelled \(b\) and \(c\).

Let \(M\) be the number of beautiful labellings, and let \(N\) be the number of ordered pairs \((x,y)\) of positive integers such that \(x+y\leqslant n\) and \(\gcd(x,y)=1\). Prove that

\[M=N+1.\]

                                       Day \(1\)

  2013 年 7 月 23 日, 星期二

第 1 题.  证明对于任意一对正整数 \(k\) 和 \(n\), 都存在 \(k\) 个(不必不相同的)正整数 \(m_1,m_2,\dotsc, m_k\) 使得

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

第 2 题.  平面上的 \(4027\) 个点称为是一个哥伦比亚式点集, 如果其中任意三点不共线, 且有 \(2013\) 个点是红色的, \(2014\) 个点是蓝色的. 在平面上画出一组直线, 可以将平面分成若干区域. 如果一组直线对于一个哥伦比亚式点集满足下述两个条件, 我们就称这是一个好直线组:

  • 这些直线不经过该哥伦比亚式点集中的任何一个点;
  • 每个区域中都不会同时出现两种颜色的点.

求 \(k\) 的最小值, 使得对于任意的哥伦比亚式点集, 都存在由 \(k\) 条直线构成的好直线组.

第 3 题. 设三角形\(ABC\) 的顶点 \(A\) 所对的旁切圆与边 \(BC\) 相切于点 \(A_1\). 类似地, 分别用顶点 \(B\) 和顶点 \(C\) 所对的旁切圆定义 \(CA \) 边上的点 \(B_1\) 和 \(AB\) 边上的点 \(C_1\). 假设三角形 \(A_1B_1C_1\) 的外接圆圆心在三角形 \(ABC\)  的外接圆上. 证明: 三角形\(ABC\) 是直角三角形.

三角形 \(ABC \) 的顶点 \(A\) 所对的旁切圆是指与边 \(BC \) 相切, 并且与边 \(AB, AC\) 的延长线相切的圆. 顶点 \(B, C\)所对的旁切圆可类似定义.

 

                                       Day \(2\)

  2013 年 7 月 24 日, 星期三

第 4 题. 设三角形 \(ABC\) 是一个锐角三角形, 其垂心为 \(H\), 设 \(W\) 是边 \(BC\) 上一点, 与顶点 \(B,C\) 均不重合. \(M\) 和 \(N\) 分别是过顶点 \(B\) 和 \(C\) 的高的垂足. 记三角形 \(BWN\) 的外接圆为 \(\omega_1\), 设 \(X\) 是 \(\omega_1\) 上一点, 且 \(WX\) 是  \(\omega_1\) 的直径. 类似地, 记三角形 \(CWM\)  的外接圆为  \(\omega_2\), 设 \(Y\) 是  \(\omega_2\) 上一点, 且 \(WY\) 是  \(\omega_2\) 的直径. 证明: \(点 X, Y\) 和 \(H\) 共线.

第 5 题.  记 \(\Bbb Q_{>0}\)是所有正有理数组成的集合. 设函数 \(f\colon\Bbb Q_{>0}\to \Bbb R\) 满足如下三个条件:

(i)  对所有的 \(x,y\in\Bbb Q_{>0}\), 都有 \(f(x)f(y)\geqslant f(xy)\);
(ii)  对所有的 \(x,y\in\Bbb Q_{>0}\), 都有 \(f(x + y) \geqslant f(x) + f(y)\);
(iii) 存在有理数 \(a > 1\), 使得 \(f(a) = a\).

证明: 对所有的 \(\Bbb Q_{>0}\), 都有 \(f(x) = x\).

第 6 题.  设整数 \(n \geqslant 3\) , 在圆周上有 \(n + 1\) 个等分点. 用数 \(0, 1,\dotsc, n\) 标记这些点, 每个数字恰好用一次. 考虑所有可能的标记方式; 如果一种标记方式可以由另一种标记方式通过圆的旋转得到, 那么认为这两种标记方式是同一个. 一种标记方式称为是漂亮的, 如果对于任意满足 \(a + d = b + c\) 的四个标记数 \(a < b < c < d\), 连接标 \(a\) 和 \(d\) 点的弦与连接标 \(b\) 和 \(c\) 的点的弦都不相交.

设 \(M\) 是漂亮的标记方式的总数, 又设 \(N\) 是满足 \(x + y \leqslant n\), 且 \(\gcd(x,y)=1\) 的有序正整数对 \((x,y)\)的个数. 证明:

\[M=N+1.\]

 Posted by at 9:49 am  Tagged with:
Jul 142012
 

Problem 1 (Evangelos Psychas, Greece)

It is obvious that

\[\angle JFL=\angle JBM-\angle FMB=\frac12(\angle BAC+\angle BCA)-\frac12\angle BCA=\frac12\angle BAC,\]

therefore \(J,L,A\) and \(F\) belong to a circle which implies that \(\angle JFS=90^{\circ}\). But \(\angle JMS=90^{\circ}\), so \(J,M,F\) and \(S\) are concyclic, \(\angle JSM=\angle JFM=\frac12\angle BAC\).

Similarly, \(\angle JTM=\frac12\angle BAC\), so \(\angle JSM=\angle JTM\).

Since \(JM\perp ST\), we obtain \(SM=MT\).

Problem 2 (Angelo di Pasquale, the current Australian leader)

It is easy to see that

\[a_k+1=a_k+\frac 1{k-1}+\dotsb+\frac 1{k-1}\geqslant k\sqrt[k]{\frac{a_k}{(k-1)^{k-1}}},\]

so \((a_k+1)^k\geqslant\frac{k^k}{(k-1)^{k-1}} \,a_k,\) the inequality is strict unless \(a_k=\frac1{k-1}\). Multiplying analogous inequalities for \(k=2,3,\dotsc,n\) yields

\[ \prod_{k=2}^n(a_k+1)^k\geqslant n^na_2a_3\dotsm a_n=n^n. \]

the inequality is strict because \(a_k=\frac1{k-1}\) holds for all \(k\in\{2,3,\dotsc,n\}\) is not possible .

Problem 3 (David Arthur, Canada)

The problem was actually written two years ago.

1. We can assume  \(n=2^k, N=n+1\).

The binary digits of  \(1,2,\dotsc,2^k\) are \(\overline{a_1a_2\ldots a_{k+1}}\), where  \(a_i(i=1,2,\dotsc,k+1)\) is \(0\) or \(1\); then, let  \(T\) is  the set of all the \(2^k\) binary digits. The binary digit of  \(2^k+1\) is \(100\ldots01.\) Define

\[S_1=\{100\ldots0\}, S_i=\{\overline{a_1a_2\ldots a_{k+1}}\in T|a_1=0, a_i=1\}, i=2,3,\dotsc,k+1.\]

  • B chooses  \(S_1\) repeatedly. If B get an answer of  no \(k+1\) times, then B can exclude the number \(100\ldots0\). Otherwise, A will eventually say yes.
  • If  A last said yes, B then asks \(S_2,S_3,\dotsc,S_{k+1}\), and guarantees a win.
2.  Let \(p\) be a  positive real number such that \( 1.99< p<2\). Let us choose \(k_0\) such that for every \(k>k_0\), the following relation holds:

\[(2-p)p^{k+1}-1.99^k>2.\]

We will prove that if  \(N\in\left(1.99^k+1, (2-p)p^{k+1}\right)\), then B cannot specify a set \(X(|X|\leqslant N-1)\) such that \(x\in X\).

\(T=\{1,2,\dotsc, N\}\). \(j\in\Bbb N\), The \( j\)-th question consists of \( B\) choosing a set \( S_j\subset T\) and we define \(P_j\) is \(S_j\) or \(S_j^C\) depend on the answer: if A answer it with yes, \(P_j=S_j\); Otherwise, \(P_j=S_j^C\). Let \(P_0=T\). Define \(q_j\) as follows:

\[q_j=q_j(P_j)=a_0+a_1p+a_2p^2+\dotsb+a_jp^j,\]

where \(a_0=\left|P_j\right|,a_i=\left|P_{j-i}\setminus \left(P_j\cup P_{j-1}\cup\cdots\cup P_{j-i+1} \right)\right|(i=1,2,\dotsc,j).\)   It is easy to see that \(\sum\limits_{i=0}^ja_i=N.\)   \(q_0=N.\)

The player \( A\) can keep the following relation holds:

\[q_j<\frac N{2-p},          j\geqslant0.\]

In fact, \(q_0=N<\frac N{2-p}.\) We  assume  that \(q_j<\frac N{2-p}\), then A can choose \( P_{j+1}\in\left\{S_{j+1},S_{j+1}^C\right\}\) such that \(q_{j+1}<\frac N{2-p}\). Let

\[q_{j+1}(S_{j+1})=b_0+b_1p+b_2p^2+\dotsb+b_jp^j+b_{j+1}p^{j+1},\]

\[q_{j+1}(S_{j+1}^C)=c_0+c_1p+c_2p^2+\dotsb+c_jp^j+c_{j+1}p^{j+1}.\]

Notice that \(b_0+c_0=N,b_i+c_i=a_{i-1}(i=1,2,\dotsc,j+1),\) so

\begin{equation*}\begin{split}q_{j+1}(S_{j+1})+q_{j+1}(S_{j+1}^C)&=N+p(a_0+a_1p+a_2p^2+\dotsb+a_jp^j)\\
&<N+p\cdot\frac N{2-p},\end{split}\end{equation*}

hence

\[ \min\left\{q_{j+1}(S_{j+1}),q_{j+1}(S_{j+1}^C)\right\}< \frac{N}2+\frac p2\cdot\frac N{2-p}=\frac N{2-p}.\]

so, A can take \( P_{j+1}\in\left\{S_{j+1},S_{j+1}^C\right\}\).

Since \(q_j<\frac N{2-p}<p^{k+1},\) we get that for \(i\geqslant k+1, a_i=0,\) then B cannot exclude a number in \(T\), and cannot specify a set \(X(|X|\leqslant N-1)\) such that \(x\in X\).

1.  可以认为 \(n=2^k, N=n+1\). 采用二进制.

把 \(1,2,\dotsc,2^k\) 都写成二进制: \(\overline{a_1a_2\ldots a_{k+1}}\), 这里 \(a_i(i=1,2,\dotsc,k+1)\) 是 \(0\) 或者 \(1\); 然后, 记 \(T\) 为这 \(2^k\) 个二进制数组成的集合. \(2^k+1\) 的二进制表示是 \(100\ldots01.\) 令

\[S_1=\{100\ldots0\}, S_i=\{\overline{a_1a_2\ldots a_{k+1}}\in T|a_1=0, a_i=1\}, i=2,3,\dotsc,k+1,\]

也就是说, \(S_i\) 就是 \(T\) 中所有满足 \(a_i=1\) 的元素组成的子集 \(( i=1,2,\dotsc,k+1).\)

乙采用如下问题, 可保证获胜: 第一次提问, 选择 \(S_1\), 并且接下来也一直选取\(S_1\), 甲的回答会出现两种情况:

  • 连续 \(k+1\) 次回答 “否”, 则 \(100\ldots0\) 可以排除;
  • 在至多 \(k+1\) 次回答中, 一旦出现”是”, 乙接下来的 \(k\) 次提问, 依次选取 \(S_2,S_3,\dotsc,S_{k+1}\), 就取得胜利. 事实上, 若甲最后的 \(k\) 次回答都是”是”, 则 \(x\in T\); 若甲最后的 \(k\) 次回答有一些是”否”, 则 \(x\) 绝对不可能是 \(\overline{a_1a_2\ldots a_{k+1}}\), 这里 \(a_1=0\), \(a_i=0\) 还是 \(1\) 取决于甲对 \(S_i\) 的答案: 若甲的回答是”是”, \(a_i=0\), 否则 \(a_i=1( i=2,3,\dotsc,k+1).\)

2. 解答 \(1\)  任取实数 \(p\) 使得 \(1.99<p<2\), 再选取正整数 \(k_0\), 使得当 \(k>k_0\) 时

\[(2-p)p^{k+1}-1.99^k>2.\]

设正整数 \(N\) 使得 \(1.99^k+1<N<(2-p)p^{k+1}\). 如果 \(n=N-1\), 我们来证明甲有办法使乙无法胜利.

\(T=\{1,2,\dotsc, N\}\). \(j\) 是正整数, 记 \(S_j\subset T\) 是乙的第 \(j\) 个问题展示的集合, 设 \(P_j\) 为 \(S_j\) 或者 \(S_j^C\), 取决于甲对 \(S_j\) 的答案: 若甲的回答是”是”, \(P_j=S_j\), 否则 \(P_j=S_j^C\); \(P_0=T\). 定义 \(q_j(j\geqslant0)\) 如下:

\[q_j=q_j(P_j)=a_0+a_1p+a_2p^2+\dotsb+a_jp^j,\]

这里 \(a_0=\left|P_j\right|,a_i=\left|P_{j-i}\setminus \left(P_j\cup P_{j-1}\cup\cdots\cup P_{j-i+1} \right)\right|(i=1,2,\dotsc,j).\) 此时 \(\sum\limits_{i=0}^ja_i=N.\)  注意 \(q_0=N.\)

我们指出, 甲可以使得

\[q_j<\frac N{2-p},           j\geqslant0\]

成为事实.

\(q_0=N<\frac N{2-p}.\) 假设已有 \(q_j<\frac N{2-p}\), 甲可选取 \( P_{j+1}\in\left\{S_{j+1},S_{j+1}^C\right\}\) 使得 \(q_{j+1}<\frac N{2-p}\). 事实上,

\[q_{j+1}(S_{j+1})=b_0+b_1p+b_2p^2+\dotsb+b_jp^j+b_{j+1}p^{j+1},\]

\[q_{j+1}(S_{j+1}^C)=c_0+c_1p+c_2p^2+\dotsb+c_jp^j+c_{j+1}p^{j+1}.\]

注意 \(b_0+c_0=N,b_i+c_i=a_{i-1}(i=1,2,\dotsc,j+1),\) 于是

\begin{equation*}\begin{split}q_{j+1}(S_{j+1})+q_{j+1}(S_{j+1}^C)&=N+p(a_0+a_1p+a_2p^2+\dotsb+a_jp^j)\\
&<N+p\cdot\frac N{2-p},\end{split}\end{equation*}

因之

\[ \min\left\{q_{j+1}(S_{j+1}),q_{j+1}(S_{j+1}^C)\right\}< \frac{N}2+\frac p2\cdot\frac N{2-p}=\frac N{2-p}.\]

于是, 可以选取 \( P_{j+1}\in\left\{S_{j+1},S_{j+1}^C\right\}\) 达到我们的要求.

既然 \(q_j<\frac N{2-p}<p^{k+1},\) 那么, 只要 \(i\geqslant k+1,\) 必定 \(a_i=0,\) 这导致乙无法排除 \(T\) 的任何一个元素, 不能指定一个集合\(X(|X|\leqslant N-1),\) 使得 \(x\in X\), 于是对于 \(n=N-1\), 乙不能取得胜利.

解答 \(2\) 记 \(p,q\) 是满足 \(1.99<p<q<2\) 的实数, 选取正整数 \(k_0\) 使得

\[\left(\frac pq\right)^{k_0}\leqslant 2\left(1-\frac q2\right),\quad   p^{k_0}-1.99^{k_0}>2.\]

对任意 \( k\geqslant k_0\), 选取 \( N\in\left(1.99^k+1, p^k\right)\). \( T=\{1,2,\dotsc, N\}\). \(j\) 是正整数, 记 \(S_j\subset T\) 是乙的第 \(j\) 个问题所问的集合, \(P_j\) 是 \(S_j\) 或者 \(S_j^C\), 取决于甲对 \(S_j\) 的答案: 若甲的回答是”是”, \(P_j=S_j\), 否则 \(P_j=S_j^C\); \(P_0=T\). 我们来指出, 甲有策略, 通过回答”是”或者”否”, 使得
\[ P_j\cup P_{j+1}\cup\cdots\cup P_{j+k}=T\]

对所有 \(j\in\Bbb N\) 成立.

定义 \( (\mathbf{x})_{j=0}^\infty=\left(x_1^j, x_2^j, \dotsc, x_N^j\right) \) 如下: \( x_1^0=x_2^0=\cdots =x_N^0=1 \); 在 \(P_{j+1}\) 选定之后, 定义 \( \mathbf x^{j+1} \):

\begin{equation}x_i^{j+1}=\left\{\begin{array}{rl} 1,& i\in P_{j+1},\\ q\, x_i^j, & i\notin P_{j+1}. \end{array}\right.\end{equation}

只要甲使得成立 \(x_i^j\leqslant q^k(1\leqslant i\leqslant N, j\geqslant0)\), 那么乙不能指定一个集合\(X(|X|\leqslant N-1),\) 使得 \(x\in X\), 于是对于 \(n=N-1\), 乙无法取得胜利.

记 \( T(\mathbf x)=\sum\limits_{i=1}^N x_i\), 甲只要使得 \( T\left(\mathbf x^j\right)\leqslant q^k( j\geqslant0)\) 即可. 这是可以做到的:
显而易见的事情是, \( T\left(\mathbf x^0\right)=N\leqslant p^k < q^k\).
假设已有 \( T\left(\mathbf x^j\right)\leqslant q^k\), 甲可以就乙的 \(S_{j+1}\) 选取 \( P_{j+1}\in\left\{S_{j+1},S_{j+1}^C\right\}\) 使得 \( T\left(\mathbf x^{j+1}\right)\leqslant q^k \). 假定甲回答”是”, 此时 \( P_{j+1}=S_{j+1}\), 记 \(\mathbf y\) 是根据 \((1)\) 得到的序列; 相应地, 记 \(\mathbf z\) 是甲回答”否”, \( P_{j+1}=S_{j+1}^C\), 根据 \((1)\) 得到的序列. 于是

\[ T\left(\mathbf y\right)=\sum_{i\in S_{j+1}^C} qx_i^j+\left|S_{j+1}\right|,\]

\[ T\left(\mathbf z\right)=\sum_{i\in S_{j+1}} qx_i^j+\left|S_{j+1}^C\right|.\]

因此

\[ T\left(\mathbf y\right)+T\left(\mathbf z\right)= q\cdot T\left(\mathbf x^j\right)+ N\leqslant q^{k+1}+ p^k, \]

根据选取的 \(k_0\) 的性质, 得

\[ \min\left\{T\left(\mathbf y\right),T\left(\mathbf z\right)\right\}\leqslant \frac{q}2\cdot q^k+\frac{p^k}2\leqslant q^k.\]

Problem 4 (Liam Baker, South Africa)

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

  1. 令 \(a=b=c=0\), 得 \(f(0)=0\);
  2. 令 \(b=-a,c=0\), 得 \(f(a)=f(-a)\). 于是只需讨论当 \(a\) 为正整数时的 \(f(a)\) 就行了.
  3. 若有 \(a\in\Bbb Z\), 使得 \(f(a)=0\), 那么, 对于任意整数 \(b\), 由 \(a+b+(-a-b)=0\) 得 \(f(a+b)=f(b).\)

根据性质 \(3\), 若 \(f(1)=0,\) 则 \(f\) 有周期 \(1\), 故而 \(f(x)=c\) 对所有 \(x\) 成立, 这又迫使 \(f(x)=0\) 对所有 \(x\). 下面假设 \(f(1)\neq0.\)

令 \(a=b=1,c=-2\), 得 \(f(2)=0\) 或者 \(f(2)=4f(1).\)

若 \(f(2)=0\), 由第 \(3\) 条性质, \(f\) 有如下形式:

\begin{equation}f(x)=\left\{\begin{array}{rl}0,& 2\mid n,\\ c, & 2\not\mid n.\end{array}\right.\end{equation}

这里 \(c\) 是任意的整数. 很容易验证, 这样的函数都符合要求.

若 \(f(2)=4f(1)\), 则 \(i=0,1,2\) 时, 已有 \(f(i)=f(1)i^2.\) 假定当 \(k=0,1,2,\dotsc, n\) 时, \(f(i)=f(1)i^2\) 已经成为事实, 由 \(1+n+(-1-n)=0\) 得

\[f(1)^2+n^4f(1)^2+f(n+1)^2=2n^2f(1)^2+2(n^2+1)f(n+1)f(1),\]

这也就是

\[\left(f(n+1)-(n+1)^2f(1)\right)\left(f(n+1)-(n-1)^2f(1)\right)=0.\]

如果 \(f(n+1)=f(1)(n-1)^2\), 由 \((n+1)+(1-n)-2=0\) 得

\[2(n-1)^4f(1)^2+16f(1)^2=2 (n-1)^4f(1)^2+16(n-1)^2f(1)^2,\]

于是 \(n=2,f(3)=f(1)\). 由 \(1+3-4=0\) 得 \(2f(1)^2+f(4)^2=2f(1)^2+4f(1)f(4),\) 从而 \(f(4)=0\) 或者 \(f(4)=4f(1)=f(2)\). 假定 \(f(4)\neq0\), 由 \(2+2-4=0\) 得 \(2f(2)^2+f(4)^2=2f(2)^2+4f(2)f(4),\) 于是 \(f(4)=4f(2).\) 结合已经得到的 \(f(4)=f(2)\) 得\(f(2)=0\). 这不可能! 于是 \(f(4)=0\), \(f\) 有周期 \(4\), 所以

\begin{equation}f(x)=\left\{\begin{array}{rl}0,& 4\mid n,\\ c, & 2\nmid n,\\ 4c, & n\equiv2\pmod4\end{array}\right.\end{equation}

这里 \(c\) 是任意的整数. 很容易验证, 这样的函数都符合要求.

如果 \(f(n)=f(1)n^2\) 对所有的正整数 \(n\) 都成立, 即

\begin{equation}f(n)=cn^2,\end{equation}

这里 \(c\) 是任意的整数. 很容易验证, 这样的函数都符合要求.

综上所述, 所有形如 \((2),(3),(4)\) 的函数就是要求的函数.

Problem 5 (Josef Tkadlec, Czech Republic)

解答 \(1\)     把以 \(A\) 为心, \(AC\) 为半径的圆和以 \(B\) 为心, \(BC\) 为半径的圆分别记为 \(\odot A,\odot B,\) \(CD\) 即是两圆根轴. 分别过 \(A,B\) 作 \(BX,AX\) 的垂线 \(AF,BE\), 垂足为 \(F,E\). 设 \(AF,BE\) 相交于点 \(W\), 则 \(X\) 是 \(\triangle WAB\) 的垂心, 于是 \(W\) 在 \(DC\) 的延长线上.

由 \(AL^2=AC^2=AD\cdot AB=AF\cdot AW\) 得 \(AL\perp WL, WL\) 是\(\odot A\) 的切线. 同理 \(BK\perp WK, WK\) 是\(\odot B\) 的切线. \(W\) 在两圆根轴上, 故而 \(WL=WK\). 结合 \(AL\perp WL, BK\perp WK\) 就推出了 \(ML=MK\).

解答 \(2\)    把以 \(A\) 为心, \(AC\) 为半径的圆和以 \(B\) 为心, \(BC\) 为半径的圆分别记为 \(\odot A,\odot B,\) \(CD\) 即是两圆根轴. 分别延长 \(AX,BX\) 交 \(\odot B,\odot A\) 于 \(P,Q\) 两点. \(X\) 在根轴上, 所以 \(L,P,Q,K\) 四点共圆, 记此圆为 \(\odot O\).

\(AC\) 为 \(\odot B\) 的切线, 所以 \(AL^2=AC^2=AK\cdot AP\), \(AL\) 是 \(\odot O\) 的切线. 同理, \(BK\) 也是 \(\odot O\) 的切线, 故而 \(ML=MK\).

Problem 6 (Dušan Djukić, Serbia)

记 \(M=\max\{a_1,\dotsc, a_n\}\), 那么 \(1\cdot 3^{M-a_1}+ 2\cdot 3^{M-a_2}+\dotsb + n\cdot3^{M-a_n}=3^M\), 于是

\[1+2+\dotsb+n=\frac{n(n+1)}2\equiv1\pmod2,\]

此时必定 \(n\equiv1,2\pmod4\).

下面来证明, 对形如 \(4k+1\) 或者 \(4k+2\) 的 正整数 \(n\), 可以找到符合要求的 \(a_1,a_2,\dotsc,a_n\).

先对 \(n=4k+1(k\geqslant0)\) 找出符合要求的 \(\mathbf a\): 当\(k=0\) 时, \(a_1=0\) 可以. 下面假设 \(k>0\).

设 \(\mathbf g=\left(1, 2, \dotsc, 4k,4k\right)\), 其分量用 \(g_i\) 表示. 记 \(\mathbf a=\left(a_1, a_2, \dotsc, a_{4k+1}\right)\) 为 \((1,2,\dotsc,4k+1)\) 的一个排列, \(\displaystyle S(\mathbf a)=\sum_{i=1}^{4k+1}\frac{a_i}{3^{g_i}}.\) 由于 \(\displaystyle \sum_{i=1}^{4k+1}\frac1{2^{g_i}}=1,\) 因此只要找出一个 \(\mathbf a \) 使得  \(\displaystyle S(\mathbf a)=1\) 即可.

\[\mathbf a=\left(2,1,4,3,\dotsc,2k,2k-1,2k+2,2k+1,\dotsc,4k,4k-1,4k+1\right),\]

则 \(\displaystyle S(\mathbf a)=1+\frac{2k}{3^{4k}}.\)  记

\[\mathbf a\prime=\left(2,1,4,3,\dotsc,2k,2k-1,2k+1,\dotsc,4k,4k-1,4k+1,2k+2\right),\]

则 \(\displaystyle S(\mathbf a)-S(\mathbf a\prime)=\frac{2k}{3^{4k}}\), 故而 \(\displaystyle S(\mathbf a\prime)=1.\)

对序列 \(\mathbf a=\left(a_1, a_2, \dotsc, a_n\right)\), 记

\[L(\mathbf a)=\sum_{i=1}^n\frac1{2^{a_i}},R(\mathbf a)=\sum_{i=1}^n\frac i{3^{a_i}}.\]

假定对 \(n=2m+1\) 存在非负整数序列 \(\mathbf a=\left(a_1, a_2, \dotsc, a_n\right)\) 使得 \(L(\mathbf a)=R(\mathbf a)=1\), 考虑序列\(\mathbf a^\prime=(a_1^\prime,\dots, a_{n+1}^\prime)\):

\[a_j^\prime=\left\{\begin{array}{rl} a_j,&  j\notin \{m+1,2m+2\},\\
a_{m+1}+1,&  j\in \{m+1,2m+2\}.\end{array}\right.\]

可见

\[L\left(\mathbf a^\prime\right)=L(\mathbf a)-\frac1{2^{a_{m+1}}}+2\cdot \frac1{2^{a_{m+1}+1}}=1,\]

\[R\left(\mathbf a^{\prime}\right)=R(\mathbf a)- \frac{m+1}{3^{a_{m+1}}}+\frac{m+1}{3^{a_{m+1}+1}}+\frac{2m+2}{3^{a_{m+1}+1}}=1.\]

我们对 \(n=2m+2\) 找到了合乎要求的非负整数序列.

综上, 满足 \(n\equiv1,2\pmod4\) 的正整数就是所求.

 

Comments on the problems

可以把本届 IMO 与 \(2000\) 年做一个比较. 这两届IMO的 \(6\) 个问题, 难度相当, 在IMO历史上, 我个人觉得至多中等; 风格也极为相似: 最难的都是第 \(3\) 题, 碰巧都是组合, 都有 \(2\) 个部分, 一个肯定一个否定, 解答策略也不无相似.

关于本届 IMO 的 problem \(3\)

\(1\). 有这么一个趣味的数学游戏, 书上应该不难找到:

把 \(1,2,\dotsc,31\) 都写成二进制: \(\overline{a_5a_4a_3a_2a_1}\), 这里 \(a_i(i=1,2,3,4,5)\) 是 \(0\) 或 \(1\); 然后, 记 \(T\) 为这 \(31\) 个二进制数组成的集合. 令

\[ S_i=\{\overline{a_5a_4a_3a_2a_1}\in T| a_i=1\}, \]

也就是说, \(S_i\) 就是 \(T\) 中所有满足 \(a_i=1\) 的元素组成的子集, \(|S_i|=16( i=1,2,3,4,5).\)

现在取来 \(5\) 张纸, 把 \(S_i\) 中的 \(16\) 个数写在第 \(i\) 张纸上\((i=1,2,3,4,5)\), 就成了一种生日预测卡: 游戏者看到的, 就是这 \(5\) 张卡片. 然后, 利用这套卡片来猜测对方的生日: 你只要告诉我, 哪几张卡片上有你的生日, 我就能知道你的生日是哪一天.

这个游戏背后的玄机, 和我们给出的 \(1\) 的解法, 是一致的. 当然, 并不是说\(1\) 只能这么解决. 乙有别的提问途径, 也可保证获胜, 只不过没有这么轻松.

\(2\). 难度稍大一些, 但我们采取的手段也不新鲜: 考察一个辅助函数, 这个函数有某种性质, 单调性, 有界, 不变量等等, 反映的都是隐藏在游戏中的某个”量”的性质. \(2000\) IMO 的 problem \(3\) 的 \(2\) 是这么解决的, \(1986\) 年 IMO 的 problem \(3\) 仍然是这样的思路.

游戏中出现的量是”离散”而不是”连续”的, 因此, 这种做法屡试不爽!

\(3\). 这里给出的”两种”证法, 实质上没有任何差别.

 Posted by at 5:13 pm  Tagged with:
Jul 102012
 

                                       Day \(1\)

                                                                                                       Tuesday, July 10, 2012    9:00 am-1:30 pm

Problem 1.  Given triangle \(ABC\) the point \(J\) is the centre of the excircle opposite the vertex \(A\). This excircle is tangent to the side \(BC\) at \(M\), and to the lines \(AB\) and \(AC\) at \(K\) and \(L\), respectively. The lines \(LM\)  and \(BJ\) meet at \(F\), and the lines \(KM\) and \(CJ\) meet at \(G\). Let \(S\) be the point of intersection of the lines \(AF\) and \(BC\), and let \(T\) be the point of intersection of the lines \(AG\) and \(BC\).
Prove that \(M\) is the midpoint of \(ST\).

(The excircle of \(ABC\) opposite the vertex \(A\) is the circle that is tangent to the line segment \(BC\), to the ray \(AB\) beyond \(B\), and to the ray \(AC\) beyond \(C\).)

Problem 2.  Let  \(n\geqslant 3\) be an integer, and let  \(a_2,a_2,\dotsc,a_n\) be positive real numbers such that \(a_2a_3\dotsm a_n=1.\) Prove that

\[ \left(1+a_2\right)^2\left(1+a_3\right)^3\dotsm\left(1+a_n\right)^n>n^n.\]
Problem 3.   The liar’s guessing game is a game played between two players \(A\) and \(B\). The rules of the game depend on two positive integers \(k\) and \(n\) which are known to both players.
At the start of the game \(A\) chooses integers \(x\) and \(N\) with \(1\leqslant x \leqslant N\). Player \(A\)  keeps \(x\) secret, and truthfully tells \(N\) to player \(B\). Player \(B\) now tries to obtain information about \(x\) by asking player \(A\) questions as follows: each question consists of \(B\) specifying an arbitrary set \(S\) of positive integers (possibly one specified in some previous question), and asking \(A\) whether \(x\) belongs to \(S\). Player \(B\) may ask as many such questions as he wishes. After each question, player \(A\) must immediately answer it with yes or no, but is allowed to lie as many times as she wants; the only restriction is that, among any \(k+1\) consecutive answers, at least one answer must be truthful.
After \(B\) has asked as many questions as he wants, he must specify a set \(X\) of at most \(n\) positive integers. If \(x\) belongs to \(X\), then \(B\) wins; otherwise, he loses. Prove that:

  1. If  \(n\geqslant 2^k\), then \(B\) can guarantee a win.
  2. For all sufficiently large \(k\), there exists an integer \(n\geqslant1.99^k\) such that \(B\) cannot guarantee a win.

 

                                      Day \(2\)

                                                                          Wednesday, July 11, 2012     9:00 am-1:30 pm

Problem 4.  Find all functions \(f:\Bbb Z \rightarrow\Bbb Z\) such that, for all integers \( a,b,c\) that satisfy \(a+b+c=0\), the following equality holds:

\[ f(a)^2+f(b)^2+f(c)^2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a). \]

(Here \(\Bbb Z\) denotes the set of integers.)

Problem 5.  Let \( ABC \) be a triangle with \(\angle BCA=90^\circ\), and let \(D\) be the foot of the altitude from \(C\). Let \(X\) be a point in the interior of the segment \(CD\). Let \(K\) be the point on the segment \(AX\) such that \(BK=BC\). Similarly, let \(L\) be the point on the segment \(BX\) such that \(AL=AC\). Let \(M\) be the point of intersection of \(AL\) and \(BK\).
Show that \(MK=ML\).

Problem 6.  Find all positive integers \(n\) for which there exist non-negative integers \(a_1,a_2,\dotsc,a_n\) such that

\[\frac1{2^{a_1}}+\frac1{2^{a_2}}+\dotsb+\frac1{2^{a_n}}=\frac1{3^{a_1}}+\frac2{3^{a_2}}+\dotsb+\frac n{3^{a_n}}= 1.\]

 

 

 

                                     第一天

                                                                                   2012年7月10日, 星期二

1.  设 \(J\) 为三角形 \(ABC\) 顶点 \(A\) 所对旁切圆的圆心. 该旁切圆与边 \(BC\) 相切于点 \(M\), 与直线 \(AB\) 和 \(AC\) 分别相切于点\(K\) 和 \(L\). 直线 \(LM\) 和 \(BJ\) 相交于点 \(F\), 直线 \(KM\) 与 \(CJ\) 相交于点 \(G\). 设 \(S\) 是直线 \(AF\) 和 \(BC\) 的交点, \(T\) 是直线 \(AG\) 和 \(BC\) 的交点.
证明: \(M\) 是线段 \(ST\) 的中点.

(三角形 \(ABC\) 的顶点 \(A\) 所对的旁切圆是指与边 \(BC\) 相切, 并且与边 \(AB,AC\) 的延长线相切的圆.)

2. 设整数 \(n\geqslant 3\), 正实数\(a_2,a_2,\dotsc,a_n\) 满足 \(a_2a_3\dotsm a_n=1.\) 证明:

\[ \left(1+a_2\right)^2\left(1+a_3\right)^3\dotsm\left(1+a_n\right)^n>n^n.\]
3.  “欺诈猜数游戏”在两个玩家甲和乙之间进行, 游戏依赖于两个甲和乙都知道的正整数 \(k\) 和 \(n\).
游戏开始时甲先选定两个整数 \(x\) 和 \(N,1\leqslant x \leqslant N.\) 甲如实告诉乙 \(N\) 的值, 但对 \(x\) 守口如瓶. 乙现在试图通过如下方式的提问来获得关于 \(x\) 的信息: 每次提问, 乙任选一个由若干正整数组成的集合 \(S\) (可以重复使用之前提问中使用过的集合), 问甲”\(x\) 是否属于 \(S\)?”. 乙可以提任意数量的问题. 在乙每次提问之后, 甲必须对乙的提问立刻回答 “是” 或 “否”, 甲可以说谎话, 并且说谎的次数没有限制, 唯一的限制是甲在任意连续 \(k+1\) 次回答中至少有一次回答是真话.
在乙问完所有想问的问题之后, 乙必须指出一个至多包含 \(n\) 个正整数的集合 \(X\), 若 \(x\) 属于 \(X\), 则乙获胜; 否则甲获胜. 证明:

  1. 若 \(n\geqslant 2^k\), 则乙可保证获胜;
  2. 对所有充分大的整数 \(k\), 存在整数 \(n\geqslant1.99^k\), 使得乙无法保证获胜.

 

                                      第二天

                                                                                     2012年7月11日, 星期三

4.  求所有的函数 \(f:\Bbb Z \rightarrow\Bbb Z\), 使得对所有满足 \(a+b+c=0\) 的整数 \( a,b,c\), 都有

\[ f(a)^2+f(b)^2+f(c)^2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a). \]

(这里 \(\Bbb Z\) 表示整数集.)

 5.  已知三角形 \( ABC \) 中,  \(\angle BCA=90^\circ\),  \(D\) 是过顶点 \(C\) 的高的垂足. 设 \(X\) 是线段 \(CD\) 内部的一点.  \(K\) 是线段 \(AX\) 上一点, 使得 \(BK=BC\).  \(L\) 是线段 \(BX\) 上一点, 使得 \(AL=AC\). 设 \(M\) 是 \(AL\) 与 \(BK\) 的交点.
证明 : \(MK=ML\).

6.  求所有的正整数 \(n,\) 使得存在非负整数  \(a_1,a_2,\dotsc,a_n,\) 满足

\[\frac1{2^{a_1}}+\frac1{2^{a_2}}+\dotsb+\frac1{2^{a_n}}=\frac1{3^{a_1}}+\frac2{3^{a_2}}+\dotsb+\frac n{3^{a_n}}= 1.\]

 Posted by at 9:55 am  Tagged with: