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 Problems/Problem 2"

(Created page with "Let <math>a_1, a_2, \dots</math> be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer <math>n</math> the numbers...")
 
m (→‎Solution)
 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
==Problem==
 +
 
Let <math>a_1, a_2, \dots</math> be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer <math>n</math> the numbers <math>a_1, a_2, \dots, a_n</math> leave <math>n</math> different remainders upon division by <math>n</math>. Prove that every integer occurs exactly once in the sequence.
 
Let <math>a_1, a_2, \dots</math> be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer <math>n</math> the numbers <math>a_1, a_2, \dots, a_n</math> leave <math>n</math> different remainders upon division by <math>n</math>. Prove that every integer occurs exactly once in the sequence.
 +
 +
==Solution==
 +
<math>{a_n}</math> satisfies the conditions if and only if <math>{a_n-a_1}</math> does.
 +
Therefore we can assume that <math>a_1=0</math>
 +
 +
First of all, <math>|a_n|<n</math>
 +
Otherwise, <math>a_n = 0</math> mod <math>a_{a_n}</math>
 +
 +
 +
Claim: <math>a_{k+1}</math> is either the smallest positive number not in <math>{a_1, a_2, ..., a_k}</math> or the largest negative number not in this set.
 +
*Proof by induction: the induction hypothesis implies that <math>a_1, a_2, ..., a_k</math> are consecutive. Let m and M be the smallest and largest numbers in this consecutive set, respectively. It is clear that <math>a_{k+1}=m-1=M+1</math> mod <math>k+1</math>. But since <math>|a_n|<n</math>, <math>a_{k+1}=m-1</math> or <math>M+1</math>
 +
 +
 +
This proves that if <math>{a_n}</math> contains an infinite number of positive and negative numbers, it must contain each integer exactly once.
 +
 +
~Kscv
 +
 +
==See Also==
 +
 +
{{IMO box|year=2005|num-b=1|num-a=3}}

Latest revision as of 09:07, 19 November 2023

Problem

Let $a_1, a_2, \dots$ 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, \dots, a_n$ leave $n$ different remainders upon division by $n$. Prove that every integer occurs exactly once in the sequence.

Solution

${a_n}$ satisfies the conditions if and only if ${a_n-a_1}$ does. Therefore we can assume that $a_1=0$

First of all, $|a_n|<n$ Otherwise, $a_n = 0$ mod $a_{a_n}$


Claim: $a_{k+1}$ is either the smallest positive number not in ${a_1, a_2, ..., a_k}$ or the largest negative number not in this set.

  • Proof by induction: the induction hypothesis implies that $a_1, a_2, ..., a_k$ are consecutive. Let m and M be the smallest and largest numbers in this consecutive set, respectively. It is clear that $a_{k+1}=m-1=M+1$ mod $k+1$. But since $|a_n|<n$, $a_{k+1}=m-1$ or $M+1$


This proves that if ${a_n}$ contains an infinite number of positive and negative numbers, it must contain each integer exactly once.

~Kscv

See Also

2005 IMO (Problems) • Resources
Preceded by
Problem 1 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 3
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_IMO_Problems/Problem_2&oldid=204658"