Maths Olympiad Prep

Library / /115 of 196

Number theory Difficulty 5.3 AIME, harder Prove it Soviet Union

Problem:

nn is an integer. Prove that the sum of all fractions 1/rs1/rs, where rr and ss are relatively prime integers satisfying 0<r<sn0 < r < s \leq n, r+s>nr + s > n, is 1/21/2.

Solution

Solution:

We use induction on nn. If n=2n = 2, then the only such fraction is r=1r = 1, s=2s = 2, giving 1/rs=1/21/rs = 1/2, so the result holds.

Suppose it holds for n1n - 1. As we move to nn, we lose the fractions with r+s=nr + s = n. The other fractions 1/rs1/rs which satisfy the conditions for n1n - 1 also satisfy the conditions for nn. We also gain the fractions with s=ns = n. These have sum =1/n= 1/n (sum 1/r1/r for all rr satisfying 0<r<n0 < r < n and rr relatively prime to nn).

But if rr is relatively prime to nn, then so is nrn - r, and nrn - r does not equal rr (otherwise rr divides nn). The pair 1/r1/r, 1/(nr)1/(n - r) has sum n/(r(nr))n/(r(n - r)). So the fractions with s=ns = n have sum equal to the sum of all 1/(r(nr))1/(r(n - r)) with 0<r<n0 < r < n and rr relatively prime to nn. But that is exactly the sum of the fractions lost. Thus the total is unchanged as we move from n1n - 1 to nn.

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.