Competition problem — Number theory

Library / /14 of 46

Number theory Difficulty 5.7 AIME, harder Prove it Russia

An increasing sequence of positive integers $\{a_n\}$ and a positive integer $k$ are given. For each positive integer $n$ the following conditions hold: the number $a_n$ is divisible either by $1005$ or by $1006$ , $a_n$ is not divisible by $97$ , and $a_{n+1} - a_n \le k$ . Find the least possible value of $k$ . (A. Golovanov)

Solution

Ответ. $k = 2010$ .

Let us denote our sequence by $(a_n)$ . Clearly, $a_1 < 1005 \cdot 1006 \cdot 97 \cdot N = D$ for some natural $N$ . Then there exists such $n$ that $a_n \le D$ , but $a_{n+1} > D$ (at the same time, $a_n \ne D$ by the condition). But the largest numbers less than $D$ and divisible by $1005$ and $1006$ are $D-1005$ and $D-1006$ , respectively; therefore $a_n \le D-1005$ . Similarly, $a_{n+1} \ge D+1005$ ; hence $a_{n+1}-a_n \ge (D+1005)-(D-1005) = 2010$ . Thus, $k \ge 2010$ .

For $k=2010$ , for example, the sequence of all numbers divisible by $1005$ but not by $97$ fits (note that $1005$ is not divisible by $97$ ).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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