2003 USAMO Problems/Problem 1

Revision as of 05:56, 22 April 2007 by Boy Soprano II (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

(Titu Andreescu) Prove that for every positive integer $\displaystyle n$ there exists an $\displaystyle n$-digit number divisible by $\displaystyle 5^n$ all of whose digits are odd.

Solution

We proceed by induction. For our base case, $\displaystyle n=1$, we have the number 5. Now, suppose that there exists some number $\displaystyle a \cdot 5^{n-1}$ with $\displaystyle n-1$ digits, all of which are odd. It is then sufficient to prove that there exists an odd digit $\displaystyle 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 $\displaystyle 5^n$. This is equivalent to proving that there exists an odd digit $\displaystyle 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, $\displaystyle k$ exists and the induction is complete.

Resources