China National Team Selection Test

We need three lemmas. Firstly, define $N^{\ast }$ as the set of all the positive integers.

Lemma 1 If there is an arithmetic progression having infinite positive integer terms with the same color, then the conclusion holds.

Proof: Let $c_1<c_2<\cdots <c_n<\dots$ be a red arithmetic progression of positive integers, we can set $a_i=c_{2i-1}$ ($i=1,2,3,\dots$) to obtain a sequence such that the condition holds.

Lemma 2 If for any $i\in N^{\ast }$, there exists a positive integer $j$, such that $i,\frac{i+j}{2}$, $j$ are of the same color, then the conclusion holds.

Proof: Let $a_1=1$, and $a_1$ be red. Since there exists $k\in N^{\ast }$ such that $a_1,\frac{a_1+k}{2}$, $k$ have the same color, so we can set $a_2=k$. In the same way, we can have a sequence of red numbers satisfying $$a_1<\frac{a_1+a_2}{2}<a_2<\frac{a_2+a_3}{2}<a_3<\dots$$

Lemma 3 If there is no arithmetic progression satisfying the condition of Lemma 1, and there exists $i_0\in N^{\ast }$, such that for every $j\in N^{\ast }$, $i_0,\frac{i_0+j}{2}$, $j$ have different colors, then the conclusion holds.

Proof: We can suppose $i_0=1$, otherwise using $N^{\prime }=\{n{i}_0\mid n\in {\mathbb{N}}^{\ast }\}$ in place of ${\mathbb{N}}^{\ast }$, will yield the same result. Let $i_0=1$ be a red number. Then we have the following condition: For every $k\in {\mathbb{N}}^{\ast }$, $k\ge 2$, $k$ and $2k-1$ cannot be both red. ① Since there is no arithmetic progression having infinite terms with the same color, therefore there are infinite terms of blue colored numbers of different parities in ${\mathbb{N}}^{\ast }$. We prove there is an infinite sequence of odd numbers of blue color in ${\mathbb{N}}^{\ast }$. Let $a_1$ be a blue odd number, and suppose odd numbers $a_1<a_2<\cdots <a_n$ satisfy that $$a_1<\frac{a_1+a_2}{2}<a_2<\cdots <a_{n-1}<\frac{a_{n-1}+a_n}{2}<a_n$$ are all blue. Now we prove there exists an odd number $a_{n+1}\in {\mathbb{N}}^{\ast }$, such that $\frac{a_n+a_{n+1}}{2}$ and $a_{n+1}$ are blue. ②

(1) If for every $i\in {\mathbb{N}}^{\ast }$, the numbers $a_n+i,a_n+2i$ have different colors, and there is no $a_{n+1}$ satisfying ②, then for $a_{n+1}>a_n$, numbers $\frac{a_n+a_{n+1}}{2}$ and $a_{n+1}$ cannot be both blue. ③ Since there is no arithmetic progression with infinite terms of the same color, there must exist infinitely many red and blue numbers in ${\mathbb{N}}^{\ast }$. Let $i\in {\mathbb{N}}^{\ast }$ such that $a_n+i$ is red, then $a_n+2i$ is blue. Write $a_n=2k+1$, we know $2k+1$ is blue, $2k+i+1$ is red, $2k+2i+1$ is blue. Using ①, we know that $4k+2i+1(=2(2k+i+1)-1)$ is blue. Similarly from ③, $3k+i+1=\frac{(2k+1)+(4k+2i+1)}{2}$ is red. From ① we get $6k+2i+1=2(3k+i+1)-1$ to be blue, and so on. Consequently, we have an arithmetic progression $\{2nk+2i+1{\}}_{i=1}^{\infty }$ of blue numbers, contradiction! Hence there must be a number $a_{n+1}$ satisfying ②.

(2) Suppose there is $i\in {\mathbb{N}}^{\ast }$, such that $a_n+i$ and $a_n+2i$ have the same color. Let $a_n=2k+1$. Firstly, if $a_n+i$ and $a_n+2i$ are blue, then $a_{n+1}=a_n+2i$, satisfying ②. Secondly, if $a_n+i$ and $a_n+2i$ are red, then from ① we have $4k+2i+1(=2(2k+i+1)-1)$ and $4k+4i+1(=2(2k+2i+1)-1)$ being blue. So if $3k+2i+1=\frac{(2k+1)+(4k+4i+1)}{2}$ are blue, then $a_{n+1}=4k+4i+1$, hence satisfying ②, otherwise, the number $6k+4i+1(=2(3k+2i+1)-1)$ is blue, then $a_{n+1}=6k+4i+1$, satisfying ②. Hence proving Lemma 3.

Therefore combining Lemmas 1, 2 and 3, we are done.