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.
 A: (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)$.
A: 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$.) 
