Track / Stage 6 / 343 of 400 #1343 of 2000

Problem 1343

National olympiad, first round

Number theory Difficulty 6.7 Prove it 37th Iranian Mathematical Olympiad · Iran

Let $k \in \mathbb{N}$ and $\{a_n\}_{n \ge 0}$ and $\{b_n\}_{n \ge 0}$ be two sequences of positive integers such that $a_i, b_i \in \{1, 2, \dots, 9\}$ . For all $n \ge 0$
$\overline{a_n \dots a_1 a_0} + k \mid \overline{b_n \dots b_1 b_0} + k.$
Prove that there is a number $t$ with $1 \le t \le 9$ and $N \in \mathbb{N}$ such that $b_n = t a_n$ for all $n \ge N$ .

(Note that $(\overline{x_n x_{n-1} \dots x_0}) = 10^n \times x_n + \dots + 10 \times x_1 + x_0)$

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

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 \neq 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{aligned} 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{aligned}$
Therefore,
$10^{n+1} \mid (A_n + k)(C_{n+1} - C_n).$
Now suppose that $C_{n+1} \neq 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} \neq 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. ■

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.