Track / Stage 5 / 203 of 400 #1283 of 2444

Problem 1283

AIME late

Number theory Difficulty 5.4 Prove it Iberoamerican Mathematical Olympiad · Ibero-American Mathematical Olympiad

$n > 2$ is an integer. Consider the pairs $(a, b)$ of relatively prime positive integers, such that $a < b \leq n$ and $a + b > n$ . Show that the sum of $1 / ab$ taken over all such pairs is $1 / 2$ .

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.

Official solution

Solution:

Induction on $n$ . It is obvious for $n = 3$ , because the only pairs are $(1, 3)$ and $(2, 3)$ , and $1 / 3 + 1 / 6 = 1 / 2$ .

Now suppose it is true for $n$ . As we move to $n + 1$ , we introduce the new pairs $(a, n + 1)$ with $a$ relatively prime to $n + 1$ and we lose the pairs $(a, n + 1 - a)$ with $a$ relatively prime to $n + 1 - a$ and hence to $n + 1$ .

So for each $a$ relatively prime to $n + 1$ and $a < (n + 1) / 2$ we gain $(a, n + 1)$ and $(n + 1 - a, n + 1)$ and lose $(a, n + 1 - a)$ . But

$\frac{1}{a(n + 1)} + \frac{1}{(n + 1 - a)(n + 1)} = \frac{n + 1 - a + a}{a(n + 1 - a)(n + 1)} = \frac{1}{a(n + 1 - a)}.$

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