Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1996 OIM Problems/Problem 4"

(Created page with "== Problem == Given a natural number <math>n \ge 2</math>, consider all fractions of the form <math>\frac{1}{ab}</math>, where <math>a</math> and <math>b</math> are natural nu...")
 
(solution)
Line 11: Line 11:
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
We utilize induction on <math>n</math>. The base case <math>n=2</math> is obvious, so we let <math>n=k-1</math> for <math>k\ge3</math> and show that <math>n=k</math> works.
 +
 
 +
Notice that for every increase of <math>n</math>, the bounds shift. The ordered pairs <math>(a,b)</math> that once were allowed but are now not after an increase of <math>1</math> of <math>k-1</math> are the points such that <math>a+b=k</math>. On the other hand, the points that once were not allowed but now are permitted are the points that have <math>b=k</math>. All other pairs that were not allowed are still not allowed and vice versa. Then let <math>A</math> be the sum of the set of the <math>b=k</math> pairs and <math>B</math> be the sum of the set of the <math>a+b=k</math> 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 <math>b=k</math>; the sum would then be
 +
<cmath>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}</cmath>
 +
On the contrary, we consider the points such that <math>a+b=k</math>. First, notice that <math>a\ne b</math> since <math>a</math> and <math>b</math> are relatively prime (and  <math>a</math> and <math>b</math> cannot both equal <math>1</math> since <math>k\ge3</math>). Thus we can eliminate the condition <math>a<b</math> for a moment and can divide by <math>2</math> later to remove the excess cases. That being said, we can express our summation:
 +
<cmath>B=\frac{1}{2}\sum_{\substack{\text{gcd}(i,k-i)=1 \\ 0<i<k}}\frac{1}{i(k-i)}</cmath>
 +
Notice that since <math>\text{gcd}(i,k-i)=1</math>, then by the [[Euclidean Algorithm]], we must also have <math>\text{gcd}(i,k)=1</math>. Also,
 +
<cmath>\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)</cmath>
 +
Therefore:
 +
<cmath>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}</cmath>
 +
Thus <math>A=B</math>, implying the conclusion.
 +
 
 +
~ [https://artofproblemsolving.com/wiki/index.php/User:Eevee9406 eevee9406]
  
 
== See also ==
 
== See also ==
 
https://www.oma.org.ar/enunciados/ibe11.htm
 
https://www.oma.org.ar/enunciados/ibe11.htm

Revision as of 19:36, 26 March 2025

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}\] Thus $A=B$, implying the conclusion.

~ eevee9406

See also

https://www.oma.org.ar/enunciados/ibe11.htm

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1996_OIM_Problems/Problem_4&oldid=246116"