# Day $$1$$

Tuesday, July 18, 2017

Problem 1. For each integer  $$a_0\gt1$$, define the sequence $$a_0$$, $$a_1$$, $$a_2$$, $$\dotsc$$ by:

$a_{n+1} = \begin{cases}\sqrt{a_n} & \text{if } \sqrt{a_n} \text{ is an integer,} \\a_n + 3 & \text{otherwise.}\end{cases}\quad \text{for each}\; n\geqslant 0.$

Determine all values of $$a_0$$ so that there exists a number $$A$$ such that $$a_n = A$$ for infinitely many values of $$n$$.

Problem 2. Let $$\Bbb R$$ be the set of real numbers. Determine all functions $$f\colon \Bbb R \rightarrow \Bbb R$$ such that, for all real numbers $$x$$ and $$y$$,

$f\big(f(x)f(y)\big) + f(x+y) = f(xy).$

Problem 3. A hunter and an invisible rabbit play a game in the Euclidean plane. The rabbit’s starting point, $$A_0$$ , and the hunter’s starting point, $$B_0$$ are the same. After $$n-1$$ rounds of the game, the rabbit is at point $$A_{n-1}$$ and the hunter is at point $$B_{n-1}$$ . in the $$n^{\text{th}}$$ round of the game, three things occur in order:

i) The rabbit moves invisibly to a point $$A_n$$ such that the distance between $$A_{n-1}$$ and $$A_n$$ is exactly $$1$$ .

ii) A tracking device reports a point $$P_n$$ to the hunter. The only guarantee provided by the tracking device to the hunter is that the distance between $$P_n$$ and $$A_n$$ is at most $$1$$ .

iii) The hunter moves visibly to a point $$B_n$$ such that the distance between $$B_{n-1}$$ and $$B_n$$ is exactly $$1$$ .

Is it always possible, no matter how the rabbit moves, and no matter what points are reported by the tracking device, for the hunter to choose her moves so that after $$10^9$$ rounds, she can ensure that the distance between her and the rabbit is at most $$100$$ ?

# Day $$2$$

Wednesday, July 19, 2017

Problem 4. Let $$R$$ and $$S$$ be different points on a circle $$\Omega$$ such that $$RS$$ is not a diameter. Let $$\ell$$ be the tangent line to at $$R$$. Point $$T$$ is such that $$S$$ is the midpoint of the line segment $$RT$$. Point $$J$$ is chosen on the shorter arc $$RS$$ of $$\Omega$$ so that the circumcircle  $$\Gamma$$ of triangle $$JST$$ intersects $$\ell$$ at two distinct points. Let $$A$$ be the common point of $$\Gamma$$ and $$\ell$$ that is closer to $$R$$. Line $$AJ$$ meets $$\Omega$$ again at $$K$$. Prove that the line $$KT$$ is tangent to $$\Gamma$$.

Problem 5. An integer $$N\geqslant2$$ is given. A collection of $$N(N + 1)$$ soccer players, no two of whom are of the same height, stand in a row. Sir Alex wants to remove $$N(N-1)$$ players from this row leaving a new row of $$2N$$ players in which the following $$N$$ conditions hold:

(1) no one stands between the two tallest players,

(2) no one stands between the third and fourth tallest players,

$$\vdots$$

(N) no one stands between the two shortest players.

Show that this is always possible.

Problem 6. An ordered pair $$(x, y)$$ of integers is a primitive point if the greatest common divisor of $$x$$ and $$y$$ is $$1$$. Given a finite set $$S$$ of primitive points, prove that there exist a positive integer $$n$$ and integers $$a_0$$, $$a_1$$ , $$\dotsc$$, $$a_n$$ such that, for each $$(x, y)$$ in $$S$$, we have:

$a_0x^n + a_1x^{n-1}y + a_2x^{n-2}y^2 + \dotsb + a_{n-1}xy^{n-1} + a_ny^n = 1.$

Tagged with:

