Any partition of $\{1,2,\ldots,9\}$ must contain a $3$-Term Arithmetic Progression

Question

Prove that for any way of dividing the set $X=\{1,2,3,\dots,9\}$ into $2$ sets, there always exist at least one arithmetic progression of length $3$ in one of the two sets.

Answer 1

This result is part of a nice area in Ramsey theory. If you want to study generalizations, the term you want to look for is Van der Waerden number; we are saying here that $w(2,3)\le 9$, where the $3$ indicates you want an arithmetic progression of length three, and the $2$ indicates that yo are splitting the set in two pieces. In fact, $w(2,3)=9$, meaning that, in addition, there is a way to split the numbers from $1$ to $8$ into two pieces, both avoiding such triples: $\{1,2,5,6\}$ and $\{3,4,7,8\}$.

To see that $9$ suffices, the easiest argument proceeds by an analysis of cases: Consider a splitting of $X$ into two sets, and let's attempt to see what restrictions these sets must satisfy in order to avoid arithmetic triples. We must conclude that it is impossible to have such a splitting. The key in my approach is to consider $4,5,6$. They cannot all be in the same piece, but two of them must be. Let's call that piece $A$, and let $B$ be the other one.

• Case 1. $4,6\in A$.

This is the easiest case to eliminate, since $2,5,8$ must then be an arithmetic triple in $B$: Consider, respectively, the triples $2,4,6$, and $4,5,6$, and $4,6,8$. If we place any of $2,5,8\in A$, one of these three arithmetic triples ends up in $A$.

• Case 2. $4,5\in A$.

Then $3,6\in B$ (consider, respectively, the triples $3,4,5$ and $4,5,6$), so $9\in A$ (consider $3,6,9$), but then $1,7\in B$ (consider $1,5,9$ and $5,7,9$), so $2,8\in A$ (consider $1,2,3$ and $6,7,8$). We now see this case cannot be either, because the triple $2,5,8$ is in $A$.

• Case 3. $5,6\in A$.

This is really the same as case 2, by symmetry. (In this case, $4,7\in B$, so $1\in A$, so $3,9\in B$, so $2,8\in A$, and we see that the triple $2,5,8$ is in $A$.)