Olympiad Maths Prep

Track / Stage 6 / 31 of 400 #1031 of 2000

Problem 1031

National olympiad, first round
Number theory Difficulty 6.0 Prove it

Example 33 (2001 China National Team Training Selection Contest for IMO) For given positive integers a,b,b>a>1,aa, b, b>a>1, a does not divide bb and a given sequence of positive integers {bn}n=1\left\{b_{n}\right\}_{n=1}^{\infty}, satisfying for all positive integers nn that bn+12bnb_{n+1} \geqslant 2 b_{n}. Does there always exist a sequence of positive integers {an}n=1\left\{a_{n}\right\}_{n=1}^{\infty} such that for all positive integers nn, an+1an{a,b}a_{n+1}-a_{n} \in\{a, b\}, and for all positive integers m,lm, l (which can be the same), am+al{bn}n=1a_{m}+a_{l} \notin\left\{b_{n}\right\}_{n=1}^{\infty}?

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

The answer is affirmative. We prove it by inductive construction.
Take a1a_{1} as a positive integer such that 2a1{bn}n=1,a1>ba2 a_{1} \notin \left\{b_{n}\right\}_{n=1}^{\infty}, a_{1}>b-a (for example, if bn0>ba+1b_{n_{0}}>b-a+1, take a1=bn01a_{1}=b_{n_{0}}-1). Assume that a1,a2,,aka_{1}, a_{2}, \cdots, a_{k} have been chosen such that
ai+1ai{a,b},am+al{bn}n=11(1mk,1lk)a_{i+1}-a_{i} \in \{a, b\}, a_{m}+a_{l} \notin \left\{b_{n}\right\}_{n=1}^{\prime \prime 1}(1 \leqslant m \leqslant k, 1 \leqslant l \leqslant k). Consider
 (I) a1+ak+a,a2+ak+a,,ak+ak+a,2ak+2a (II) a1+ak+b,a2+ak+b,,ak+ak+b,2ak+2b \begin{array}{l} \text { (I) } a_{1}+a_{k}+a, a_{2}+a_{k}+a, \cdots, a_{k}+a_{k}+a, 2 a_{k}+2 a \text {; } \\ \text { (II) } a_{1}+a_{k}+b, a_{2}+a_{k}+b, \cdots, a_{k}+a_{k}+b, 2 a_{k}+2 b \text {. } \end{array}

Assume (I) contains a term bub_{u} from {bn}n=1n\left\{b_{n}\right\}_{n=1}^{n}, and (II) contains a term bvb_{v} from {bn}n=1n\left\{b_{n}\right\}_{n=1}^{n}. Since
2 a_{k}+2 b0$. By the inductive hypothesis, $a_{i}-a_{j}=c a+d b, c, d$ are non-negative integers. Thus, $c a+d b=b-a$. Therefore, $d=0, b=(c+1) a$, which contradicts the fact that $a$ does not divide $b$. Case $2 \quad b_{u}=2 a_{k}+2 a$. In this case, $a_{k}-a_{j}=b-2 a$. By $1 \leqslant j \leqslant k$ and the inductive hypothesis, $a_{k}-a_{j}=c^{\prime} a+d^{\prime} b, c^{\prime}, d^{\prime}$ are non-negative integers. Thus, $c^{\prime} a+d^{\prime} b=b-2 a$. Therefore, $d^{\prime}=0, b=\left(c^{\prime}+1\right) a$, which is a contradiction. Hence, (I) or (II) does not contain any term from $\left\{b_{n}\right\}_{n=1}^{\infty}$. Therefore, we can take $a_{k+1}=a_{k}+a$ or $a_{k}+b$ such that
a_{k+1}+a_{i} \notin \left\{b^{\prime \prime}\right\}_{n=1}^{\prime \prime}, 1 \leqslant i \leqslant k+1 \text {. }

The proposition is proved.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.