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 "2003 USAMO Problems/Problem 1"

 
m
Line 7: Line 7:
  
 
We proceed by induction.  For our base case, <math> \displaystyle n=1 </math>, we have the number 5.  Now, suppose that there exists some number <math> \displaystyle a \cdot 5^{n-1} </math> with <math> \displaystyle n-1 </math> digits, all of which are odd.  It is then sufficient to prove that there exists an odd digit <math> \displaystyle k </math> such that <math> k\cdot 10^{n-1} + a \cdot 5^{n-1} = 5^{n-1}(k \cdot 2^{n-1} + a) </math> is divisible by <math> \displaystyle 5^n </math>.  This is equivalent to proving that there exists an odd digit <math> \displaystyle k </math> such that <math> k \cdot 2^{n-1} + a </math> is divisible by 5, which is true when <math> k \equiv -3^{n-1}a \pmod{5} </math>.  Since there is an odd digit in each of the residue classes mod 5, <math> \displaystyle k </math> exists and the induction is complete.
 
We proceed by induction.  For our base case, <math> \displaystyle n=1 </math>, we have the number 5.  Now, suppose that there exists some number <math> \displaystyle a \cdot 5^{n-1} </math> with <math> \displaystyle n-1 </math> digits, all of which are odd.  It is then sufficient to prove that there exists an odd digit <math> \displaystyle k </math> such that <math> k\cdot 10^{n-1} + a \cdot 5^{n-1} = 5^{n-1}(k \cdot 2^{n-1} + a) </math> is divisible by <math> \displaystyle 5^n </math>.  This is equivalent to proving that there exists an odd digit <math> \displaystyle k </math> such that <math> k \cdot 2^{n-1} + a </math> is divisible by 5, which is true when <math> k \equiv -3^{n-1}a \pmod{5} </math>.  Since there is an odd digit in each of the residue classes mod 5, <math> \displaystyle k </math> exists and the induction is complete.
 +
 +
 +
{{alternate solutions}}
  
 
== Resources ==
 
== Resources ==

Revision as of 06:34, 22 April 2007

Problem

(Titu Andreescu) Prove that for every positive integer $\displaystyle n$ there exists an $\displaystyle n$-digit number divisible by $\displaystyle 5^n$ all of whose digits are odd.

Solution

We proceed by induction. For our base case, $\displaystyle n=1$, we have the number 5. Now, suppose that there exists some number $\displaystyle a \cdot 5^{n-1}$ with $\displaystyle n-1$ digits, all of which are odd. It is then sufficient to prove that there exists an odd digit $\displaystyle k$ such that $k\cdot 10^{n-1} + a \cdot 5^{n-1} = 5^{n-1}(k \cdot 2^{n-1} + a)$ is divisible by $\displaystyle 5^n$. This is equivalent to proving that there exists an odd digit $\displaystyle k$ such that $k \cdot 2^{n-1} + a$ is divisible by 5, which is true when $k \equiv -3^{n-1}a \pmod{5}$. Since there is an odd digit in each of the residue classes mod 5, $\displaystyle k$ exists and the induction is complete.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2003_USAMO_Problems/Problem_1&oldid=14674"