When replying to the problem, I ask that you make posts for solutions and submit comments, jokes, smilies, etc. separately. Please use LaTeX for posting solutions. Thanks.

Don't post in solved problems, please. This (and all the others) should go in the proposed problems section. Ooh and this was the very first problem I solved on an official olympiad ... yay .

It follows by induction on $n$; clearly for $n = 1$, $5$ satisfies the given conditions. Suppose the proposition works for $n$, i.e. there exists some number $N$ satisfying the giving conditions. Consider the five numbers $i*10^n + N$, where $i = 1, 3, 5, 7, 9$. It is clear that these five numbers all have $n+1$ digits with all digits odd, from the inductive hypothesis. Also from the inductive hypothesis, they are all divisible by $5^n$. If one were to divide them by $5^n$ however, they would differ by $2^n$ between consecutive numbers, i.e. they would all have different residues mod $5$. Thus one exists whose residue mod $5$ is $0$, or in other words, the original number was divisible by $5^{n+1}$ and thus satisfies the conditions for $n+1$.

Who can show that the first digit number of the k-digit number can be never equal to 1 ? Davron

It is easy to construct this number by induktion. $k_0=1, N_0=k_0*5^n=a_{n-1,0}a_{n-2,0}\dots a_{0,0}, a_{0,0}=5 \ is \ odd.$ Let we have $k_l<2^{m_l+1},k_l*5^n=N_l=a_{n-1,l}a_{n-2,l}\dots a_{0,l}$ were m_l+1 digits $a_{m_l,l}\dots a_{0,l}$ are odd. Let we have $m_{l+1}>m_l$, suth that $a_{m_{l+1},l}$ is even. We construct $k_{l+1}=k_l+2^{m_{l+1},N_{l+1}=k_{l+1}*5^n}$ with property: digits $a_{i,l+1}$ are odd for $i\le m_{l+1}$. This number is unique.

Rust wrote: It is easy to construct this number by induktion. $k_0=1, N_0=k_0*5^n=a_{n-1,0}a{n-2,0}\dots a_{0,0}, a_{0,0}=5 \ is \ odd.$ Let we have $k_l<2^{m_l+1},k_l*5^n=N_l=a_{n-1,l}a_{n-2,l}\dots a_{0,l}$ were m_l+1 digits $a_{m_l,l}\dots a_{0,l}$ are odd. Let we have $m_{l+1}>m_l$, suth that $a_{m_{l+1},l}$ is even. We construct $k_{l+1}=k_l+2^{m_{l+1},N_{l+1}=k_{l+1}*5^n}$ with property: digits $a_{i,l+1}$ are odd for $i\le m_{l+1}$. This number is unique. Thank you very much Rust please and is this the answer to my question ? Davron

I think you are wrong. Check it by programming. It is easy calculate for n<1000.

Rust wrote: I think you are wrong. Check it by programming. It is easy calculate for n<1000. nope but we have all the terms as odd numbers...?

the first number to satisfy ur condition is 375=3*5^3

We will proceed by induction to prove that there always exists a $n$ digit number with all odd digits $A_n$ such that $5^n|A_n$. Base Case: $n=1$, let $A_1=5$ and $5^1|A_1=5$. Inductive Hypothesis: There exists a $k$ digit number with all odd digits such that $5^k|A_k$. Now let $a\in\{1, 3, 5, 7, 9\}$ and $A_k=b_k\cdot 5^k$, then let $A_{k+1}=a\times 10^{k}+bA_k$ and we shall show that you can always pick some $a$ and $b$ such that $5^{k+1}|A_{k+1}$. Notice that $A_{k+1}$ is $A_k$ with an odd digit augmented to beginning of the number. Thus, $A_{k+1}$ contains only odd digits. \[A_{k+1}=5^{k}(a\cdot 2^k+b_k)\] So if we can choose some $a$ such that $a\cdot 2^k+b_k$ is divisible by $5$, then $5^{k+1}|A_{k+1}$. However, this is obviously true because $2^k a$ can take on any possible residue modulo $5$ since $a$ can take on any residue modulo $5$ and we are done. $\blacksquare$

