Problem 1034

Let the two subsets be denoted by $A$ and $B$, and that $n$ is an element of $A$ is denoted (as usual) by $n \in A$. We assume that the statement of the problem is not true, and $A, B$ is such a partition where there is no three-term arithmetic progression. We will show that if $n \geq 4$, then $(n-1)$ and $(n+1)$ cannot belong to the same set. If indeed $n-1 \in A, n+1 \in A$, then only $n-3 \in B, n+3 \in B$ could be possible, but then $n$ could not be in either $A$ or $B$. Clearly, we can assume that 7 is in $A$. Then, according to our previous finding, only $5 \in B, 9 \in B$ can be true, and because of these, $3 \in A, 11 \in A$. Since the arithmetic mean of 3 and 11 must be in $A$ according to our assumption, we have reached a contradiction, so our statement is true.

Remark. It can also be shown that the first 9 natural numbers cannot be partitioned into two sets such that neither contains a three-term arithmetic progression. This is not true for the first 8 numbers, as the partition $A=\{1,2,5,6\}, B=\{3,4,7,8\}$ demonstrates. As can be inferred from the theorem recently proved by mathematician Endre Szemerédi, if we partition a sufficiently large set of numbers into two sets, the existence of arithmetic progressions of arbitrary length can also be proven.