Difference between revisions of "2005 IMO Shortlist Problems/N2"
(Created page with "== Problem == Let <math>a_1,a_2,\ldots</math> be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer <math>n</math> t...") |
(No difference)
|
Revision as of 10:41, 1 September 2012
Problem
Let be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer the numbers leave different remainders upon division by .
Prove that every integer occurs exactly once in the sequence .
Solution
It is clear that if and only if , or the sequence would not satisfy the specified property.
If , then and leave the same remainder when divided by . It then follows that for all positive integers and . Now consider , and let this be , with . It follows that are all in the closed interval , and hence is a permutation of consecutive numbers, for all .
Note that there are infinitely many positive and negative terms. Therefore for any arbitrarily large integer there exists an such that and a such that . Since is a permutation of consecutive integers, it follows that every integer in the range is in the sequence, and consequently every integer occurs in the sequence.