USA IMO 2003

We proceed by induction. The property is clearly true for $n=1$. Assume that $N=a_1{a}_2\dots a_n$ is divisible by $5^n$ and has only odd digits. Consider the numbers $$N_1=1a_1{a}_2\dots a_n=1\cdot 10^n+5^{n}M=5^n(1\cdot 2^n+M),$$ $$N_2=3a_1{a}_2\dots a_n=3\cdot 10^n+5^{n}M=5^n(3\cdot 2^n+M),$$ $$N_3=5a_1{a}_2\dots a_n=5\cdot 10^n+5^{n}M=5^n(5\cdot 2^n+M),$$ $$N_4=7a_1{a}_2\dots a_n=7\cdot 10^n+5^{n}M=5^n(7\cdot 2^n+M),$$ $$N_5=9a_1{a}_2\dots a_n=9\cdot 10^n+5^{n}M=5^n(9\cdot 2^n+M).$$ The numbers $1\cdot 2^n+M,3\cdot 2^n+M,5\cdot 2^n+M,7\cdot 2^n+M,9\cdot 2^n+M$ give distinct remainders when divided by $5$. Otherwise the difference of some two of them would be a multiple of $5$, which is impossible, because neither $2^n$ is a multiple of $5$, nor is the difference of any two of the numbers $1,3,5,7,9$. It follows that one of the numbers $N_1,N_2,N_3,N_4,N_5$ is divisible by $5^n\cdot 5$, and the induction is complete.

---

Alternative solution.

For an $m$ digit number $a$, where $m\ge n$, let $\ell (a)$ denote the $m-n$ leftmost digits of $a$. (That is, we consider $\ell (a)$ as an $(m-n)$-digit number.) It is clear that we can choose a large odd number $k$ such that $a_0=5^n\cdot k$ has at least $n$ digits. Assume that $a_0$ has $m_0$ digits, where $m_0\ge n$. Note that the $a_0$ is an odd multiple of $5$. Hence the unit digit of $a_0$ is $5$.

If the $n$ rightmost digits of $a_0$ are all odd, then the number $b_0=a_0-\ell (a_0)\cdot 10^n$ satisfies the conditions of the problem, because $b_0$ has only odd digits (the same as those $n$ leftmost digits of $a_0$) and that $b_0$ is the difference of two multiples of $5^n$.

If there is an even digit among the $n$ rightmost digits of $a_0$, assume that $i_1$ is the smallest positive integer such that the $i_1$th rightmost digit of $a_0$ is even. Then number $a_1=a_0+5^n\cdot 10^{i_1-1}$ is a multiple of $5^n$ with at least $n$ digits. The $(i-1)$th rightmost digit is the same as that of $a_0$ and the $i_1$th rightmost digit of $a_1$ is odd. If the $n$ rightmost digits of $a_1$ are all odd, then $b_1=a_1-\ell (a_1)\cdot 10^n$ satisfies the conditions of the problem. If there is an even digit among the $n$ rightmost digits of $a_1$, assume that $i_2$ is the smallest positive integer such that the $i_2$th rightmost digit of $a_1$ is even. Then $i_2>i_1$. Set $a_2=a_1+5^n\cdot 10^{i_2-1}$. We can repeat the above process of checking the rightmost digits of $a_2$ and eliminate the rightmost even digits of $a_2$, if there is such a digit among the $n$ rightmost digits of $a_2$. This process can be repeated for at most $n-1$ times because the unit digit of $a_0$ is $5$. Thus, we can obtain a number $a_k$, for some nonnegative integer $k$, such that $a_k$ is a multiple of $5^n$ with its $n$ rightmost digits all odd. Then $b_k=a_k-\ell (a_k)\cdot 10^n$ is a number that satisfies the conditions of the problem.

---

Alternative solution.

Consider all the nonnegative multiples of $5^n$ that have no more than $n$ digits. There are $2^n$ such multiples, namely, $m_0=0,m_1=5^n,m_2=2\cdot 5^n,\dots ,m_{2^{n-1}}=(2^n-1)5^n$. For each $m_i$, we define an $n$-digit binary string $s(m_i)$. If $m_i$ is a $k_i$-digit number, the leftmost $n-k_i$ digits of $s(m_i)$ are all $0$'s, and the $j$th digit, $1\le j\le k_i$, of $s(m_i)$ is $1$ (or $0$) if the $j$th rightmost digit of $m_i$ is odd (or even). (For example, for $n=4$, $m_0=0,m_1=625,m_2=1250$, and $s(m_0)=s(m_1)=s(m_2)=1010$.) There are $2^n$ $n$-digit binary strings. It suffices to show that $s$ is one-to-one, that is, $s(m_i)\ne s(m_j)$ for $i\ne j$. Because then there must be a $m_i$ with $s(m_i)$ being a string of $n$ $1$'s, that is, $m_i$ has $n$ digits and all of them are odd.

We write $m_i$ and $m_j$ in binary system. Then there is a smallest positive integer $k$ such that the $k$th rightmost digit in the binary representations of $m_i$ and $m_j$ are different. Without loss of generality, we assume that those $k$th digits for $m_i$ and $m_j$ are $1$ and $0$, respectively. Then $m_i=s_i+2^k+t$ and $m_j=s_j+t$, where $s_i,s_j,t$ are positive integers such that $2^{k+1}$ divides both $s_i$ and $s_j$ and that $0\le t\le 2^k-1$. Note that adding $2^k\cdot 5^n$ to $t\cdot 5^n$ will change the parity of the $(k+1)$th rightmost digit of $t\cdot 5^n$ while not affect the $k$ rightmost digits of $t\cdot 5^n$. Note also that adding $s_i\cdot 5^n$ (or $s_j\cdot 5^n$) to $(2^k+t)\cdot 5^n$ (or $t\cdot 5^n$) will not affect the last $k+1$ digits of $(2^k+t)\cdot 5^n$ (or $t\cdot 5^n$). Hence the $(k+1)$th rightmost digits in the decimal representations of $m_i\cdot 5^n$ and $m_j\cdot 5^n$ have different parities. Thus $s(m_i)\ne s(m_j)$, as desired.