Given a number $k\in \mathbb{N}$. $\{a_{n}\}_{n\geq 0}$ and $\{b_{n}\}_{n\geq 0}$ are two sequences of positive integers that $a_{i},b_{i}\in \{1,2,\cdots,9\}$. For all $n\geq 0$ $$\left.\overline{a_{n}\cdots a_{1}a_{0}}+k \ \middle| \ \overline{b_{n}\cdots b_{1}b_{0}}+k \right. .$$Prove that there is a number $1\leq t \leq 9$ and $N\in \mathbb{N}$ such that $b_n=ta_n$ for all $n\geq N$. (Note that $(\overline{x_nx_{n-1}\dots x_0}) = 10^n\times x_n + \dots + 10\times x_1 + x_0$)
Problem
Source: Iran MO 3rd round 2019 mid-terms - Number theory P1
Tags: number theory
01.08.2019 17:02
Let $c_n=\frac{\overline{b_n\dots b_1b_0}+k}{\overline{a_n\dots a_1a_0}+k}$, note that $c_n \in \{1,2,3,\dots,9\}$. Let $\overline{a_n\dots a_1a_0}+k=A$ and $\overline{b_n\dots b_1b_0}+k=Ac_n$. Claim. For large $n$ we either have both the sequences $a_n,b_n$ consisting of only $9's$ or $10^{n+1}>A$. Proof: If $A>10^{n+1}$, then the sequence $a_i$ at one moment would start to be all $9$'s which would mean all $b_i$'s should be $9$'s. So, assume that $a_{n+1}\neq 1$, for $n$ large we have $$c_{n+1}=\frac{b_{n+1}10^{n+1}+Ac_n}{a_{n+1}10^{n+1}+A}=i+\frac{10^{n+1}(b_{n+1}-i\cdot a_{n+1})+A(c_n-i)}{a_{n+1}10^{n+1}+A}$$where $i$ is the largest natural number such that $9\geq b_{n+1}-ia_{n+1}\geq 0$. It is not hard to see that $0\leq \frac{10^{n+1}(b_{n+1}-i\cdot a_{n+1})+A(c_n-i)}{a_{n+1}10^{n+1}+A}<1$. Since we assumed $a_{n+1}\neq 1$ we have $c_{n+1}\in \{1,2,3,4\}$ and $c_{n+1}=i$. Therefore $10^{n+1}(b_{n+1}-i\cdot a_{n+1})=-A(c_n-i)$, assume $b_{n+1}\neq i\cdot a_{n+1}$, we have $10^{n}\mid A$ for all large $n$ which implies that $A$ has to be of the form $\overline{d000\dots000}$ but $a_i>0$ which is a contradiction. Remark. This proof also shows that $c_{n}=i$ which implies that the sequence $\frac{a_n}{b_n}$ is eventually constant.
27.09.2020 10:01
XbenX wrote: Let $c_n=\frac{\overline{b_n\dots b_1b_0}+k}{\overline{a_n\dots a_1a_0}+k}$, note that $c_n \in \{1,2,3,\dots,9\}$. Let $\overline{a_n\dots a_1a_0}+k=A$ and $\overline{b_n\dots b_1b_0}+k=Ac_n$. Claim. For large $n$ we have $10^{n+1}>A$. Proof: Assume not, then the sequence $a_i$ at one moment would start to be all $9$'s which would mean all $b_i$'s should be $9$'s and we'd be done. So, assume that $a_{n+1}\neq 1$, for $n$ large we have $$c_{n+1}=\frac{b_{n+1}10^{n+1}+Ac_n}{a_{n+1}10^{n+1}+A}=i+\frac{10^{n+1}(b_{n+1}-i\cdot a_{n+1})+A(c_n-i)}{a_{n+1}10^{n+1}+A}$$ Since we assumed $a_{n+1}\neq 1$ we have $c_{n+1}\in \{1,2,3,4\}$, for $c_{n+1}=i$ we have $10^{n+1}(b_{n+1}-i\cdot a_{n+1})=-A(c_n-i)$, assume $b_{n+1}\neq i\cdot a_{n+1}$, we have $10^{n+1}\mid A$ wich is a contradiction. $\blacksquare$ If $2\mid(c_n-i)$ How to get $10^{n+1}\mid A$
27.09.2020 10:50
It should be fixed now, thanks.
26.02.2022 03:37
Let $A_n=\overline{a_{n}\cdots a_{1}a_{0}}$ and $B_n= \overline{b_{n}\cdots b_{1}b_{0}} $ Let $C_n = \frac{A_n}{B_n}$ Claim 1: If for a sufficiently large $n$, $a_n \ne 9$ then there exists $N$ such that $A_n+k < 10^{n+1}$ for all $n>N$ Proof Consider $N$ such that $10^N>k$ and $a_N \ne 9$, then we have $$ A_N+k < 9 \cdot 10^N+k < 10^{N+1} $$Then $$ A_{N+1}+k=a_{N+1} \cdot 10^N+ A_N+k \le 9 \cdot 10^N+ A_N+k < 9 \cdot 10^N+10^{N+1}<10^{N+2} $$Then keep induct on $n$ for large $n>N$ we have $A_n+k < 10^{n+1}$ for all $n>N$ Now $a_n$ becomes constant $9$ from a large $n$ then we also have $b_n$ becomes constant $9$, thus $b_n=a_n$ from a large $n$ and done! Assume that for a sufficiently large $N$, $a_{N} \ne 9$ then $A_n+k <10^{n+1}$ for all $n>N$ by the claim We have $$ 10^{n+1} \cdot b_{n+1} = B_{n+1} - B_n = C_{n+1} (A_{n+1} + k ) - C_n ( A_n + k ) =(A_n+k)(C_{n+1}-C_{n})+C_{n+1} 10^{n+1} a_{n+1} $$ Hence we have $$ 10^{n+1} \mid (A_n+k)(C_{n+1}-C_{n}) (*) $$ Note that from $A_N+k<10^{N+1}$, we have $v_{10}(A_N+k)=c<N+1$ then $v_{10}(A_{N+1}+k)=v_{10}(10^{n+1}a_{N+1} + A_N+k) = v_{10}(A_N+k)=c$ implies that $$ v_{10}(A_n+k)=c \text{ for all } n >N $$ Also since $|C_{n+1}-C_n| \in \{ 0,1,2,3,..,8 \} $, which leads to $C_{n+1}=C_n$, hence $C_n = c: \text{ constant }$ from a large $n$ leads to $$ 10^{n+1} \cdot b_{n+1} =c \cdot 10^{n+1} \cdot a_{n+1} \implies b_{n+1}=c \cdot a_{n+1} \implies b_m=ca_m \forall m \ge n $$