Maths Olympiad Prep

Library / /12 of 25

Number theory Difficulty 6.2 National Olympiad Prove it North Macedonia

Let aa and bb be integers bigger than 22. Prove that there is a positive integer kk and a finite sequence n1,n2,,nkn_1, n_2, \dots, n_k of positive integers, such that n1=an_1 = a, nk=bn_k = b and (ni+ni+1)nini+1(n_i + n_{i+1}) \mid n_i n_{i+1} for every i=1,2,,ki = 1, 2, \dots, k.

Solution

We'll write aba \leftrightarrow b if there exists such a sequence. It is easy to see that \leftrightarrow is an equivalence relation. Notice that n2nn \leftrightarrow 2n for every integer nn, n3n \ge 3 because in that case the desired finite sequence is
n1=n, n2=n(n1), n3=n(n1)(n2), n4=n(n2), n5=2n n_1 = n,\ n_2 = n(n-1),\ n_3 = n(n-1)(n-2),\ n_4 = n(n-2),\ n_5 = 2n
For every nn, n4n \ge 4 we have n=(n1)(n2)3n' = (n-1)(n-2) \ge 3 and we obtain n2nn' \leftrightarrow 2n'. For n4n \ge 4:
n1=n, n2=n(n1), n3=n(n1)(n2), n4=n(n1)(n2)(n3),n5=2(n1)(n2)=2n \begin{aligned} n_1 &= n,\ n_2 = n(n-1),\ n_3 = n(n-1)(n-2),\ n_4 = n(n-1)(n-2)(n-3),\\ n_5 &= 2(n-1)(n-2) = 2n' \end{aligned}
i.e. n2nn \leftrightarrow 2n' and because n1=n=(n1)(n2)n_1' = n' = (n-1)(n-2), n2=n1n_2' = n-1 we obtain nn1n' \leftrightarrow n-1. From the previous discussion we get that n2nn \leftrightarrow 2n', 2nn2n' \leftrightarrow n', nn1n' \leftrightarrow n-1 and from the transitivity of \leftrightarrow we obtain nn1n \leftrightarrow n-1 for every integer nn, n4n \ge 4. Because \leftrightarrow is symmetric nn+1n \leftrightarrow n+1 for every integer nn, n3n \ge 3. Hence from the transitivity of \leftrightarrow we obtain the desired result.

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.