Call a positive integer totally odd if all of its decimal digits are odd.
Show that for any positive integer k there is a k-digit totally odd integer which is a multiple of 5k.
*** Adapted from a problem which appeared at the USA Mathematical Olympiad in 2003.
This is basically an induction problem. The base case is k=1, for which the corresponding 1-digit totally odd integer is 5.
Now to the inductive part. Assume we have the solution for a given k, call that number N. Then the task is to show that there is a solution for k+1.
N mod 5^k is known to be 0. Then N mod 5^(k+1) is one of the five residues 0, 5^k, 2*5^k, 3*5^k, or 4*5^k.
Appending a digit to the front is equivalent to adding one of 10^k, 3*10^k, 5*10^k, 7*10^k, or 9*10^k. These numbers mod 5^(k+1) also form the set of residues 0, 5^k, 2*5^k, 3*5^k, or 4*5^k.
Then the solution is to choose the new digit with the complementary residue to the k-digit number.
Example: k=2, N=75.
75 mod 5^3 = 3*5^2 and 3*10^2 = 2*5^2. These are complementary residues, so the answer for k=3 is N=375.
Solution
