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

2003 USAMO Problems/Problem 1

Revision as of 20:51, 6 April 2013 by Yrushi (talk | contribs)

Problem

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

Solutions

Solution 1

We proceed by induction. For our base case, $n=1$, we have the number 5. Now, suppose that there exists some number $a \cdot 5^{n-1}$ with $n-1$ digits, all of which are odd. It is then sufficient to prove that there exists an odd digit $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 $5^n$. This is equivalent to proving that there exists an odd digit $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, $k$ exists and the induction is complete.

Solution 2

First, we note that there are $5^n$ n digit numbers with only odd digits. Now, we will prove that none of these numbers have the same residue mod $5^n$, and therefore one of them must be 0 mod $5^n$.


Proof by contradiction: Assume we have two distinct numbers $A_1A_2A_3...A_n$ and $B_1B_2B_3...B_n$ with only odd digits that leave the same residue mod $5^n$. Then, subtracting the larger from the smaller would yield a new number that is a multiple of $5^n$ and has only even digits. We could then halve all of the digits in that number to get a second multiple of $5^n$ with at most n digits that only uses the digits 0 through 4.


Lemma: Every multiple of $5^n$ with n digits or less has a 5 as one of its digits.

All numbers of type can be written as $k5^n$. Then, let $k$ have $x$ factors of $2$ in it. ($x<n$, or else our number would have more than n digits). So, we have $k5^n=a2^x5^n=a*10^x*5^{n-x}$ for some odd a. Now $a*10^x*5^{n-x}$ is an odd multiple of 5 ($a5^{n-x}$) with x zeroes after it, and all multiples of 5 end in 5. Therefore, $a*10^x*5^{n-x}$ always contains a 5 as its $(x+1)^{st}$ digit, and we have proven our lemma.

By our lemma, our number with only the digits 0 through 4 cannot be a multiple of $5^n$, and so we have reached a contradiction. QED

Note: Not only does this prove the desired claim that there exists such a number, but it also proves that there is exactly one such number.

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

See also

2003 USAMO (Problems • Resources)
Preceded by
First question 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2003_USAMO_Problems/Problem_1&oldid=52248"