6
$\begingroup$

I recently encountered this on a practice test

Find the smallest positive integer $n$ such that there exists an integer $m$ satisfying $0.33 < \frac{m}{n} < \frac{1}{3}$

My answer:

$$\begin{align}0.33 < \frac{m}{n} < \frac{1}{3}&\implies(\frac{33}{100} < \frac{m}{n})\land(\frac{m}{n}<\frac{1}{3}) \\ &\implies(33n<100m)\land(3m<n) \\\end{align}$$ and thus $n=3m+1$.

So $$\begin{align}33n<100m&\implies33(3m+1)<100m \\ &\implies 99m+33<100m\\ &\implies m>33\end{align}$$ Taking $m\geq34$, we find that $n=34\times3+1=103$

After the test, I had the following thoughts, which I do not know how to answer.

Questions

Will the solution for $n$ always yield the smallest $m$ possible?

Does this method (find minimum value of $n$ and substitute) work for all such problems? (where $m,n\in\mathbb{Z}$)

Can we generalise $n$ for all possible fraction ranges, and if so, will $n$ always be of a certain form compared to $a,b,c,$ and $d$? (where $\frac{a}{b}<\frac{m}{n}<\frac{c}{d}$).


note: sorry for asking multiple questions in one post (which I know some people frown on) but I feel posting multiple questions with the same 'introduction' (problem+proof) would clutter and be somewhat cumbersome.

$\endgroup$
  • $\begingroup$ In my opinion the smallest is $n=103$ because the smallest $m$ is $34$. Indeed if you solve for positive $n$ $$\frac{34}{n}<\frac{1}{3}$$ you get $n>102$ $\endgroup$ – Raffaele Oct 29 '17 at 11:01
  • $\begingroup$ @mathlove typo by me, thanks. I've also noticed that in our example $\frac{33}{100}<\frac{34}{103}<\frac{1}{3}$, the numerator of the middle fraction is the sum of the other numerators, and the denominator for the middle fraction is the sum of the other denominators. I wonder if this is a coincidence or not, though I won't put that into the question (three questions in one post is already plenty) $\endgroup$ – user472341 Oct 29 '17 at 11:03
  • $\begingroup$ The continued fraction for $\frac13$ is $(0;3)=(0;3,\infty)$ and the continued fraction for $0.33$ is $(0;3,33)$. The simplest between them is $(0;3,34)=\frac{34}{103}$. $\endgroup$ – robjohn Oct 29 '17 at 11:04
5
$\begingroup$

Can we generalise $n$ for all possible fraction ranges, and if so, will $n$ always be of a certain form compared to $a,b,c,$ and $d$? (where $\frac{a}{b}<\frac{m}{n}<\frac{c}{d}$).

This answer uses your method.

In the following, $a,b,c,d,m,n$ are positive integers.

$\frac ab\lt \frac mn\lt \frac cd$ is equivalent to $$na\lt mb\qquad\text{and}\qquad \frac{md}{c}\lt n$$

From the second inequality, we can set $n=\lfloor\frac{md}{c}\rfloor+1$ where $\lfloor x\rfloor$ is the greatest integer less than or equal to $x$.

So, from the first inequality, we get $$\left(\left\lfloor\frac{md}{c}\right\rfloor+1\right)a\lt mb\tag1$$

As a result, we can say that the smallest positive integer $n$ such that there exists an integer $m$ satisfying $\frac ab\lt\frac mn\lt\frac cd$ is given by$$\left\lfloor\frac{Md}{c}\right\rfloor+1$$ where $M$ is the smallest integer $m$ satisfying $(1)$.


If $c=1$, then the smallest positive integer $n$ such that there exists an integer $m$ satisfying $\frac ab\lt\frac mn\lt\frac 1d$ is given by$$\left(\left\lfloor\frac{a}{b-da}\right\rfloor+1\right)d+1$$

$\endgroup$
1
$\begingroup$

Yes to both of your questions. This is essentially the mediant for two terms in a Farey sequence. There is some deep theory here. Read up on Farey sequences for more information.

$\endgroup$
  • $\begingroup$ I had three questions - i'm assuming you're talking about the first two? either way, thanks for the links. $\endgroup$ – user472341 Oct 29 '17 at 11:09
  • 2
    $\begingroup$ The mediant is not always the smallest. Take for instance $\frac13$ and $\frac34$: the mediant is $\frac47$, which is between the two, but $\frac12$ is the fraction with the smallest denominator. $\endgroup$ – robjohn Oct 29 '17 at 11:12
  • 2
    $\begingroup$ I think the mediant is only relevant when the fractions are consecutive terms in some Farey sequence. In the example @robjohn gives, $1/3$ and $3/4$ are not consecutive terms in any Farey sequence. $\endgroup$ – Gerry Myerson Oct 29 '17 at 11:17
  • 1
    $\begingroup$ You can iterate the algorithm using the mediant. For 1/3, 3/4 we get 4/7 and then with 1/3, 4/7 we get 1/2. $\endgroup$ – i. m. soloveichik Oct 29 '17 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy