Maths Olympiad Prep

Library / NMO Selection Tests for BMO and IMO /18 of 47

NMO Selection Tests for BMO and IMO

Number theory Difficulty 8.0 National Olympiad, round 2 Prove it Romania

Let nn be a positive integer, and let a1,…,ana_1, \dots, a_n be pairwise distinct positive integers. Show that
∑k=1n1[a1,…,ak]<4, \sum_{k=1}^{n} \frac{1}{[a_1, \dots, a_k]} < 4,
where [a1,…,ak][a_1, \dots, a_k] is the least common multiple of the integers a1,…,aka_1, \dots, a_k.

Solution

Since the number of positive divisors of a positive integer mm does not exceed 2m2\sqrt{m}, and a1,…,aka_1, \dots, a_k are pairwise distinct positive divisors of [a1,…,ak][a_1, \dots, a_k], it follows that [a1,…,ak]≥k2/4[a_1, \dots, a_k] \ge k^2/4. Consequently,
∑k=1n1[a1,…,ak]=1a1+∑k=2n1[a1,…,ak]≤1+∑k=2n4k2<1+4∑k=2n1k2−14=1+4⋅2(13−12n+1)<113<4. \begin{aligned} \sum_{k=1}^{n} \frac{1}{[a_1, \dots, a_k]} &= \frac{1}{a_1} + \sum_{k=2}^{n} \frac{1}{[a_1, \dots, a_k]} \le 1 + \sum_{k=2}^{n} \frac{4}{k^2} < 1 + 4 \sum_{k=2}^{n} \frac{1}{k^2 - \frac{1}{4}} \\ &= 1 + 4 \cdot 2 \left( \frac{1}{3} - \frac{1}{2n+1} \right) < \frac{11}{3} < 4. \end{aligned}

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.