Competition problem — Number theory

Library / /11 of 22

Number theory Difficulty 4.9 AIME Prove it United States

Problem:
Each of the positive integers $a_{1}, a_{2}, \ldots, a_{n}$ is less than $2016$ , and the least common multiple of any two is greater than $2016$ . Show that
$\frac{1}{a_{1}}+\cdots+\frac{1}{a_{n}}<1+\frac{n}{2016}.$

Solution

Solution:
By considering multiples of the $a_{i}$ which are less than $2016$ (these don't overlap by condition) we derive
$\sum\left\lfloor\frac{2016}{a_{i}}\right\rfloor \leq 2016$
Upon using the fact that $\lfloor x\rfloor>x-1$ , we then obtain
$\sum\left(\frac{2016}{a_{i}}-1\right)<2016 \text{.}$
which rearranges to the desired conclusion.

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.