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 (→‎Solution 3 (Construct digits of exemplar.))
 
(19 intermediate revisions by 3 users not shown)
Line 4: Line 4:
 
Prove that for every positive integer <math>n </math> there exists an <math>n </math>-digit number divisible by <math>5^n </math> all of whose digits are odd.
 
Prove that for every positive integer <math>n </math> there exists an <math>n </math>-digit number divisible by <math>5^n </math> all of whose digits are odd.
  
−
== Solution ==
+
==Solutions==
 +
=== Solution 1 ===
  
 
We proceed by induction.  For our base case, <math>n=1 </math>, we have the number 5.  Now, suppose that there exists some number <math>a \cdot 5^{n-1} </math> with <math>n-1 </math> digits, all of which are odd.  It is then sufficient to prove that there exists an odd digit <math>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>5^n </math>.  This is equivalent to proving that there exists an odd digit <math>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>k </math> exists and the induction is complete.
 
We proceed by induction.  For our base case, <math>n=1 </math>, we have the number 5.  Now, suppose that there exists some number <math>a \cdot 5^{n-1} </math> with <math>n-1 </math> digits, all of which are odd.  It is then sufficient to prove that there exists an odd digit <math>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>5^n </math>.  This is equivalent to proving that there exists an odd digit <math>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>k </math> exists and the induction is complete.
  
 +
=== Solution 2 ===
  
−
{{alternate solutions}}
+
First, we note that there are <math> 5^n</math> <math>n</math> digit numbers with only odd digits.  Now, we will prove that none of these numbers have the same residue mod <math> 5^n</math>, and therefore one of them must be 0 mod <math> 5^n</math>.
−
 
 
−
== Solution 2 ==
 
−
 
 
−
First, we note that there are <math> 5^n</math> n digit numbers with only odd digits.  Now, we will prove that none of these numbers have the same residue mod <math> 5^n</math>, and therefore one of them must be 0 mod <math> 5^n</math>.
 
  
  
Line 22: Line 20:
 
Lemma: Every multiple of <math> 5^n</math> with n digits or less has a 5 as one of its digits.   
 
Lemma: Every multiple of <math> 5^n</math> with n digits or less has a 5 as one of its digits.   
  
−
All numbers of type can be written as <math> k5^n</math>.  Then, let <math> k</math> have <math> x</math> factors of <math> 2</math> in it.  (<math> x<n</math>, or else our number would have more than n digits).  So, we have <math> k5^n=a2^x5^n=a*10^x*5^{n-x}</math> for some odd a.  Now <math> a*10^x*5^{n-x}</math> is an odd multiple of 5  (<math> a5^{n-x}</math>)  with x zeroes after it, and all multiples of 5 end in 5.  Therefore, <math> a*10^x*5^{n-x}</math> always contains a 5 as its <math> (x+1)^{st}</math> digit, and we have proven our lemma.   
+
All numbers of this type can be written as <math> k5^n</math>.  Then, let <math> k</math> have <math> x</math> factors of <math> 2</math> in it.  (<math> x<n</math>, or else our number would have more than n digits).  So, we have <math> k5^n=a2^x5^n=a*10^x*5^{n-x}</math> for some odd a.  Now <math> a*10^x*5^{n-x}</math> is an odd multiple of 5  (<math> a5^{n-x}</math>)  with x zeroes after it, and all multiples of 5 end in 5.  Therefore, <math> a*10^x*5^{n-x}</math> always contains a 5 as its <math> (x+1)^{st}</math> digit, and we have proven our lemma.   
  
 
By our lemma, our number with only the digits 0 through 4 cannot be a multiple of <math> 5^n</math>, and so we have reached a contradiction.  QED
 
By our lemma, our number with only the digits 0 through 4 cannot be a multiple of <math> 5^n</math>, 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.
+
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.
  
−
== Resources ==
+
=== Solution 3 (Construct digits of exemplar.) ===
 +
 
 +