2017 China IMO team selection test 3 day 1

2017 China IMO team selection test 3 day 2

2017 China IMO team selection test 2 day 1

2017 China IMO team selection test 2 day 2

$$\alpha$$, $$\beta$$ 都是无理数,

2017 China IMO team selection test 1 day 1

2017 China IMO team selection test 1 day 2

# 第 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 day 2

Tagged with:

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

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

$$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^\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$$.

IMO 2016 Problem 3 Proof 2

$$B_2B_3+B_3B_4+\dotsb+B_{k-1}B_k=B_2B_k.$$

$$\frac{B_iB_{i+1}}{A_iA_{i+1}}=\frac{A_1B_{i+1}}{A_1A_i},$$

$$i=2$$, $$3$$, $$\dotsc$$, $$k-1$$, 以及

$$\frac{B_2B_k}{A_2A_k}=\frac{A_1B_k}{A_1A_2}.$$

$$B_iB_{i+1}=\sqrt{\frac{b_{i+1}}{a_ia_{i+1}}},$$

$$i=2$$, $$3$$, $$\dotsc$$, $$k-1$$, 以及

$$B_2B_k=\sqrt{\frac{c}{a_2a_k}}.$$

$$\sum_{i=2}^{k-1}\sqrt{\frac{b_{i+1}}{a_ia_{i+1}}}=\sqrt{\frac{c}{a_2a_k}}.$$

Lemma 1  如果 $$a_1$$, $$a_2$$, $$\dotsc$$, $$a_n$$, $$b$$ 都是正有理数, 且

$\sum_{l=1}^n\sqrt{a_l}=\sqrt b,$

### 解答三

$$x\ne0$$ 是有理数, 记 $$x=\dfrac ab$$, $$a$$, $$b$$ 都是整数, $$b\ne0$$. $$p$$ 是质数, 定义 $$v_p(x)=v_p(a)-v_p(b)$$.

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

$$2S=2\sum_{l=1}^kS_{\triangle OA_lA_{l+1}}=\sum_{l=1}^kR^2\sin(2\alpha_l).$$

$$O$$, $$A_l$$, $$A_{l+1}$$ 是有理点蕴涵 $$S_{\triangle OA_lA_{l+1}}$$ 为有理数.

$$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{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}$$

• 第二个等号是由于第一个性质;
• $$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$$.

$$v_p\big(2S\big)=v_p\Big(\sum_{l=1}^kR^2\sin(2\alpha_l)\Big)\geqslant\alpha.$$

$$S_{\triangle OA_lA_{l+1}}=\dfrac{a_l^2}{\tan\alpha_l}$$ 蕴涵 $$\tan\alpha_l$$ 是有理数.

$$v_p(t_l)\geqslant\frac12(\alpha-\beta).$$

$v_p(1+t_l^2)=\beta-\beta=0,$

$$v_p\Big(\prod_{l=1}^k(1+t_l^2)\Big)=\sum_{l=1}^kv_p(1+t_l^2)=0.$$

$$f(x)=\prod_{l=1}^k(x+t_l)=\sum_{j=0}^{k-1}s_jx^j+x^k,$$

$$v_p(s_j)\geqslant\frac12(k-j)(\alpha-\beta),$$

$$j=0$$, $$1$$, $$2$$, $$\dotsc$$, $$k-1$$.

$\prod_{l=1}^k(\cos\alpha_l+i\sin\alpha_l)=\prod_{l=1}^k(\cos\alpha_l-i\sin\alpha_l)=-1,$

$$\prod_{l=1}^k(1+it_l)=\prod_{l=1}^k(1-it_l)\ne0,$$

$$f(i)=(-1)^kf(-i)\ne0.$$

$\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),$

$$\sum_{j=0}^{k-1}\big(1+(-1)^{k+j-1}\big)s_ji^j=0.$$

$$\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}$$

•  $$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$$ 与整数的乘积.