Induction: Clearly true for $n=1$. Now assume true for $n=k$, where $d_i$ are the digits in the decimal representation, i.e. $5^k\mid{\overline{d_1d_2\cdots{d_k}}_{10}}$ with all $d_i$ odd. Then the next number in the list can potentially be any one of: $\overline{(2a+1)d_1d_2\cdots{d_k}}_{10}$, where $0\leq{a}\leq{4}$; we want to show that one of these has to be divisible by $5^{k+1}$. By the inductive hypothesis: $(2a+1)\cdot{10^k}+5^kt$; $t\in{\mathbb{Z^+}}$. Factoring (I-V) we have: $5^k(2^k(2a+1)+t_1)=5^k(2^{k+1}a+2^k+t_1)$. But wait! $(2^{k+1}a+2^k+t_1)$ forms a complete set of residue classes $\mod{5}$ as it runs across the $a$'s (this is obvious, see myticterminator's proof of it above), so we're done. $\blacksquare$

Quick

We prove the set of $n$-digits integers whose digits are odd form a complete set of residue modulo $5^n$. There are $5^n$ such integers. It suffices to show they are distinct.

PS : I suppose this problem inspired Croatian National MO 2005.

Let $f(n)$ be a number with $n$-digits and divisible by $5^n$. We claim that $f(n)$ exists. Induct on $n$, $n=2$ being trivial. Assume $f(n-1)$ exists. We claim that $f(n)=x\cdot 10^{n-1} + f(n-1)$ for some odd digit $x$. Let $f(n-1)=y\cdot 5^{n-1}$. Then \begin{align*} &~ 0\equiv f(n) = x\cdot 10^{n-1} + f(n-1) = x\cdot 10^{n-1} + y\cdot 5^{n-1} \pmod{5^n}. \\ &~ 2^{n-1}x + y \equiv 0 \pmod{5} \\ &~ x\equiv \frac{-y}{2^{n-1}} =\ell \pmod5. \end{align*}If $\ell$ is even, let $x=\ell+5 \pmod{10}$, so that $x$ is odd. If $\ell$ is odd, let $x=\ell$. This completes the induction.

We induct on $n$, with the base case of $n=1$ being obvious as we can pick our number to be $5$. Now suppose that $5^nx$ is a number with $n$ digits, all odd. For all $d\in\{1,3,5,7,9\}$, consider \[y:=10^n\cdot d+5^nx=5^n(x+2^nd).\]Since $\{1,3,5,7,9\}$ is a complete residue set mod $5$, we can pick some $d$ that makes $x+2^nd$ divisible by $5$, so our new number $y$ has $n+1$ digits, all odd, and is divisible by $5^{n+1}$.

Yay, first oly solve! We use induction. The base case $n = 1$ holds since $5\mid5$. Let $5^k \cdot b$ be a $k$ digit number with all odd digits for some integer $b$. Now we prove that there exists an odd digit $a$ such that $10^k \cdot a + 5^k \cdot b$ (which had $k+1$ digits) is divisible by $5^{k+1}$. Factoring gives $$5^k (2^k \cdot a + b)$$Letting $a$ be a variable and $k$ and $b$ be constants in the modular equation $2^k \cdot a + b \equiv \bmod{5}$. Since $2^k$ and $5$ are relatively prime for any $k$, the modular inverse of $2^k \bmod{5}$ exists. Therefore, the solution for for $a$ is $a \equiv -b \cdot 2^{-k} \bmod{5}$ where $2^{-k}$ is the modular inverse. Any solution in the set $a \in {0,1,2,3,4} \mod{5}$ corresponds to an odd digit $a$. Therefore, there always exists an odd digit $a$ such that $ 5^{k+1} \mid 10^k\cdot a + 5^k\cdot b$, concluding our induction. $\Box$

That's cool,even #3 this problem as his/her oly solve.

