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.

I mostly just need someone to explain to me this problem:

Prove that it is possible to $2$-color the integers from $1$ to $1000$ so that no monochromatic arithmetic progression of length $17$ is formed.

For some reason when I think about this problem I just think of starting with coloring $1$ red then alternating until $1000$... There is obviously more to this problem, but I can't figure out what it is.

share|improve this question
3  
The problem asks you to find a coloring such that $a_1, a_2, \dots a_{17}$ never share a color, where $a_i = a_1 + (i-1)*d$. If you color even numbers blue and odd numbers red, then take $d=2$ to find a sequence of single color. –  Karolis Juodelė Mar 4 '13 at 6:42
    
What's the reasoning behind the formula? –  MITjanitor Mar 4 '13 at 6:49
    
by an arithmetic progression of 17, do you mean one with 17 terms or with common difference of 17? –  Vincent Tjeng Mar 4 '13 at 6:58
    
What I put above is all that I know for the question. I took it to be 17 consecutive terms. But I may not know what arithmetic progression means. –  MITjanitor Mar 4 '13 at 7:02
1  
The formula is what is meant by arithmetic progression. The problem is definitely talking about a progression of 17 terms, with any difference. Even if you've never heard of the length of a sequence, a hint to this is just how trivial the other interpretation would be. –  Karolis Juodelė Mar 4 '13 at 7:13

1 Answer 1

up vote 1 down vote accepted

As has been clarified in the comments, by an arithmetic progression of length $17$ they mean an arithmetic progression with $17$ terms, i.e. a progression of $17$ integers given by $a_i=a_1+(i-1)d$ for some integers $a_1$ and $d$, for instance $4,9,14,\dotsc,74,79,84$ for $a_1=4$ and $d=5$.

The claim can be proved using the probabilistic method by showing that the expected number of monochromatic arithmetic progressions of length $17$ upon independently colouring each integer with either colour with equal probability is less than $1$.

share|improve this answer

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.