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.

Given three infinite arithmetic progressions of natural numbers such that each of the numbers 1,2,3,4,5,6,7 and 8 belongs to at least one of them, prove that the number 1980 also belongs to at least one of them.

I may begin saying that 2,3,4 belong to the 3 progressions indivudually.

edit: my working for above statement

let a1,a2,a3 be the 3 progressions now if a) all 3 belong to only one of them, then 1980 obviously exists in it b) if only two of 2,3,4 belong to one of them then also it becomes a series with common difference given so which means 1980 belongs to one of them

so without loss of generality, i can safely assume 2,3,4 to belong to each one of them indivudually i.e 2 to a1, 3 to a2 and 4 to a3. now how to proceed?

well i got this far due to a clue that was associated with the question.

share|improve this question
    
I see what you mean, but can you include a reasoning for this claim. In general, it is a nice idea to show your work so that others can see where you are stuck. (Also, please avoid posting questions in the imperative mode.) –  Srivatsan Sep 3 '11 at 14:08

2 Answers 2

So: we may assume no progression has difference 1. You show that 2,3,4 belong to three different progressions. Similarly 6,7,8 belong to three different progressions. How do these match up? (Each of 2,3,4 matches one of 6,7,8.) If 4,8 are in the same progression, then 1980 is also in it, so assume not. If 4,6 are in the same progression, then 1980 is also in it, so assume not. Therefore 4,7 are in the same progression. This has difference 3 (since we assume no progression has difference 1). Next: if 3,6 are in the same progression, then 1980 is also in it, so assume not. Therefore 3,8 are in the same progression. This has difference 5. But now 5 and 6 are both missing from these two progressions, so they are both in the third progression, impossible.

share|improve this answer

If any three consecutive numbers belong to the same progression, then all numbers do. If two progressions have difference 2, or three progressions have difference 3, again they cover all numbers. If two progressions have difference 3, there remain at least two numbers between 1 and 8 with difference 3, so the third progression would also have to have difference 3. It follows that in any counterexample at most one progression can have difference 2 and at most one can have difference 3.

Now if no progression has difference 2, then the at most one progression with difference 3 covers at most 3 of the 8 numbers, and the two progressions with higher differences both cover at most 2 of the 8 numbers, for a sum of 7; it follows that there has to be a progression with difference 2. That leaves four numbers with even differences to be covered, and the only ways to cover them using two progressions are with two progressions with difference 4 or with one progression with difference 2.

Thus, in every possible case, the three progressions cover all integers, and hence also 1980.

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.