Home > Algebra, IMO, Number theory, Olympiad, Problem Solving > Sufficient condition for a sequence to be an enumeration of integers

Sufficient condition for a sequence to be an enumeration of integers


Let a_1,a_2,... be a sequence if integers with infinitely many positive and negative terms. Suppose that for any n the numbers a_1,a_2,...,a_n have n different remainders modulo n. Prove that each integer occurs exactly once in the given sequence.
IMO 2005 Problem 2

Consider S_n=\{a_1,..,a_n\}. Suppose that |a_i-a_j|=d \geq n for some i,j. Then a_i \equiv a_j \mod d in S_d; Contradiction. Therefore |a_i-a_j|<n for every i,j \leq n.

Consider the greatest element of S_n. Then, since a_i are distinct, it follows that S_n must be a list of consecutive integers.

Since the initial sequence contains infinitely many positive and negative integers it follows that (a_n) is an enumeration of the integers.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: