All Those Digits. Topic: Number Theory. Level: Olympiad.

Problem: (2003 USAMO - #1) Prove that for every positive integer $n$ there exists an $n$-digit number divisible by $5^n$ all of whose digits are odd.

Solution: We will prove the result by induction.

Base Case: $n=1$ - $5$ works.

Suppose there exists a $k$-digit positive integer with all odd digits that is divisible by $5^k$. Call this integer $x$.

Consider the following numbers:

$1(10^k)+x, 3(10^k)+x, 5(10^k)+x, 7(10^k)+x, 9(10^k)+x$, all of which have $k+1$ digits.

Let $x = 5^ky$.

Then the above numbers become

$5^k(1(2^k)+y), 5^k(3(2^k)+y), 5^k(5(2^k)+y), 5^k(7(2^k)+y), 5^k(9(2^k)+y)$.

Notice that $1(2^k)+y, 3(2^k)+y, 5(2^k)+y, 7(2^k)+y, 9(2^k)+y$ are all different modulo $5$ (since they are in an arithmetic sequence with difference $2^{k+1}$ and $(2^{k+1},5) = 1$).

Therefore one of the numbers must be divisible by $5$. Let that one be $a$.

So one of the original numbers is $5^ka$, where $a$ is divisible by $5$. Hence the number is divisible by $5^{k+1}$ and has $k+1$ digits, as desired. This completes the induction. QED.

--------------------

Practice Problem: (1994 USAMO - #1) Let $ k_1 < k_2 < k_3 < \cdots$ , be positive integers, no two consecutive, and let $s_m = k_1 + k_2 + \cdots + k_m$ for $m = 1,2,3, \ldots $. Prove that, for each positive integer $n$, the interval $[s_n, s_{n+1}) $ contains at least one perfect square.