Maths Olympiad Prep

Library / /283 of 383

Number theory Difficulty 8.8 Shortlist Prove it IMO

Let n2018n \geqslant 2018 be an integer, and let a1,a2,,an,b1,b2,,bna_{1}, a_{2}, \ldots, a_{n}, b_{1}, b_{2}, \ldots, b_{n} be pairwise distinct positive integers not exceeding 5n5n. Suppose that the sequence
a1b1,a2b2,,anbn \frac{a_{1}}{b_{1}}, \frac{a_{2}}{b_{2}}, \ldots, \frac{a_{n}}{b_{n}}
forms an arithmetic progression. Prove that the terms of the sequence are equal.

Solution

Suppose that (1) is an arithmetic progression with nonzero difference. Let the difference be Δ=cd\Delta=\frac{c}{d}, where d>0d>0 and c,dc, d are coprime.
We will show that too many denominators bib_{i} should be divisible by dd. To this end, for any 1in1 \leqslant i \leqslant n and any prime divisor pp of dd, say that the index ii is pp-wrong, if vp(bi)<vp(d)v_{p}\left(b_{i}\right)<v_{p}(d). (vp(x)v_{p}(x) stands for the exponent of pp in the prime factorisation of xx.)

Claim 1. For any prime pp, all pp-wrong indices are congruent modulo pp. In other words, the pp-wrong indices (if they exist) are included in an arithmetic progression with difference pp.

Proof. Let α=vp(d)\alpha=v_{p}(d). For the sake of contradiction, suppose that ii and jj are pp-wrong indices (i.e., none of bib_{i} and bjb_{j} is divisible by pαp^{\alpha} ) such that i≢j(modp)i \not \equiv j\pmod{p}. Then the least common denominator of aibi\frac{a_{i}}{b_{i}} and ajbj\frac{a_{j}}{b_{j}} is not divisible by pαp^{\alpha}. But this is impossible because in their difference, (ij)Δ=(ij)cd(i-j) \Delta=\frac{(i-j) c}{d}, the numerator is coprime to pp, but pαp^{\alpha} divides the denominator dd.

Claim 2. dd has no prime divisors greater than 55.

Proof. Suppose that p7p \geqslant 7 is a prime divisor of dd. Among the indices 1,2,,n1,2, \ldots, n, at most np<np+1\left\lceil\frac{n}{p}\right\rceil<\frac{n}{p}+1 are pp-wrong, so pp divides at least p1pn1\frac{p-1}{p} n-1 of b1,,bnb_{1}, \ldots, b_{n}. Since these denominators are distinct,
5nmax{bi:pbi}(p1pn1)p=(p1)(n1)16(n1)1>5n 5 n \geqslant \max \left\{b_{i}: p \mid b_{i}\right\} \geqslant\left(\frac{p-1}{p} n-1\right) p=(p-1)(n-1)-1 \geqslant 6(n-1)-1>5 n
a contradiction.

Claim 3. For every 0kn300 \leqslant k \leqslant n-30, among the denominators bk+1,bk+2,,bk+30b_{k+1}, b_{k+2}, \ldots, b_{k+30}, at least φ(30)=8\varphi(30)=8 are divisible by dd.

Proof. By Claim 1, the 22-wrong, 33-wrong and 55-wrong indices can be covered by three arithmetic progressions with differences 2,32,3 and 55. By a simple inclusion-exclusion, (21)(31)(51)=8(2-1) \cdot(3-1) \cdot(5-1)=8 indices are not covered; by Claim 2, we have dbid \mid b_{i} for every uncovered index ii.

Claim 4. Δ<20n2|\Delta|<\frac{20}{n-2} and d>n220d>\frac{n-2}{20}.

Proof. From the sequence (1), remove all fractions with bn<n2b_{n}<\frac{n}{2}. There remain at least n2\frac{n}{2} fractions, and they cannot exceed 5nn/2=10\frac{5 n}{n / 2}=10. So we have at least n2\frac{n}{2} elements of the arithmetic progression (1) in the interval (0,10](0,10], hence the difference must be below 10n/21=20n2\frac{10}{n / 2-1}=\frac{20}{n-2}.
The second inequality follows from 1dcd=Δ\frac{1}{d} \leqslant \frac{|c|}{d}=|\Delta|.

Now we have everything to get the final contradiction. By Claim 3, we have dbid \mid b_{i} for at least n308\left\lfloor\frac{n}{30}\right\rfloor \cdot 8 indices ii. By Claim 4, we have dn220d \geqslant \frac{n-2}{20}. Therefore,
5nmax{bi:dbi}(n308)d>(n301)8n220>5n 5 n \geqslant \max \left\{b_{i}: d \mid b_{i}\right\} \geqslant\left(\left\lfloor\frac{n}{30}\right\rfloor \cdot 8\right) \cdot d>\left(\frac{n}{30}-1\right) \cdot 8 \cdot \frac{n-2}{20}>5 n
which is a contradiction. Therefore, the difference Δ\Delta must be zero, i.e., all terms of the sequence are equal.

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.