2003 USAMO Problems/Problem 1
(Titu Andreescu) Prove that for every positive integer there exists an -digit number divisible by all of whose digits are odd.
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.
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 this 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 :
. (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.
In fact, if that solves the case , then .
Note that in some cases (like ) , both of yield distinct numbers and with all odd digits. has digits, and so 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.
|2003 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|