# 2018 AMC 12B Problems/Problem 17

## Problem

Let $p$ and $q$ be positive integers such that $$\frac{5}{9} < \frac{p}{q} < \frac{4}{7}$$and $q$ is as small as possible. What is $q-p$?

$\textbf{(A) } 7 \qquad \textbf{(B) } 11 \qquad \textbf{(C) } 13 \qquad \textbf{(D) } 17 \qquad \textbf{(E) } 19$

## Solution 1

We claim that, between any two fractions $a/b$ and $c/d$, if $bc-ad=1$, the fraction with smallest denominator between them is $\frac{a+c}{b+d}$. To prove this, we see that

$$\frac{1}{bd}=\frac{c}{d}-\frac{a}{b}=\left(\frac{c}{d}-\frac{p}{q}\right)+\left(\frac{p}{q}-\frac{a}{b}\right) \geq \frac{1}{dq}+\frac{1}{bq},$$ which reduces to $q\geq b+d$. We can easily find that $p=a+c$, giving an answer of $\boxed{\textbf{(A)}\ 7}$.

## Solution 2 (requires justification)

Assume that the difference $\frac{p}{q} - \frac{5}{9}$ results in a fraction of the form $\frac{1}{9q}$. Then,

$9p - 5q = 1$

Also assume that the difference $\frac{4}{7} - \frac{p}{q}$ results in a fraction of the form $\frac{1}{7q}$. Then,

$4q - 7p = 1$

Solving the system of equations yields $q=16$ and $p=9$. Therefore, the answer is $\boxed{\textbf{(A)}\ 7}$

## Solution 3

Cross-multiply the inequality to get $$35q < 63p < 36q.$$

Then, $$0 < 63p-35q < q,$$ $$0 < 7(9p-5q) < q.$$

Since $p$, $q$ are integers, $9p-5q$ is an integer. To minimize $q$, start from $9p-5q=1$, which gives $p=\frac{5q+1}{9}$. This limits $q$ to be greater than $7$, so test values of $q$ starting from $q=8$. However, $q=8$ to $q=14$ do not give integer values of $p$.

Once $q>14$, it is possible for $9p-5q$ to be equal to $2$, so $p$ could also be equal to $\frac{5q+2}{9}.$ The next value, $q=15$, is not a solution, but $q=16$ gives $p=\frac{5\cdot 16 + 1}{9} = 9$. Thus, the smallest possible value of $q$ is $16$, and the answer is $16-9= \boxed{\textbf{(A)}\ 7}$.

## Solution 4

Graph the regions $y > \frac{5}{9}x$ and $y < \frac{4}{7}x$. Note that the lattice point $(16,9)$ is the smallest magnitude one which appears within the region bounded by the two graphs. Thus, our fraction is $\frac{9}{16}$ and the answer is $16-9= \boxed{\textbf{(A)}\ 7}$.

Remark: This also gives an intuitive geometric proof of the mediant using vectors.

## Solution 5 (Using answer choices to prove mediant)

As the other solutions do, the mediant $=\frac{9}{16}$ is between the two fractions, with a difference of $\boxed{\textbf{(A)}\ 7}$. Suppose that the answer was not $A$, then the answer must be $B$ or $C$ as otherwise $p$ would be negative. Then, the possible fractions with lower denominator would be $\frac{k-11}{k}$ for $k=12,13,14,15$ and $\frac{k-13}{k}$ for $k=14,15,$ which are clearly not anywhere close to $\frac{4}{7}\approx 0.6$

## Solution 6

Inverting the given inequality we get $$\frac{7}{4} < \frac{q}{p} < \frac{9}{5}$$

which simplifies to $$35p < 20q < 36p$$

We can now substitute $q = p + k$. Note we need to find $k$.

$$35p < 20p + 20k < 36p$$

which simplifies to $$15p < 20k < 16p$$

Cleary $p$ is greater than $k$. We will now substitute $p = k + x$ to get

$$15k + 15x < 20k < 16k + 16x$$

The inequality $15k + 15x < 20k$ simplifies to $3x < k$. The inequality $20k < 16k + 16x$ simplifies to $k < 4x$. Combining the two we get $$3x < k < 4x$$

Since $x$ and $k$ are integers, the smallest values of $x$ and $k$ that satisfy the above equation are $2$ and $7$ respectively. Substituting these back in, we arrive with an answer of $\boxed{\textbf{(A)}\ 7}$.

## Solution 7

Start with $\frac{5}{9}$. Repeat the following process until you arrive at the answer: if the fraction is less than or equal to $\frac{5}{9}$, add $1$ to the numerator; otherwise, if it is greater than or equal to $\frac{4}{7}$, add one $1$ to the denominator. We have:

$$\frac{5}{9}, \frac{6}{9}, \frac{6}{10}, \frac{6}{11}, \frac{7}{11}, \frac{7}{12}, \frac{7}{13}, \frac{8}{13}, \frac{8}{14}, \frac{8}{15}, \frac{9}{15}, \frac{9}{16}$$

$16 - 9 = \boxed{\textbf{(A)}\ 7}$.

## Solution 8

Because q and p are positive integers with $p, we can let $q=p+k$ where $k\in{\mathbb{Z}}$. Now, the problem condition reduces to

$\frac{5}{9}<\frac{p}{p+k}<\frac{4}{7}$

Our first inequality is $\frac{5}{9}<\frac{p}{p+k}$ which gives us $5p+5k<9p\implies \frac{5}{4}k.

Our second inequality is $\frac{p}{p+k}<\frac{4}{7}$ which gives us $7p<4p+4k\implies p<\frac{4}{3}k$.

Hence, $\frac{5}{4}k.

It is clear that we are aiming to find the least positive integer value of k such that there is at least one value of p that satisfies the inequality.

Now, simple casework through the answer choices of the problem reveals that $q-p=p+k-p=k\implies k\ge{\boxed{7}}$.

## Solution 9 (Quick inspection)

Checking possible fractions within the interval can get us to the answer, but only if we do it with more skill. The interval can also be written as $0.5556. This represents fraction with the numerator a little bit more than half the denominator. Every fraction we consider must not exceed this range.

The denominators to be considered are $9,10,11,12...$. We check $\frac{6}{10}, \frac{6}{11}, \frac{7}{13}, \frac{8}{15}, \frac{9}{16}$. At this point we know that we've got our fraction and our answer is $16-9=\boxed{\textbf{A } 7}$

The inspection was made faster by considering the fact that $\frac{a+1}{b+1}>\frac{a}{b}$. So, once a fraction was gotten which was greater than $\frac{4}{7}$ we jump to the next denominator and also make sure we consider fractions with higher positive difference between the denominator and numerator, making sure also that the numerator is greater than half of the denominator.

~OlutosinNGA