Induct to winduct. Obviously $n=1$ holds as $5^1\mid 5.$ Now we append a digit $k$ to the left of the $n$ digit number $a_n.$ Note that \[5^n\mid k\text{ and }5^n\mid a_n\]by definition. So let $\frac{a_n}{5^n}=b_n$ and note our new number is $5^n(2^n\cdot k+b_n).$ Note that since $5\nmid 2^n$ and $\{1,3,5,7,9\}$ is a complete residue set mod $5,$ $2^n\cdot k$ also covers a complete residue set mod $5,$ so it is always possible for $2^n\cdot k\equiv -b_n\pmod{5}$ to be true.

We will show that if there exists a $k$ digit integer divisible by $5^{k}$ there exists a $k+1$ digit integer divisible by $5^{k+1}$. If we add a digit $a$ to the far left of are $k$ digit integer we will show there exists an $a$ such that this is divisible by $5^{k+1}$ Let are $k$ digit integer be $c$ then we require $$c+a10^{k}\equiv 0 \pmod{5^{k+1}}$$$$\frac{c}{5^{k}}+2^{k}a \equiv 0 \pmod{5}$$Since we get a complete residue set mod $5$ as possibilities for $a$ the desired number exists. Since $5$ has $1$ digit and is divisible by $5$ we have completed our induction.

We prove this statement by induction. The base case for $n = 1$ is trivial, as $5^1 \mid 5$. Assume that for all $N \leq n$, we have $k \cdot 5^n$ has all of its $n$-digits as odd. (Observe that $k \in \{1, 3, 5, 7, 9\}$). Consider the $(n+1)$-digit integer $\ell \cdot 10^n + 5^n$. Factoring yields, \[5^n(\ell \cdot 2^n + k), \phantom{ccc}\ell \in \{1, 3, 5, 7, 9\}.\]Notice that the inside expression goes through all residues modulo $5$. Hence for every value of $\ell$, there is some $k$ for which $(\ell \cdot 2^n + k)$ is divisible by $5$, so that the entire expression including the factor of $5^n$ is divisible by $5^{n+1}$, which finishes the induciton. $\blacksquare$

Consider induction on $n$. When $n=1$, the desired number is $5$, and when moving forward, consider a working $n$-digit number to be $N$. Then, simply notice that exactly one of the elements in \[S = \{10^n+N, 3 \cdot 10^n+N, 5 \cdot 10^n+N, 7 \cdot 10^n+N, 9 \cdot 10^n+N\}\] will satisfy the conditions for an $(n+1)$-digit number, so we are done. $\square$

We proceed with induction. The base case, $n=1$ is obvious by just taking $5$ as our number. For our inductive step, assume $k$ is an $n$-digit number divisible by $5^n$ with all odd digits. We know that $k\equiv 0 \pmod {5^n}$, so $k$ can be congruent to either $0, 5^n, 2(5^n), 3(5^n)$, or $4(5^n)$ modulo $5^{n+1}$. Notice that the $n+1$ digit number $x(10^n) = x\cdot 2^n (5^n)$ as $x$ ranges over $1, 3, 5, 7, 9$ can only be $0, 5^n, 2(5^n), 3(5^n)$, or $4(5^n)$ modulo $5^{n+1}$. In fact, each of these five residues appears exactly once due to $\gcd(5, 2^n) = 1$. Thus, given a $k$, we can always pick an $x(10^n)$ that makes $k+x(10^n)$ an $n+1$ digit number with all odd digits and $k+x(10^n)\equiv 0\pmod {5^{n+1}}$. This completes our induction, so we're done. $\blacksquare$

We will use induction. $\newline$ Let our $n$-digit number be $k_n$. Then our base case of $n = 1$ works for $k_1 = 5$. $\newline$ Inductive Step: $\newline$ Assume that $k_n$ works. Then we can prove that $k_{n+1}$ works. Let $k_{n+1} = a \cdot 10^n + k_{n}$ for some $a \in \{1, 3, 5, 7, 9\}$. And since all of $\{1, 3, 5, 7, 9\}$ are distinct modulo $5$, then there must be some $a$ that makes $k_{n+1} \equiv 0\pmod{5^{n+1}}$ since both $10^n$ and $k_n$ are divisible by $5^n$, so we are done.

