Maths Olympiad Prep

Track / Stage 5 / 394 of 400 #1634 of 2604

Problem 1634

AIME late
Number theory Difficulty 6.0 Prove it IRL ABooklet · Ireland

Determine whether there is a finite set {a1,a2,…,an}\{a_1, a_2, \dots, a_n\} of distinct positive integers such that
2020=∑j=1n1aj. 2020 = \sum_{j=1}^{n} \frac{1}{a_j}.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Yes, there is such a set. We construct it in two stages.
Readers who are familiar with Egyptian Fractions should be aware of the fact that any rational number 0<x<10 < x < 1 can be expressed as a sum of reciprocals of distinct integers. Indeed, the greedy algorithm delivers such an expression: at each point choose the smallest integer ss for which 1s≤x\frac{1}{s} \le x; this either gives equality, in which case we stop, or we start again with x−1sx - \frac{1}{s} replacing xx. We need to show this algorithm terminates and gives a sequence of distinct denominators ss. We write the fraction in its lowest terms as x=pqx = \frac{p}{q} with 1≤p<q1 \le p < q. If p=1p = 1 the result is immediate. Otherwise 1<p<q1 < p < q and there exists a unique integer s≥2s \ge 2 such that
1s≤x<1s−1. \frac{1}{s} \le x < \frac{1}{s-1}.
As x−1s<1s−1−1s=1s(s−1)x - \frac{1}{s} < \frac{1}{s-1} - \frac{1}{s} = \frac{1}{s(s-1)}, the denominator chosen in the next step must be greater than s(s−1)≥ss(s-1) \ge s. This shows that the algorithm produces a sequence of distinct denominators.
To prove termination of this algorithm we show that the numerators are strictly decreasing. From pq<1s−1\frac{p}{q} < \frac{1}{s-1} we obtain ps−p<qps - p < q, which is equivalent to ps−q<pps - q < p. Therefore,
0≤pq−1s=ps−qq 0 \le \frac{p}{q} - \frac{1}{s} = \frac{ps - q}{q}
has non-negative numerator smaller than pp, and this remains true when we write it in lowest terms. As we cannot have an infinite strictly decreasing sequence of non-negative integers, the algorithm terminates. This completes the lemma, giving the required decomposition for rational 0<x<10 < x < 1.

To solve the original question we wish to extend this result to rational x≥1x \ge 1, specifically to x=2020x = 2020. As the harmonic sequence diverges, for any x≥1x \ge 1 there is some integer m≥1m \ge 1 for which:
∑j=1m1j≤x<∑j=1m+11j. \sum_{j=1}^{m} \frac{1}{j} \le x < \sum_{j=1}^{m+1} \frac{1}{j}.
We then apply the result of the first part to
x−∑j=1m1j. x - \sum_{j=1}^{m} \frac{1}{j}.
As this is less than 11+m\frac{1}{1+m} we have distinctness and the result follows.

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