Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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  
@LevanDokite, I understand but I can't prove it in any nice way. There is an admittedly ugly proof here cut-the-knot.org/Curriculum/Arithmetic/ArithmeticSequence.shtml –  sperners lemma Nov 18 '12 at 15:54
add comment

1 Answer

up vote 6 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.