# 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$$ 平行. 若一条线段的两端为结点, 且线段上没有其他结点, 称之为基本线段. 求遍历所有划分方式时, 基本线段数量的最小值个最大值.

cmo 2017 day 2

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:

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

Tagged with: