Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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...")
 
(→‎Solution)
Line 7: Line 7:
 
It is clear that <math>a_i=a_j</math> if and only if <math>i=j</math>, or the sequence would not satisfy the specified property.
 
It is clear that <math>a_i=a_j</math> if and only if <math>i=j</math>, or the sequence would not satisfy the specified property.
  
−
If <math>|a_i-a_j|\geq \max(i,j)</math>, then <math>a_i</math> and <math>a_j</math> leave the same remainder when divided by <math>\max(i,j)</math>. It then follows that <math>|a_i-a_j|<\max(i,j)</math> for all positive integers <math>i</math> and <math>j</math>. Now consider <math>\min(a_1,a_2,\ldots,a_n)</math>, and let this be <math>a_k</math>, with <math>k\in [1,n]</math>. It follows that <math>a_1,a_2,\ldots a_{n}</math> are all in the closed interval <math>[a_k,a_k+n-1]</math>, and hence <math>a_1,a_2,\ldots a_n</math> is a permutation of <math>n</math> consecutive numbers, for all <math>n</math>.
+
If <math>|a_i-a_j|\geq \max(i,j)</math>, then <math>a_i</math> and <math>a_j</math> leave the same remainder when divided by <math>|a_i-a_j|</math>, which violates the given condition for the sequence. It then follows that <math>|a_i-a_j|<\max(i,j)</math> for all positive integers <math>i</math> and <math>j</math>. Now consider <math>\min(a_1,a_2,\ldots,a_n)</math>, and let this be <math>a_k</math>, with <math>k\in [1,n]</math>. It follows that <math>a_1,a_2,\ldots a_{n}</math> are all in the closed interval <math>[a_k,a_k+n-1]</math>, and hence <math>a_1,a_2,\ldots a_n</math> is a permutation of <math>n</math> consecutive numbers, for all <math>n</math>.
  
−
Note that there are infinitely many positive and negative terms. Therefore for any arbitrarily large integer <math>\Delta</math> there exists an <math>i</math> such that <math>a_i\geq \Delta</math> and a <math>j</math> such that <math>a_j\leq -\Delta</math>. Since <math>a_1,a_2,\ldots, a_n</math> is a permutation of <math>n</math> consecutive integers, it follows that every integer in the range <math>[-\Delta,\Delta]</math> is in the sequence, and consequently every integer occurs in the sequence.  
+
Note that there are infinitely many positive and negative terms. Therefore for any arbitrarily large integer <math>\Delta</math> there exists an <math>i</math> such that <math>a_i\geq \Delta</math> and a <math>j</math> such that <math>a_j\leq -\Delta</math>. Since <math>a_1,a_2,\ldots, a_n</math> is a permutation of <math>n</math> consecutive integers, it follows that every integer in the range <math>[-\Delta,\Delta]</math> is in the sequence, and consequently every integer occurs in the sequence.
  
 
== See Also ==
 
== See Also ==

Revision as of 10:43, 1 September 2012

Problem

Let $a_1,a_2,\ldots$ be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer $n$ the numbers $a_1,a_2,\ldots,a_n$ leave $n$ different remainders upon division by $n$.

Prove that every integer occurs exactly once in the sequence $a_1,a_2,\ldots$.

Solution

It is clear that $a_i=a_j$ if and only if $i=j$, or the sequence would not satisfy the specified property.

If $|a_i-a_j|\geq \max(i,j)$, then $a_i$ and $a_j$ leave the same remainder when divided by $|a_i-a_j|$, which violates the given condition for the sequence. It then follows that $|a_i-a_j|<\max(i,j)$ for all positive integers $i$ and $j$. Now consider $\min(a_1,a_2,\ldots,a_n)$, and let this be $a_k$, with $k\in [1,n]$. It follows that $a_1,a_2,\ldots a_{n}$ are all in the closed interval $[a_k,a_k+n-1]$, and hence $a_1,a_2,\ldots a_n$ is a permutation of $n$ consecutive numbers, for all $n$.

Note that there are infinitely many positive and negative terms. Therefore for any arbitrarily large integer $\Delta$ there exists an $i$ such that $a_i\geq \Delta$ and a $j$ such that $a_j\leq -\Delta$. Since $a_1,a_2,\ldots, a_n$ is a permutation of $n$ consecutive integers, it follows that every integer in the range $[-\Delta,\Delta]$ is in the sequence, and consequently every integer occurs in the sequence.

See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_IMO_Shortlist_Problems/N2&oldid=48171"