Problem 1764

We need three lemmas. Firstly, define $N^*$ 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 < \dots < 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^*$, 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^*$ 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^*$, such that for every $j \in N^*$, $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' = \{ni_0 \mid n \in \mathbb{N}^*\}$ in place of $\mathbb{N}^*$, 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}^*$, $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}^*$. We prove there is an infinite sequence of odd numbers of blue color in $\mathbb{N}^*$.
Let $a_1$ be a blue odd number, and suppose odd numbers $a_1 < a_2 < \dots < a_n$ satisfy that
$$a_1 < \frac{a_1 + a_2}{2} < a_2 < \dots < 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}^*$, such that $\frac{a_n + a_{n+1}}{2}$ and $a_{n+1}$ are blue. ②

(1) If for every $i \in \mathbb{N}^*$, 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}^*$. Let $i \in \mathbb{N}^*$ 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}^*$, 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.