Maths Olympiad Prep

Track / Stage 5 / 394 of 400 #1474 of 2444

Problem 1474

AIME late
Number theory Difficulty 6.0 Prove it Irish Mathematical Olympiad · 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 1sx\frac{1}{s} \le x; this either gives equality, in which case we stop, or we start again with x1sx - \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 1p<q1 \le p < q. If p=1p = 1 the result is immediate. Otherwise 1<p<q1 < p < q and there exists a unique integer s2s \ge 2 such that
1sx<1s1. \frac{1}{s} \le x < \frac{1}{s-1}.
As x1s<1s11s=1s(s1)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(s1)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<1s1\frac{p}{q} < \frac{1}{s-1} we obtain psp<qps - p < q, which is equivalent to psq<pps - q < p. Therefore,
0pq1s=psqq 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 x1x \ge 1, specifically to x=2020x = 2020. As the harmonic sequence diverges, for any x1x \ge 1 there is some integer m1m \ge 1 for which:
j=1m1jx<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
xj=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.