Smallest value of $b$ when $0<\left\lvert \frac{a}{b}-\frac{3}{5}\right\rvert\leq\frac{1}{150}$

Question

Problem

For positive integers $a$ and $b$, $$0<\left\lvert \dfrac{a}{b}-\dfrac{3}{5}\right\rvert\leq\dfrac{1}{150}$$ What is the smallest possible value of $b$? (BdMO 2021 Junior P10)

My approach

If $\dfrac{a}{b}>\dfrac{3}{5}$, then $\dfrac{a}{b} \leq \dfrac{91}{150}$ and if $\dfrac{a}{b}<\dfrac{3}{5}$, then $\dfrac{a}{b} \geq \dfrac{89}{150}$.

Hence the maximum value of $\dfrac{a}{b}$ is $\dfrac{91}{150}$. And $\dfrac{a}{b}$ is maximum when $b$ is the smallest.

So, I thought $150$ would be the smallest value of $b$.

But my friend said that the smallest value of $b$ would be $32$ as $\left\lvert \dfrac{19}{32}- \dfrac{3}{5}\right\rvert= \dfrac{1}{160}$ works actually. Though he said that he found this intuitively.

So, how to solve the problem with proper procedure?

Answer 1

Response to OP's comment regarding triangle inequality : you used the triangle inequality to prove that $\frac{89}{150} < \frac ab < \frac{91}{150}$, perhaps you and the other commenter would like elaboration on that, in which case I'll provide it upon request.

I must critique your approach as well, since this is to correct particular issues.

Indeed, note that even if $\frac {89}{150}<\frac{a}{b} < \frac{91}{150}$ , that doesn't necessarily mean that there cannot be any other fraction of smaller denominator sitting between them. To take a very simple example, $\frac{8}{11} < \frac 34 < \frac {9}{11}$. Indeed, numbers sitting in between each other, even in tiny gaps has nothing to do with the size of the denominator, as I illustrate. You can probably find even more extreme examples of this phenomena.

Therefore, the way to do this question would instead be to observe (in hindsight, since I know the answer is $32$ : but even otherwise it's a very decent approach) that once you take the lcm (note : I took the product in the hint below), you want to be looking at the two fractions and comparing their numerators and denominators.

---

More precisely , note that following the creation of a commmon denominator , if $\frac{|5a-3b|}{5b} \leq \frac 1{150}$, then since $|5a-3b| \geq 1$ we must have $5b \geq 150$ i.e. $b \geq 30$, otherwise $\frac{|5a-3b|}{5b}$ would have a bigger numerator and smaller denominator than $\frac 1{150}$, which would make it a bigger fraction.

Once you have that, you just want to check from $b=30$ onwards, and you hit $32$.

Note : One can go for the lcm in the denominator as well : since $5$ is prime, for example, the lcm can be either the product $5b$, or just $b$ itself. Of course this is not required since we are still done by taking the product itself, but it's still useful. For example, for $b=30$ you wouldn't use the product, you'd just have $\frac{|a-18|}{30}$ instead of the other expression, and then obviously moving $a$ either side moves the fraction off by at least $\frac 1{30}$ so $30$ doesn't work, so this is where that observation is useful.

Answer 2

Clearing denominators, we are effectively asked to find minimal $b$ s.t. $0 < |150a-90b| \leqslant b$, for $a, b \in \mathbb N$.

Note as the gcd $(150,90)=30$, the middle term will at least be $30$ (or a larger multiple), so $b\geqslant 30$.

It remains to to check if $150 \mid (30\pm 90b)$ or equivalently if $b \equiv \pm2 \pmod 5$ for $b\geqslant 30$ to conclude $b_{min}=32$.

---

The following constructive approach avoids brute force.

From Bézout's identity $150\cdot(-1)+90\cdot2=30\tag{1}$ and the obvious $150\cdot(-3)+90\cdot5=0\tag{2}$ we can use the latter equation to scale up $b$ above $30$ without adding to the RHS error term. Further, as we noted $b \equiv \pm2 \pmod 5$, all solutions will be of form equation $(2)\times n \,\pm$ equation $(1)$. If there is any solution which is not of this form, subtract $(2)$ multiple times from it to get a contradiction with $b \equiv \pm 2\pmod 5$.

Now as $5n\pm2 \geqslant 30$ has minimal solution $n=6$, equation $(2)\times 6\,+$ equation $(1)$ gives $150\cdot(-19)+90\cdot(32)=30 < 32 \implies b_{min}=32$.

Answer 3

HINT:

If $\frac{a}{b}$ satisfies the condition then $$|5 a - 3 b| = 1$$ the explanation being that in the parallelogram on the vectors $(3,5)$ and $(a,b)$ there should be no other integer points excepts the vertices. Now, the solutions of $$5 a - 3 b = 1$$ are $$a = 2 + 3 t \\ b = 3 + 5 t$$ while those of $$5 a - 3 b = -1$$ are $$a = 1 + 3 t \\ b = 2 + 5 t $$

Now if $|5 a - 3 b| = 1$, then

$$\left|\frac{a}{b} - \frac{3}{5}\right| = \frac{1}{5 b}$$

Therefore, we need $$5 b \ge 150$$, or $$b \ge 30$$

Now, the smallest $b \equiv 2 \text{ or } 3 \mod 5$ and $\ge 30$ is $32$ ( and not $33$).

Answer 4

Once you get that $\frac{a}{b}$ is between $\frac{89}{150}$ and $\frac{91}{150}$, you may simply consider the continued fractions of these rational numbers:

$$ \frac{89}{150}=[0;1,1,2,5,1,1,2] $$ $$ \frac{91}{150}=[0;1,1,1,1,5,2,2] $$ In particular we are looking for a fraction of the form $[0;1,1,2,\alpha]$ with $\alpha > [5;1,1,2]=\frac{28}{5}$.
In order to have the smallest denominator the most effective choice is just $\alpha=6$, and $$ [0;1,1,2,6]=\frac{19}{\color{blue}{32}}.$$