<math>5^n \pmod {10} \equiv 5</math>.
 +
 
 +
<math>2^k 5^n \pmod {10^{k +1} } \equiv  10^k 5^{n-k} \equiv 5 \cdot 10^k</math>.
 +
 
 +
For any <math>n</math>, we can construct a <math>a = 5^n \cdot \sum_{0 \leq i < n}{2^{x_i}}</math>:
 +
 
 +
<math>x_0 = 1</math>
 +
 
 +
<math>a_i = 5^n \sum_{0 \leq j \leq i}{2^{x_j}}</math>
 +
 
 +
<math>x_{i} = \frac{a_{i-1}}{10^{i}} + 1 \pmod 2</math>. (This makes the <math>10^{i}</math> place of <math>a_{i}</math> odd, without changing the the smaller place digits).
 +
 
 +
<math>a = a_{n-1} = 5^n \cdot  \sum_{0 \leq j < n}{2^{x_j}}</math> ,  with digits in place <math>10^i</math> odd, for <math>0 \leq i<n</math>.
 +
 
 +
Since <math>\sum_{0 \leq j < n}{2^{x_j}}  < 2^n</math>,  <math>a < 5^n 2^n = 10^n</math>.
 +
 
 +
By construction, the digits in all the places up through  <math>10^{n-1}</math> are odd, and since <math>a<10^n</math>, there are no other digits.
 +
 
 +
In fact, if <math>A_m = a</math> that solves the case <math>n=m</math>,  then <math>A_{m+1} \mod 10^ m \equiv A_m</math>.
 +
 
 +
Note that in some cases (like <math>n=5</math>) , both of <math>x_{n-1} \in \{0,1\}</math> yield distinct numbers <math>a-5\cdot10^{n-1}</math> and <math>a</math> with all odd digits.
 +
<math>a-5\cdot10^{n-1}</math> has <math>n-1<n</math> digits, and so <math>x_{n-1}=1</math> is needed for padding.
 +
 
 +
----
 +
 
 +
{{alternate solutions}}
  
−
* [[2003 USAMO Problems]]
+
== See also ==
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=336189#p336189 Discussion on AoPS/MathLinks]
+
{{USAMO newbox|year=2003|before=First question|num-a=2}}
  
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 21:17, 3 March 2023

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 this 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.

Solution 3 (Construct digits of exemplar.)

$5^n \pmod {10} \equiv 5$.

$2^k 5^n \pmod {10^{k +1} } \equiv 10^k 5^{n-k} \equiv 5 \cdot 10^k$.

For any $n$, we can construct a $a = 5^n \cdot \sum_{0 \leq i < n}{2^{x_i}}$:

$x_0 = 1$

$a_i = 5^n \sum_{0 \leq j \leq i}{2^{x_j}}$

$x_{i} = \frac{a_{i-1}}{10^{i}} + 1 \pmod 2$. (This makes the $10^{i}$ place of $a_{i}$ odd, without changing the the smaller place digits).

$a = a_{n-1} = 5^n \cdot \sum_{0 \leq j < n}{2^{x_j}}$ , with digits in place $10^i$ odd, for $0 \leq i<n$.

Since $\sum_{0 \leq j < n}{2^{x_j}} < 2^n$, $a < 5^n 2^n = 10^n$.

By construction, the digits in all the places up through $10^{n-1}$ are odd, and since $a<10^n$, there are no other digits.

In fact, if $A_m = a$ that solves the case $n=m$, then $A_{m+1} \mod 10^ m \equiv A_m$.

Note that in some cases (like $n=5$) , both of $x_{n-1} \in \{0,1\}$ yield distinct numbers $a-5\cdot10^{n-1}$ and $a$ with all odd digits. $a-5\cdot10^{n-1}$ has $n-1<n$ digits, and so $x_{n-1}=1$ is needed for padding.

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

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