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

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.

Solution 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$.)

Solution 2:

(This is very similar to Andres Caicedo's proof, but is a little simpler.)

Let us call the sets red and blue. Consider the elements $\{4,5,6\}$. At least two of these are the same color; say red. Then we have three cases: $\{4,5\}$ are red, $\{4,6\}$ are red, or $\{5,6\}$ are red. $\def\r#1{\color{red}{#1}}\def\b#1{\color{blue}{#1}}$

• $\r4$ and $\r5$ are both red. Then if $3$ or $6$ is red we are done, so suppose $\b3$ and $\b6$ are blue. Then $\r9$ is red (else $\b3,\b6,\r9$ is blue), so $\b1$ is blue (else $\b1,\r5,\r9$ is red), $\r2$ is red ($\b1,\r2,\b3$), $\b8$ is blue ($\r2,\r5,\b8$). Now if $7$ is red we have $\r5,\r7,\r9$ and if $7$ is blue we have $\b6,\b7,\b8$.

• $\r4$ and $\r6$ are both red. Then $\b2$ and $\b5$ are both blue (else $\b2,\r4,\r6$ or $\r4,\b5,\r6$). Now if $8$ is red we have red $\r4,\r6,\r8$ and if $8$ is blue we have blue $\b2,\b5,\b8$.

• $\r5$ and $\r6$ are both red. This reduces to the $\{4,5\}$ case by the transformation $x\mapsto (10-x)$.