$1996$ Austrian-Polish Number theory problem 
Let $k \ge 1$ be a positive integer. Prove that there exist exactly $3^{k-1}$ natural numbers $n$ with the following properties:

(i) $n$ has exactly $k$ digits (in decimal representation),
(ii) all the digits of $n$ are odd,
(iii) $n$ is divisible by $5$,
(iv) the number $m = n/5$ has $k$ odd digits
My work -
Let $n=10^{k-1}a_1+10^{k-2}a_2+...+a_k$
Now because all digits of n are odd and $5 | n$ we have $a_k =5$.
Now $m=n/5=2(10^{k-2}a_1+10^{k-3}a_2+...+a_{k-1})+1$
For $k=2$ I found that $n=55,75,95$ but not able to prove in general...
Hint says that all digit of m must be $1,5$, or $9$ and so there are $3^{k-1}$ choices for m hence n
but I am not able to understand why all digit of m must be 1,5, or 9 ???
Thankyou
 A: As you found out yourself (with the exception of the $+1$ mentioned by user3052655, coming from dividing $a_k=5$ by $5$), we have
$$\begin{eqnarray}
m=n/5 & = & 2(10^{k-2}a_1+10^{k-3}a_2+...+a_{k-1})+1 = \\
      & =  & 10^{k-2}(2a_1)+10^{k-3}(2a_2)+\ldots+10^1(2a_{k-2})+(2a_{k-1}+1).
\end{eqnarray}$$
If you look at the last line, this looks suspiciously like the decimal representation of a number with $k-1$ digits, all but the last of which are even, which is not what we want, so how can this become a $k$ digit number with all odd digits? The answer is the carry, of course. If any $2a_i$ value is $10$ or greater, the decimal digit will be $2a_i-10$ and the next higher digit gets a carry.
Since the carries start from the lowest value digits, let's start with the $1$-digit, $2a_{k-1}+1$, it's odd, so at the moment there is no further condition on $a_{k-1}$ (in addition to being odd, as $a_{k-1}$ is a digit of $n$ which has only odd digits).
Now let's look at the $10$-digit, $2a_{k-2}$. It's even, and even if it was $\ge 10$, $2a_{k-2}-10$ is again an even digit. The only way to make it an odd digit is if there is carry from the $1$-digit. So now we need that $2a_{k-1}+1 \ge 10$, that leaves us with exactly 3 options: $a_{k-1}=5,7$ or $9$.
So now that we have the carry from the $1$-digit, the $10$-digit is actually $2a_{k-2}+1$ (if there is no carry from this digit) or $2a_{k-2}-9$ (if there is a carry from this digit), both of which are odd, so that's what we want.
From now on, this argument continues throughout all the digits. Each time for a digit of $m$ ($2a_i$) to become odd , there must be a carry from the next lower value digit ($2a_{i+1}+1$, after applying the carry from the digit before), which can only happen if $a_{i+1}$ is $5,7$ or $9$. This continues until we find that $a_2$ must be $5,7$ or $9$.
This makes $2a_1+1$ odd, even if $a_1=1$ or $3$. But in those cases, the resulting number has only $k-1$ digits, which contradicts condition (iv) of the problem. So we need again $a_1$ must be at least $5$, such that $2a_1+1$ is at least $10$ and $2a_1+1$ produces a carry so that there is actually a $k$-th digit ($1$) for $10^{k-1}$.
If you look back, we found that $a_k$ must be $5$, while for $i=1,2,\ldots,k-1$ we have $a_i=5,7$ or $9$. This means those are exactly $3^{k-1}$ numbers, and I leave to you to check that they are actually solutions (which isn't hard, consodering the necessary conditions for producing a carry are also sufficient).
A: The digits $3$ and $7$ are forbidden because they give an odd carry ($15$ and $35$) which leads to an even digit or to one digit more , if the first digit is $3$ or $7$.
Moreover, the first digit must be $1$, the others can be $1,5,9$. All such numbers give a valid $m$, hence $3^{k-1}$ is the number of possibilities.