$$v_p(s_j)\geqslant\frac32(\alpha-\beta).$$

$$\big(1+(-1)^{k+j-1}\big)\big(k-1-j\big)s_ji^{k+j-1}$$ 是 $$s_j$$ 与整数的积, 因此

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

$\big(i^kf(i)\big)^2=f(i)f(-i)=\prod_{l=1}^k(1+t_l^2).$

$$v_p\big(i^kf(i)\big)=0.$$

$$\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}$$

Tagged with:

# 2016 第 57 届 IMO 解答

## Problem 1 (The Kingdom Of Belgium)

IMO 2016 Problem 1

$\angle FBA=\angle FAB=\angle DAC=\angle DCA= \angle EAD=\angle EDA.$

$$\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}$$

$$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.$

$$M$$ 是直角三角形 $$FBC$$ 的斜边 $$FC$$ 的中点, 因此 $$MF=MB$$. 由

$\angle MFB= \angle FBA+\angle FBA=\angle DAB$

$\angle DEA+\angle EAC= \angle DEA+(\angle EAD+\angle DAC)=\angle DEA+(\angle EAD+\angle EDA)=180^\circ$

## Problem 2 ( Australia)

• 第一类: 第 $$2$$, $$5$$, $$8$$, $$\dotsc$$, $$3k-1$$ 行的所有格子;
• 第二类: 第 $$2$$, $$5$$, $$8$$, $$\dotsc$$, $$3k-1$$ 列的所有格子; 以及
• 第三类: 小方格个数是三的倍数的所有对角线上的全部格子.

IMO 2016 Problem 2 Proof 1

## Problem 3 ( Russia)

$16S^2=2a^2b^2+2b^2c^2+2c^2a^2-a^4-b^4-c^4$

$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,$

$u=\max\{\alpha_{ij}, \; 1\leqslant i\lt j\leqslant m,\; j-i\gt1\}.$

IMO 2016 Problem 3 Proof 1

Ptolemy 定理给出

$ab+cd=ef.$

$a^2b^2+c^2d^2+2abcd=e^2f^2.$

$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,$

## Problem 4 (Luxembourg)

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 \equiv 7\pmod{19},\; a+1 \equiv 2\pmod7,\; a+2 \equiv 1\pmod 3,$

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

$$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$$ 满足要求.

$\big(P(a+2),P(a+5)\big)=3,\; \big(P(a+1),P(a+4)\big)=3$

Lemma 1   当 $$n$$ 为正整数, $$9\not\mid P(n)$$.

$4(n^2+n+1)=(2n+1)^2+3,$

Lemma 2   当 $$n$$, $$m$$ 都是正整数,  $$\big(P(n),P(n+m)\big)\mid (m^3+3m)$$.

$$\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}$$

$\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$

Lemma 4  当整数 $$t \equiv n, n^2\pmod{P(n)}$$, 必定 $$P(t) \equiv 0 \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}$$

## Problem 5 ( Russia)

$$\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}$$

\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}

\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}

$x-1\gt x-2\gt0,$

$-(x-2016)\gt-(x-2015)\gt0.$

\begin{equation*}-(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{equation*}

## Problem 6 (The Czech Republic)

(a) 在 $$n$$ 为奇数, 把青蛙放在 $$P_1$$, $$P_3$$, $$\dotsc$$, $$P_{2n-1}$$, 可以实现他的愿望.

$$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) 杰夫想实现他的理想的话, 青蛙不能放在圆上相邻的端点.

### Annotations

1. 今年的题, 如果时间充裕一点, 应该都能做出来
2. 又一次的证明, 出现精彩万分的数论题是多么不容易.
3. 最好的题是第 3 题, 毫无疑问. 本题需要一点智慧. 如果知道一点代数数论, 本题是有好几种突破口, 请参看续集 IMO 2016 solutions II.
4. 题 6 不适合作为 Q3 或 Q6, 难度不够, 似乎比 Q2 容易.
Tagged with: