Difference between revisions of "2003 USAMO Problems/Problem 1"

Revision as of 10:36, 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 5 \cdot 10^k$ .

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

$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 \mod 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.

Note that in some cases (like $n=5$ ) , both of $x_{n-1} \in {0,1}$ yield distinct exemplars $a$ and $a-5\cdot10^{n-1}$ and $a$ . This happens when $10^{n-2} <= a_{n-2} < 10^{n-1}$ , in which case the construction "sees" an even 0 the $10^{n-1}$ place of $a_{n-2}$ , and so adds $5 \cdot 10^{n-1}$ . In this case, since that is the leading digit, 0 is ignored by the problem objective, and adding the final $5 \cdot 10^{n-1}$ is optional.

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

@@ Line 20: / Line 20: @@
 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
 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.) ===

2003 USAMO (Problems • Resources)
Preceded by First question	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search