Maths Olympiad Prep

Library / /210 of 299

Number theory Difficulty 6.9 National Olympiad Prove it Iran

Let n2n \ge 2 be a given positive integer. Prove that there is a nn-tuple (a1,,an)(a_1, \dots, a_n) of pair-wise coprime positive integers, each of which greater than 14021402 such that
a1a2+a2a3++ana1=a2a1+a3a2++a1an \lfloor \frac{a_1}{a_2} \rfloor + \lfloor \frac{a_2}{a_3} \rfloor + \dots + \lfloor \frac{a_n}{a_1} \rfloor = \lfloor \frac{a_2}{a_1} \rfloor + \lfloor \frac{a_3}{a_2} \rfloor + \dots + \lfloor \frac{a_1}{a_n} \rfloor
Note. by x\lfloor x \rfloor, we mean the greatest integer that doesn't exceed xx.

Solution

Notice that if a1<a2<<ana_1 < a_2 < \dots < a_n are positive integers such that
a2/a1,a3/a2,,an/an1(1,2)a_2/a_1, a_3/a_2, \dots, a_n/a_{n-1} \in (1, 2)

while an/a1(n,n+1)a_n/a_1 \in (n, n+1) then (a1,,an)(a_1, \dots, a_n) would satisfy the condition of the problem. It thus suffices to find such numbers. We shall then prove the following lemma.

Lemma 1. Let AA and BB be rational numbers and pp and qq be distinct prime numbers. Then, gcd(AN!+p,BN!+q)=1\gcd(A \cdot N! + p, B \cdot N! + q) = 1, for all large enough positive integers NN.

Proof. Let (A,B)=(a/b,c/d)(A, B) = (a/b, c/d). Let D=gcd(AN!+p,BN!+q)D = \gcd(A \cdot N! + p, B \cdot N! + q). It follows that DacpbdqD|acp - bdq. Thus, D<max(acp,bdq)D < \max(acp, bdq). Choose N>2max(acp,bdq)N > 2 \cdot \max(acp, bdq), it follows that DAN!D|A \cdot N!, DBN!D|B \cdot N!. Yielding D=1D = 1. This proves our lemma.

We now construct a1,,ana_1, \dots, a_n. Let us denote by p1,,pnp_1, \dots, p_n the first nn primes and A1,,AnA_1, \dots, A_n be arbitrary rational numbers such that Ai(1,2)A_i \in (1, 2) while A1A2An(n,n+1)A_1 \cdot A_2 \cdots A_n \in (n, n+1). Then, choose a large enough NN and put ai=AiN!+pia_i = A_i \cdot N! + p_i, i=1,,ni = 1, \dots, n. It can be easily verified that these numbers would be satisfying the condition of the problem. ■

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.