Difference between revisions of "2003 USAMO Problems/Problem 1"
m (→Solution 3 (Construct digits of exemplar.)) |
m (→Solution 3 (Construct digits of exemplar.)) |
||
Line 48: | Line 48: | ||
− | Note that in some cases (like <math>n=5</math>) , both of <math>x_{n-1} \in {0,1}</math> yield distinct exemplars <math>a</math> and <math>a-5\cdot10^{n-1}</math> and <math>a</math>. This happens when <math>10^{n-2} <= a_{n-2} < 10^{n-1}</math>, in which case the construction "sees" an even 0 the <math>10^{k-1}</math> place of <math>a_{n-2}. In this case, since that is the leading digit, 0 is ignored by the problem objective, and adding the final < | + | Note that in some cases (like <math>n=5</math>) , both of <math>x_{n-1} \in {0,1}</math> yield distinct exemplars <math>a</math> and <math>a-5\cdot10^{n-1}</math> and <math>a</math>. This happens when <math>10^{n-2} <= a_{n-2} < 10^{n-1}</math>, in which case the construction "sees" an even 0 the <math>10^{k-1}</math> place of <math>a_{n-2}</math>. In this case, since that is the leading digit, 0 is ignored by the problem objective, and adding the final <math>5 \cdot 10^{n-1}</math> is optional. |
---- | ---- |
Revision as of 11:24, 3 March 2023
Contents
Problem
(Titu Andreescu)
Prove that for every positive integer there exists an
-digit number divisible by
all of whose digits are odd.
Solutions
Solution 1
We proceed by induction. For our base case, , we have the number 5. Now, suppose that there exists some number
with
digits, all of which are odd. It is then sufficient to prove that there exists an odd digit
such that
is divisible by
. This is equivalent to proving that there exists an odd digit
such that
is divisible by 5, which is true when
. Since there is an odd digit in each of the residue classes mod 5,
exists and the induction is complete.
Solution 2
First, we note that there are
digit numbers with only odd digits. Now, we will prove that none of these numbers have the same residue mod
, and therefore one of them must be 0 mod
.
Proof by contradiction:
Assume we have two distinct numbers and
with only odd digits that leave the same residue mod
. Then, subtracting the larger from the smaller would yield a new number that is a multiple of
and has only even digits. We could then halve all of the digits in that number to get a second multiple of
with at most n digits that only uses the digits 0 through 4.
Lemma: Every multiple of with n digits or less has a 5 as one of its digits.
All numbers of type can be written as . Then, let
have
factors of
in it. (
, or else our number would have more than n digits). So, we have
for some odd a. Now
is an odd multiple of 5 (
) with x zeroes after it, and all multiples of 5 end in 5. Therefore,
always contains a 5 as its
digit, and we have proven our lemma.
By our lemma, our number with only the digits 0 through 4 cannot be a multiple of , 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.)
.
.
For any , we can construct a number
as follows:
(this makes the
place of
odd, without changing the the smaller place digits).
, with digits in place
odd, for
.
Since ,
.
By construction, the digits in all the places up through are odd, and since
, there are no other digits.
Note that in some cases (like ) , both of
yield distinct exemplars
and
and
. This happens when
, in which case the construction "sees" an even 0 the
place of
. In this case, since that is the leading digit, 0 is ignored by the problem objective, and adding the final
is optional.
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.