1996 OIM Problems/Problem 4

Problem

Given a natural number $n \ge 2$ , consider all fractions of the form $\frac{1}{ab}$ , where $a$ and $b$ are natural numbers, prime to each other and such that

$a < b \le n$

$a + b > n$

Prove that for each $n$ the sum of these fractions is 1/2.

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

We utilize induction on $n$ . The base case $n=2$ is obvious, so we let $n=k-1$ for $k\ge3$ and show that $n=k$ works.

Notice that for every increase of $n$ , the bounds shift. The ordered pairs $(a,b)$ that once were allowed but are now not after an increase of $1$ of $k-1$ are the points such that $a+b=k$ . On the other hand, the points that once were not allowed but now are permitted are the points that have $b=k$ . All other pairs that were not allowed are still not allowed and vice versa. Then let $A$ be the sum of the set of the $b=k$ pairs and $B$ be the sum of the set of the $a+b=k$ pairs.

As a result, the sum of each of the two sets of fractions should be equal in order to preserve the overall value of the fraction. First, we consider the fractions of $b=k$ ; the sum would then be $A=\sum_{\substack{\text{gcd}(i,k)=1 \\ 0<i<k}}\frac{1}{ik}=\frac{1}{k}\sum_{\substack{\text{gcd}(i,k)=1 \\ 0<i<k}}\frac{1}{i}$ On the contrary, we consider the points such that $a+b=k$ . First, notice that $a\ne b$ since $a$ and $b$ are relatively prime (and $a$ and $b$ cannot both equal $1$ since $k\ge3$ ). Thus we can eliminate the condition $a<b$ for a moment and can divide by $2$ later to remove the excess cases. That being said, we can express our summation: $B=\frac{1}{2}\sum_{\substack{\text{gcd}(i,k-i)=1 \\ 0<i<k}}\frac{1}{i(k-i)}$ Notice that since $\text{gcd}(i,k-i)=1$ , then by the Euclidean Algorithm, we must also have $\text{gcd}(i,k)=1$ . Also, $\frac{1}{i(k-i)}=\frac{1}{k}\cdot\frac{k}{i(k-i)}=\frac{1}{k}\cdot\frac{i+(k-i)}{i(k-i)}=\frac{1}{k}\left(\frac{1}{i}+\frac{1}{k-i}\right)$ Therefore: $B=\frac{1}{2k}\sum_{\substack{\text{gcd}(i,k)=1 \\ 0<i<k}}\left(\frac{1}{i}+\frac{1}{k-i}\right)=\frac{1}{k}\sum_{\substack{\text{gcd}(i,k)=1 \\ 0<i<k}}\frac{1}{i}$ the last equality coming from symmetry since $\gcd(i,k)=\gcd(k-i,k)$ . Thus $A=B$ , implying the conclusion.

~ eevee9406

Page

Toolbox

Search

1996 OIM Problems/Problem 4

Problem

Solution

See also