Davron wrote: Who can show that the first digit number of the k-digit number can be never equal to 1 ? Davron Consider 193,359,375

we will use induction we first have that there exists $(2x_0+1)*10^0$ that is divisible by $5^1$ next, assume there exists $(2x_0+1)*10^{n-1}+...+(2x_n+1)*10^0$ divisible by $5^n$ multiply by $10$ to get $2(x_1*10^n+...+x_n*10)+\frac{10^{n+1}-10}{9}$ this is divisible by $5^{n+1}$ add one to get $2(x_1*10^n+...+x_n*10)+\frac{10^{n+1}-1}{9} \equiv 1 (\text{mod }5^{n+1})$ we need $2(y_1*10^n+...+y_n) \equiv -1 (\text{mod }5^{n+1})$ the existence of this is trivial since $5^{n+1}-1$ is even therefore, we are done

Apologies for adding another solution to the long list already present here. Look at the $n$-digit decimal representations of the numbers $S = \left\{k\cdot 5^n\,\mid\, 0\leq k < 2^n\right\}$ [i.e., if the number has less than $n$ digits, then add appropriate number of zeroes at the beginning]. Define a map $f : S \to \{0,1\}^n$ as follows: $ f(\overline{a_1 a_2 \cdots a_n}) = (b_1, b_2, \cdots , b_n) $, where $ b_i = 0 $ if $ a_i $ is even and $ b_i = 1 $ if $ a_i $ is odd. If $ f(k\cdot 5^n) = f(l\cdot 5^n) $ where $ 0 \leq k \leq l < 2^n$ then $ (k-l) \cdot 5^n = \sum_{i=0}^{n-1} c_i \cdot 10^i $ for some $ c_i \in \{-8, -6, -4, -2, 0, 2, 4, 6, 8\} $. If any of the $ c_i $ are nonzero, let $ i $ be the smallest one. Then, the highest power of $5$ dividing $ \sum_{i=0}^{n-1} c_i \cdot 10^i $ is $i$, which is a contradiction. Therefore, $ k = l $, which implies that $f$ is injective. Since $|S| = 2^n = |\{ 0,1\}^n| $, we get that $f$ is surjective as well. Looking at the pre image of $(1, 1,\cdots , 1)$, we are done.

sus this was easier than i thought it was We will construct such a number inductively. Let $a_n$ be our constructed number with $n$ digits divisible by $5^n$ with all odd digits. For the base case $n = 1,$ take $a_1 = 5.$ Now suppose we have our number $a_k$ that is divisible by $5^k.$ Then we will add a digit to the beginning of $a_k$ to make $a_{k+1}.$ To add the digit at the beginning, we need to add one of $10^k, 3 \cdot 10^k, 5 \cdot 10^k, 7 \cdot 10^k,$ or $9 \cdot 10^k.$ Adding any of these will not change whether or not the expression is divisible by $5^k.$ Moreover, if we let $u = 2^k,$ the possible numbers we can add become $u \cdot 5^k, 3u \cdot 5^k, 5u \cdot 5^k, 7u \cdot 5^k,$ and $9u \cdot 5^k.$ Note that $\gcd(u, 5) = 1,$ so taking mod $5^{k+1}$ gives the list $0, 5^k, 2 \cdot 5^k, 3 \cdot 5^k, 4 \cdot 5^k$ in some order. Then if $a_n \equiv z \cdot 5^k \pmod{5^{k+1}},$ we just add the digit which gives the residue $(5-z) \cdot 5^k \pmod{5^{k+1}},$ which will give $a_{k+1}.$ The induction is complete, so we have solved the problem.

