Competition problem — Algebra — Maths Olympiad Prep

Library / /9 of 15

Algebra Difficulty 5.2 AIME, harder Prove it United States

Problem:

Determine, with proof, whether or not there exist distinct positive integers $a_{1}, a_{2}, \ldots, a_{n}$ such that
$\frac{1}{a_{1}} + \frac{1}{a_{2}} + \cdots + \frac{1}{a_{n}} = 2019.$

Solution

Solution:

Yes, the decomposition exists.
Recall that the harmonic series diverges. We first take the largest partial sum of the harmonic series that is smaller than $2019$ , subtract it from $2019$ to get a "remainder" $r$ . We then use the greedy algorithm to pick the rest of the unit fractions: pick the largest integer $n$ with $1 / n \leq r$ , and replace $r$ with $r - 1 / n$ . It is not hard to see the integers chosen at each step increase.

The main observation is that as we whittle away at the remainder $r$ , the numerator of the remainder decreases at every step. Therefore this process must eventually terminate, and it can only terminate when $r = 0$ , as needed.

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.