Progetto Olimpiadi di Matematica - GARA di SECONDO LIVELLO

Solution:

The number of positive integers $n$ with properties (a) and (b) is $3^{k-1}$.

To prove this, consider the integer $\frac{n}{5}$ and let $a_{0}, a_{1}, \ldots, a_{k-1}$ be its digits, that is
$$\frac{n}{5}=a_{k-1} 10^{k-1}+\ldots+a_{1} 10+a_{0}$$
By (b) the digits $a_{i}$ are all odd, that is $a_{i} \in\{1,3,5,7,9\}$ for every $i=0,1, \ldots, k-1$.
Since $n$ in base 10 has exactly $k$ digits, we deduce that $a_{k-1}=1$, because otherwise, if $a_{k-1}>1$, we would have
$$n=5 \cdot \frac{n}{5} \geq 5 \cdot a_{k-1} 10^{k-1} \geq 10^{k}$$
that is, $n$ would have at least $k+1$ digits.

Moreover, observe that for every integer $a$ we have $5 a=\frac{a-1}{2} 10+5$, so in our case, recalling that $a_{k-1}=1$, it holds that
$$\begin{aligned} & n=5 \cdot \frac{n}{5}=5\left(a_{k-1} 10^{k-1}+\cdots+a_{1} 10+a_{0}\right)=5 a_{k-1} 10^{k-1}+5 a_{k-2} 10^{k-2} \cdots+5 a_{1} 10+a_{0}= \\ & 5 \cdot 10^{k-1}+\left(\frac{a_{k-2}-1}{2} 10+5\right) 10^{k-2}+\cdots+\left(\frac{a_{1}-1}{2} 10+5\right) 10+\frac{a_{0}-1}{2} 10+5= \\ & 5 \cdot 10^{k-1}+\frac{a_{k-2}-1}{2} 10^{k-1}+5 \cdot 10^{k-2}+\cdots+\frac{a_{1}-1}{2} 10^{2}+5 \cdot 10+\frac{a_{0}-1}{2} 10+5= \\ & \left(5+\frac{a_{k-2}-1}{2}\right) 10^{k-1}+\left(5+\frac{a_{k-3}-1}{2}\right) 10^{k-2}+\cdots+\left(5+\frac{a_{1}-1}{2}\right) 10^{2}+\left(5+\frac{a_{0}-1}{2}\right) 10+5 \end{aligned}$$
What is written above, since the $a_{i}$ are odd digits, is the decimal representation of $n$, because
$0 \leq 5+\frac{a_{i}-1}{2} \leq 9$ and $\frac{a_{i}-1}{2}$ is an integer for every $i=0, \ldots, k-2$.

Since by (a) $n$ has $k$ odd digits, we deduce that $5+\frac{a_{i-1}-1}{2}$ must be odd for $i=1, \ldots, k-1$, that is, $a_{i}$ can only take the values $1,5$ and $9$.

There are thus at most three ways to choose $a_{i}, i=0, \ldots, k-2$, while $a_{k-1}=1$, that is, there are at most $3^{k-1}$ candidates for $\frac{n}{5}$ and hence for $n$.

The explicit formula (1) also shows that every such choice gives a number $n$ satisfying (a) and (b).
It thus remains proven that such numbers are exactly $3^{k-1}$.

Solution:

Let us first note that, for a fixed natural number $k$ greater than $0$, the positive integers satisfying properties (a) and (b) are as many as the positive integers with $k$ digits all odd whose multiplication by $5$ is still of $k$ odd digits, since multiplication by $5$ is an injective function.

Let $a_{1} a_{2} \ldots a_{k}$ be the base ten representation of an integer with all odd digits whose multiplication by $5$ is still of $k$ odd digits. Each multiplication $a_{i} \cdot 5$ has $5$ as its units digit.

The digit $a_{1}$ is $1$, since $3 \cdot 5=15$ already produces a unit of the next power of ten, hence the product by $5$ would have $n+1$ digits.

For $i=2, \ldots, n$ the tens digit of $a_{i} \cdot 5$ must be even because it must give an odd digit when added to the $5$ units of the number $a_{i-1} \cdot 5$: hence $a_{i}$ is $1,5$, or $9$ for $i=2, \ldots, n$.

For $k>0$ natural, the number of positive integers satisfying properties (a) and (b) is $3^{k-1}$.