Maths Olympiad Prep

Library / /16 of 94

Number theory Difficulty 6.0 AIME, harder Prove it Japan

Consider an infinite sequence a1,a2,a3,a_1, a_2, a_3, \dots of positive integers. Suppose that the following 2 conditions are satisfied for an arbitrary positive integer nn:
* ana_n is a multiple of nn.
* anan+15|a_n - a_{n+1}| \le 5.
Find the maximum possible value that a1a_1 can take.

Solution

Let a1,a2,a3,a_1, a_2, a_3, \dots be an infinite sequence of positive integers satisfying the conditions of the problem. From an+1an+5a_{n+1} \le a_n + 5 (n=1,2,n = 1, 2, \dots) it follows that for every nn an5(n1)+a1a_n \le 5 (n-1) + a_1 is satisfied. In particular, for all sufficiently large nn an<6na_n < 6n is satisfied (in fact, na14n \ge a_1 - 4 will do.) As ana_n is a multiple of nn by assumption, we see that an5na_n \le 5n for all sufficiently large nn.

Suppose there exists an nn for which an>5na_n > 5n. Since there are only a finite number of such nn's, as we saw above, there must be the largest such nn, which we denote by NN. Then, aN>5Na_N > 5N and aN+15(N+1)a_{N+1} \le 5(N + 1). As aNa_N is a multiple of NN, we in fact have aN6Na_N \ge 6N. From
5aNaN+16N5(N+1)=N5 5 \ge a_N - a_{N+1} \ge 6N - 5(N+1) = N - 5
we obtain that N10N \le 10. We have thus shown that if n11n \ge 11, then an5na_n \le 5n. In particular, a1155a_{11} \le 55. and since ana_n is a multiple of nn and does not exceed an+1+5a_{n+1} + 5, we obtain recursively,
a1060,a963,a864,a763,a666,a570,a472,a375,a280,a185. \begin{align*} a_{10} &\le 60, \quad a_9 \le 63, \quad a_8 \le 64, \quad a_7 \le 63, \quad a_6 \le 66, \\ a_5 &\le 70, \quad a_4 \le 72, \quad a_3 \le 75, \quad a_2 \le 80, \quad a_1 \le 85. \end{align*}
If, on the other hand, we define
a1=85,a2=80,a3=75,a4=72,a5=70,a6=66,a7=63,a8=64,a9=63,a10=60,an=5n (n11) \begin{align*} a_1 &= 85, \quad a_2 = 80, \quad a_3 = 75, \quad a_4 = 72, \quad a_5 = 70, \quad a_6 = 66, \\ a_7 &= 63, \quad a_8 = 64, \quad a_9 = 63, \quad a_{10} = 60, \quad a_n = 5n\ (n \ge 11) \end{align*}
then this sequence can be shown to satisfy the conditions of the problem, and hence we conclude that 85 is the desired maximum.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.