Determine whether there is a finite set of distinct positive integers such that
Problem 1474
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 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 for which ; this either gives equality, in which case we stop, or we start again with replacing . We need to show this algorithm terminates and gives a sequence of distinct denominators . We write the fraction in its lowest terms as with . If the result is immediate. Otherwise and there exists a unique integer such that
As , the denominator chosen in the next step must be greater than . 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 we obtain , which is equivalent to . Therefore,
has non-negative numerator smaller than , 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 .
To solve the original question we wish to extend this result to rational , specifically to . As the harmonic sequence diverges, for any there is some integer for which:
We then apply the result of the first part to
As this is less than we have distinctness and the result follows.