We prove this by induction. Base case ($n = 1$) is trivial, consider 5. Now say we have a number $k_{n-1} =\overline{ a_{n-1}\cdots a_1}$, all of whose digits are odd and which is a multiple of $5^{n-1}$, i. e. $k_{n-1} = p5^{n-1}$. Now consider $a_n$ such that $5 \mid 2^{n-1}a_n + p$. Clearly there is a unique residue $\pmod{5}$ satisfying this, and so two such numbers in $\{0, 1, \cdots, 9\}$; one odd and one even. Pick the $a_n$ which is odd. Then the number $k_n = \overline{a_n \cdots a_1}$ works.$\square$

Induct on $n$, base case $n=1$ is $5$. Now suppose there exists an $n$-digit number $a$ all of whose digits are odd. We will add $k10^n$, where $k \in \{1, 3, 5, 7, 9\}$. $1, 3, 5, 7, 9$ are distinct $\bmod \ 5$, therefore one will result in $a + k10^n \equiv 0 \pmod {5^{n+1}}$.

This problem appeared in the 2024 Singapore Mathmatical Olympiad Open Round 2.

We will use induction. Base case: $n=1.$ The number $5$ works. Inductive step: Assume there exists a number $N$ with $k$ digits, each digit odd that is a multiple of $5^k.$ The possible $k+1$ digit numbers are $N+10^k,N+3 \left(10^k \right) \dots N+9 \left(10^k \right).$ Each of those numbers can be factored as $5^k(R+2^k), 5^k(R+3\left(2^k \right) \dots 5^k(R+9\left(2^k\right)$. Here, $R$ is the number $\frac{N}{5^k}.$ Each of the numbers of the form $R+2^k, R+3\cdot 2^k, \dots$ are equivalent to a different residue modulo 5, so one of them must be a multiple of $5$. Therefore, there exists an odd number we can "place" in front of $N$ to create a $k+1$ digit number that is a multiple of $5^{k+1}$ with all digits odd. The induction is complete and the desired statement holds.

We will prove this with induction. Base Case. $n = 1$. We can consider the odd $1$-digit number $5$ which is divisible by $5^1$. Induction. Suppose the conditions hold for $k = n$, we will show it works for $k = n + 1$. Suppose $T \cdot 5^n$ is a $n$-digit number whose digits are all odd. Then, consider the following numbers: \begin{align*} 1 \cdot 10^n + T \cdot 5^n, \quad 3 \cdot 10^n + T \cdot 5^n, \quad 5 \cdot 10^n + T \cdot 5^n, \quad 7 \cdot 10^n + T \cdot 5^n, \quad 9 \cdot 10^n + T \cdot 5^n. \end{align*}Factoring out $5^n$ from these numbers yields \begin{align*} 1 \cdot 2^n + T, \quad 3 \cdot 2^n + T, \quad 5 \cdot 2^n + T, \quad 7 \cdot 2^n + T, \quad 9 \cdot 2^n + T. \end{align*}Suppose $p$ and $q$ are unique values selected from this list. Then, $p - q = r \cdot 2^n$ for some $r$. Notice $r$ cannot be divisible by $5$, thus $p$ and $q$ are unique values modulo $5$. Therefore, these five values are all unique modulo $5$. So, one of them must be divisible by $5$, as desired.

We use induction on $n$. Base case is obvious. For $n= k$, assume there exits an integer $N$ such that $5^k \vert N$, and $N$ is $k$-digit number with all digits being odd. Now, for $n = k+1$, consider the numbers $i \times 10^k + N$, $i = 1, 3, 5, 7, 9$. Note that $5^k \vert i \times 10^k + N$, which can be written as $i \times 10^k + N = 5^k \left( i \times 2^k + \frac{N}{5^k} \right)$. Observe that the numbers $ i \times 2^k + \frac{N}{5^k}$ give five different remainders when divided by $5$, so one of them must be divisibly by $5$. This implies $i \times 10^k + N$ is divisibly by $5^{k+1}$ for one $i \in \{1, 3, 5, 7, 9 \}$, and has $k+1$ odd digits, as required. $\square$