It is known that for natural numbers $a,b,c,d$ and $n$ the following inequalities hold: $a+c<n$ and $a/b+c/d<1$. Prove that $a/b+c/d<1-1/n^3$.
Problem
Source: Ukrainian National Math Olympiad 4th round
Tags: inequalities, number theory unsolved, number theory
20.10.2014 09:24
We do some casework for this problem: First from the given information, since $n>a+c \geq 2$ it must be that $n \geq 3$. Also, $a<b$ and $c<d$ from the inequality $\frac{a}{b}+\frac{c}{d} <1$. Now, we break down into 4 cases and show that $\frac{a}{b}+\frac{c}{d} < 1-\frac{1}{n^3}$ holds in all the four cases. Case $1$: Let $b \geq n$ and $d \geq n$, then we have $ \frac{a}{b}+\frac{c}{d} \leq \frac{a}{n}+\frac{c}{n} = \frac{a+c}{n} < \frac{n-1}{n} = 1-\frac{1}{n} < 1-\frac{1}{n^3}$, so the inequality we want to prove holds. Case $2$:Let $b \leq n$ and $d \leq n$, then $\frac{a}{b}+\frac{c}{d} <1$ implies $ad+bc < bd$. i.e. $ad+bc+1 \leq bd$. Now we have $\frac{a}{b}+\frac{c}{d} \leq 1-\frac{1}{bd} = 1- \frac{1}{n^2} < 1 - \frac{1}{n^3}$. Case $3$: Let $b<n<d$. If $d \leq n^2$, then $bd < n^3$ and thus $\frac{a}{b} + \frac{c}{d} \leq 1-\frac{1}{bd} < 1-\frac{1}{n^3}$. If $d>n^2$, then $\frac{a}{b} \leq \frac{n-2}{n} = 1-\frac{2}{n^2}$ because $a<n-c \leq n-1$, so $a \leq n-2$. Now, suppose that $\frac{a}{b}+\frac{c}{d} \geq 1-\frac{1}{n^3}$. Then $1-\frac{a}{b} \leq \frac{c}{d} - \frac{1}{n^3} \leq \frac{1}{n}-\frac{2}{n^2}+\frac{1}{n^3} < \frac{1}{n}$. This suggests that $b > n(b-a) \geq n$ and thus contradicts the condition $b<n<d$ we established for Case $3$. Case $4$: Let $d<n<b$. If $b \leq n^2$, then $bd < n^3$ and thus $\frac{a}{b}+\frac{c}{d} \leq 1-\frac{1}{bd} <1-\frac{1}{n^3}$. If $b>n^2$, then $\frac{c}{d} \leq \frac{n-2}{n^2} < 1-\frac{1}{n^2} $ since $c<n-a \leq n-1$ so $c \leq n-2$.Similar to Case $3$, suppose that $\frac{a}{b}+\frac{c}{d} \geq 1-\frac{1}{n^3}$. Then $1-\frac{c}{d} \leq \frac{a}{b}-\frac{1}{n^3} \leq \frac{1}{n} -\frac{2}{n^2}+\frac{1}{n^3} < \frac{1}{n}$ and this results in $d>n(d-c) \geq n$ and thus a contradiction again. We have shown that the inequality we want to prove holds in all the cases above, and we are done.
03.01.2019 01:54
Torus121 wrote: Case $3$: Let $b<n<d$. ... If $d>n^2$, then $\frac{a}{b} \leq \frac{n-2}{n} = 1-\frac{2}{n^2}$ because $a<n-c \leq n-1$, so $a \leq n-2$. So you have maxed numerator and denominator in $\frac{a}{b}$ to obtain $\frac{a}{b} \leq \frac{n-2}{n}$? It doesn't sound like correct argumentation. Moreover, $\frac{n-2}{n} \neq 1-\frac{2}{n^2}$. And it looks like you don't need these estimates at all in subsequent inequalities.