37th Iranian Mathematical Olympiad

Let $A_n=\overline{a_n\dots a_1{a}_0}$, $B_n=\overline{b_n\dots b_1{b}_0}$, and $C_n=\frac{B_n+k}{A_n+k}$. Obviously $C_n<10$, so $C_n\in \{1,2,\dots ,9\}$.

Claim. If the sequence $\{a_i\}$ doesn't eventually become constant $9$, there exists $N\in \mathbb{N}$ such that $k+A_n<10^{n+1}$ ($\forall n>N$). Proof. Assume that there exists an index $i$ large enough that $k<10^i$ and $a_i\ne 9$. So we get $$k+A_i=\overline{a_i\dots a_0}+k<9\times 10^i+k<10^{i+1}.$$ Now note that $$k+A_{i+1}=10^{i+1}{a}_{i+1}+A_i+k\le 9\times 10^{i+1}+A_i+k<10^{i+2}.$$ So inductively, the claim will be proved. If the sequence $a_i$ becomes constant $9$, then the sequence $b_i$ also becomes constant $9$ and we're done. Now consider the case that $a_i$ doesn't become constant $9$. For all sufficiently large $n$, $A_n+k<10^{n+1}$. Also we know that $(A_n+k)C_n=B_n+k$ and $(A_{n+1}+k)C_{n+1}=B_{n+1}+k$, which implies: $$\begin{array}{rl}10^{n+1}{b}_{n+1}& =B_{n+1}-B_n=(A_{n+1}+k)C_{n+1}-(A_n+k)C_n\\ & =(A_n+k)(C_{n+1}-C_n)+10^{n+1}\times C_{n+1}{a}_{n+1}.\end{array}$$ Therefore, $$10^{n+1}\mid (A_n+k)(C_{n+1}-C_n).$$ Now suppose that $C_{n+1}\ne C_n$, which means $1\le |C_{n+1}-C_n|\le 8$. Then, because $\gcd (10^3,C_{n+1}-C_n)\le 8$, we have $10^{n-2}\mid A_n+k$. For all $n$, define $S_n$ such that for some $\theta \in \mathbb{N}$, $$A_n+k=10^{\theta }\times S_n$$ and $10\nmid S_n$. Let $A_{i-1}+k=10^{\alpha }\times S_{i-1}$. Then $$A_i+k=10^{\alpha }\times S_{i-1}+10^i\times a_i.$$ If we choose $i$ large enough, by the previous claim we know that $A_{i-1}+k<10^i$. So $\alpha <i$. This means that $A_i+k=10^{\alpha }\times S_i$. So we get that $A_n+k=10^{\alpha }\times S_n$ for all sufficiently large $n$. But if $C_{n+1}\ne C_n$, we have $10^{n-2}\mid A_n+k$ this means that $\alpha \ge n-2$, which is impossible for large enough $n$. So there exists $N\in \mathbb{N}$ such that $C_{n+1}=C_n$ for all $n>N$. This means that $10^{n+1}{b}_{n+1}=C\times 10^{n+1}{a}_{n+1}$. So $b_{n+1}=C\times a_{n+1}$ and we're done. ■