# 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.

-
What have you tried? Perhaps you could expand your post, because I think I know what you mean, but can't be sure. – Mark Bennet Nov 18 '12 at 14:49
What?? After "which" I got lost... – DonAntonio Nov 18 '12 at 14:49
I cannot believe that the "dirichlet series" tag is appropriate for this, but until the question is clarified it is a lottery to chose a better one. But if this is homework, that should be added. – Mark Bennet Nov 18 '12 at 14:55

1
anyone understand me? arithmetic which has length 3 is in one of 2 sets that means the arithmetic $<a;a+d;a+2d$ – LevanDokite Nov 18 '12 at 15:01

1
– sperners lemma Nov 18 '12 at 15:54

## 1 Answer

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

-
do you know an argument that isn't case analysis? – sperners lemma Nov 18 '12 at 16:41

1
I wanted to say that case 3 should be the same as case 1 by symmetry, and eventually realized that $[1\ldots 9]$ is not symmetric about $[3,4,5]$. I wonder if an argument similar to this one, but using $[4,5,6]$ instead of $[3,4,5]$, would be simpler. – MJD Nov 18 '12 at 16:45

2
I doubt there is one. "Softer" arguments that avoid case analysis do not tend to give precise bounds. The nice argument in "Ramsey theory" by Graham-Rotschild-Spencer, for example, gives $325$ as an upper bound. (The argument there is fairly intuitive, and one sees immediately how to generalize. But it is of course terrible for concrete bounds.) – Andres Caicedo Nov 18 '12 at 16:46
@MJD You are right. Using $4,5,6$ gives us a bit more symmetry, so case 3 would just be the "reflection" of case 1. I should have used that triple. Thanks! – Andres Caicedo Nov 18 '12 at 16:48
I didn't think it through myself, so I don't know whether it happens to complicate the other two cases enough that the gain from the symmetry is not actually a win. – MJD Nov 18 '12 at 16:49
show 1 more comment
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 54, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9407308101654053, "perplexity_flag": "head"}