Putnam 54/B6 solution

14th Putnam 1954

Problem B6

If x is a positive rational, show that we can find distinct positive integers a₁, a₂, ... , a_n such that x = ∑ 1/a_i.

Solution

Hard.

Rather surprisingly, the simplest possible algorithm - the greedy algorithm - works: take a_n to be the smallest integer not already chosen so that the sum does not exceed x. This terminates after a finite number of steps.

Note that the numbers involved can be quite large even in simple cases. For example: 4 = 1/1 + 1/2 + 1/3 + ... + 1/30 + 1/200 + 1/77706 + 1/16532869712 + 1/3230579689970657935732 + 1/36802906522516375115639735990520502954652700

The key idea is that the numerator of the difference gets smaller each time and hence the process must terminate.

First, we have to get the difference under 1. So take m such that 1 + 1/2 + ... + 1/m ≤ x < 1 + 1/2 + ... + 1/(m+1). This is possible since the harmonic series diverges. If we have equality, then we are home. If not then the difference x - (1 + 1/2 + ... + 1/m) < 1/(m+1).

Let the difference x - (1/a₁ + 1/a₂ + ... + 1/a_n) be d_n = r_n/s_n (where r_n and s_n are integers).

So we may assume that we have picked a₁, ... , a_n and that d_n < 1/(a_n + 1). We now take a_n+1 so that 1/a_n+1 ≤ d_n < 1/(a_n+1 - 1). Now d_n+1 = d_n - 1/a_n+1 = (r_na_n+1 - s_n)/(s_na_n+1). This expression may not be in lowest terms, but it is certainly sufficient to show that (r_na_n+1 - s_n) < r_n or d_na_n+1 - 1 < d_n. But that is true since d_n(a_n+1 - 1) < 1. Finally, we notice that d_n+1 < 1/(a_n+1 + 1) is equivalent to d_n - 1/a_n+1 < 1/(a_n+1 + 1), which is true since 1/(a_n+1 - 1) - 1/a_n+1 < 1/(a_n+1 + 1), since a_n+1 > 1.

14th Putnam 1954