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 "2018 AMC 12B Problems/Problem 17"

(→‎Solution 10 (testing answer choices))
m (→‎Solution 3 (Substitution))
 
(42 intermediate revisions by 3 users not shown)
Line 5: Line 5:
 
<math>\textbf{(A) } 7 \qquad \textbf{(B) } 11 \qquad \textbf{(C) } 13 \qquad \textbf{(D) } 17 \qquad \textbf{(E) } 19 </math>
 
<math>\textbf{(A) } 7 \qquad \textbf{(B) } 11 \qquad \textbf{(C) } 13 \qquad \textbf{(D) } 17 \qquad \textbf{(E) } 19 </math>
  
−
== Solution 1 ==
+
== Solution 1 (Generalization) ==
  
−
We claim that, between any two fractions <math>a/b</math> and <math>c/d</math>, if <math>bc-ad=1</math>, the fraction with smallest denominator between them is <math>\frac{a+c}{b+d}</math>. To prove this, we see that
+
More generally, let <math>a,b,c,d,p,</math> and <math>q</math> be positive integers such that <math>bc-ad=1</math> and <cmath>\frac ab < \frac pq < \frac cd.</cmath>
 +
From <math>\frac ab < \frac pq,</math> we have <math>bp-aq>0,</math> or <cmath>bp-aq\geq1. \hspace{15mm} (1)</cmath>
 +
From <math>\frac pq < \frac cd,</math> we have <math>cq-dp>0,</math> or <cmath>cq-dp\geq1. \hspace{15mm} (2)</cmath>
 +
Since <math>bc-ad=1,</math> note that:
 +
<ol style="margin-left: 1.5em;">
 +
  <li>Multiplying <math>(1)</math> by <math>d,</math> multiplying <math>(2)</math> by <math>b,</math> and adding the results, we get <math>q\geq b+d.</math></li><p>
 +
  <li>Multiplying <math>(1)</math> by <math>c,</math> multiplying <math>(2)</math> by <math>a,</math> and adding the results, we get <math>p\geq a+c.</math></li><p>
 +
</ol>
 +
To minimize <math>q,</math> we set <math>q=b+d,</math> from which <math>p=a+c.</math> Together, we can prove that <cmath>\frac{a+c-1}{b+d}\leq\frac ab<\frac{a+c}{b+d}<\frac cd\leq\frac{a+c+1}{b+d}. \hspace{15mm} (\bigstar)</cmath>
 +
For this problem, we have <math>a=5,b=9,c=4,</math> and <math>d=7,</math> so <math>p=a+c=9</math> and <math>q=b+d=16.</math> The answer is <math>q-p=\boxed{\textbf{(A) } 7}.</math>
  
−
<cmath>\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},</cmath>
+
<u><b>Remark</b></u>
−
which reduces to <math>q\geq b+d</math>. We can easily find that <math>p=a+c</math>, giving an answer of <math>\boxed{\textbf{(A)}\ 7}</math>.
 
  
−
==Solution 2 (requires justification)==
+
We will prove each part of the compound inequality in <math>(\bigstar):</math>
 +
<ol style="margin-left: 1.5em;">
 +
  <li><math>\frac{a+c-1}{b+d}\leq\frac ab</math> and <math>\frac cd\leq\frac{a+c+1}{b+d}</math></li><p>
 +
Let <math>\frac ab=k,</math> so <math>a=bk.</math> The precondition <math>bc-ad=1</math> becomes <math>bc-bdk=1,</math> so <math>c-dk=\frac1b.</math> <p>
 +
It follows that <cmath>\frac{a+c-1}{b+d}=\frac{bk+c-1}{b+d}=k+\frac{c-dk-1}{b+d}=k+\frac{\frac1b-1}{b+d}=k+\frac{1-b}{b(b+d)}\leq k.</cmath> Moreover, the equality case occurs if and only if <math>b=1.</math> <p>
 +
We can prove <math>\frac cd\leq\frac{a+c+1}{b+d}</math> by the same process. Similarly, the equality case occurs if and only if <math>d=1.</math>
 +
  <li><math>\frac ab<\frac{a+c}{b+d}<\frac cd</math></li><p>
 +
Let <math>\frac ab=k_1</math> and <math>\frac cd=k_2,</math> so <math>a=bk_1</math> and <math>c=dk_2.</math> <p>
 +
It follows that
 +
<cmath>\begin{alignat*}{10}
 +
\frac{a+c}{b+d}&=\frac{bk_1+dk_2}{b+d}&&=k_1+\frac{dk_2-dk_1}{b+d}&&=k_1+\frac{d(k_2-k_1)}{b+d}&&>k_1, \\
 +
\frac{a+c}{b+d}&=\frac{bk_1+dk_2}{b+d}&&=k_2+\frac{bk_1-bk_2}{b+d}&&=k_2+\frac{b(k_1-k_2)}{b+d}&&<k_2.
 +
\end{alignat*}</cmath>
 +
Moreover, this part of <math>(\bigstar)</math> is independent of the precondition <math>bc-ad=1.</math>
 +
</ol>
 +
~MRENTHUSIASM
  
−
Assume that the difference <math>\frac{p}{q} - \frac{5}{9}</math> results in a fraction of the form <math>\frac{1}{9q}</math>. Then,
+
== Solution 2 (Generalization) ==
 +
Define variables <math>a,b,c,d,p,</math> and <math>q</math> as Solution 1 does. Moreover, this solution refers to inequalities <math>(1)</math> and <math>(2)</math> in Solution 1.
  
−
<math>9p - 5q = 1</math>
+
Note that
 +
<cmath>\begin{align*}
 +
\frac{1}{bd}&=\frac{bc-ad}{bd} \\
 +
&=\frac cd - \frac ab \\
 +
&=\left(\frac cd - \frac pq\right)+\left(\frac pq - \frac ab\right) \\
 +
&=\frac{cq-dp}{dq}+\frac{bp-aq}{bp} \\
 +
&\geq\frac{1}{dq}+\frac{1}{bq}.
 +
\end{align*}</cmath>
 +
Multiplying both sides of <math>\frac{1}{bd}\geq\frac{1}{dq}+\frac{1}{bq}</math> by <math>bdq,</math> we get <math>q\geq b+d.</math>
  
−
Also assume that the difference <math>\frac{4}{7} - \frac{p}{q}</math> results in a fraction of the form <math>\frac{1}{7q}</math>. Then,
+
For this problem, we have <math>a=5,b=9,c=4,</math> and <math>d=7,</math> so <math>q\geq b+d=16.</math> At <math>q=16,</math> we have <cmath>\frac{8}{16}<\frac59<\frac{9}{16}<\frac47<\frac{10}{16},</cmath>
 +
from which <math>p=9.</math> Therefore, the answer is <math>q-p=\boxed{\textbf{(A) } 7}.</math>
  
−
<math>4q - 7p = 1</math>
+
Alternatively, refer to the <u><b>Remark</b></u> section in Solution 1 for further generalizations.
  
−
Solving the system of equations yields <math>q=16</math> and <math>p=9</math>. Therefore, the answer is <math>\boxed{\textbf{(A)}\ 7}</math>
+
~pieater314159 ~MRENTHUSIASM
  
−
==Solution 3==
+
==Solution 3 (Substitution)==
−
Cross-multiply the inequality to get <cmath>35q < 63p < 36q.</cmath>
 
  
−
Then,
+
Inverting the given inequality we get <cmath>\frac{7}{4} < \frac{q}{p} < \frac{9}{5},</cmath>
−
<cmath>0 < 63p-35q < q,</cmath>
+
which simplifies to <cmath>35p < 20q < 36p.</cmath>
−
<cmath>0 < 7(9p-5q) < q.</cmath>
+
We can now substitute <math>q = p + k.</math> Note we need to find <math>k:</math> <cmath>35p < 20p + 20k < 36p,</cmath>
 +
which simplifies to <cmath>15p < 20k < 16p.</cmath>
 +
Clearly <math>p>k.</math> We will now substitute <math>p = k + x</math> to get <cmath>15k + 15x < 20k < 16k + 16x.</cmath>
 +
The inequality <math>15k + 15x < 20k</math> simplifies to <math>3x < k.</math>
  
−
Since <math>p</math>, <math>q</math> are integers, <math>9p-5q</math> is an integer. To minimize <math>q</math>, start from <math>9p-5q=1</math>, which gives <math>p=\frac{5q+1}{9}</math>. This limits <math>q</math> to be greater than <math>7</math>, so test values of <math>q</math> starting from <math>q=8</math>. However, <math>q=8</math> to <math>q=14</math> do not give integer values of <math>p</math>.
+
The inequality <math>20k < 16k + 16x</math> simplifies to <math>k < 4x.</math>
  
−
Once <math>q>14</math>, it is possible for <math>9p-5q</math> to be equal to <math>2</math>, so <math>p</math> could also be equal to <math>\frac{5q+2}{9}.</math> The next value, <math>q=15</math>, is not a solution, but <math>q=16</math> gives <math>p=\frac{5\cdot 16 + 1}{9} = 9</math>. Thus, the smallest possible value of <math>q</math> is <math>16</math>, and the answer is <math>16-9= \boxed{\textbf{(A)}\ 7}</math>.
+
Combining the two inequalities, we get <cmath>3x < k < 4x.</cmath>
 +
Since <math>x</math> and <math>k</math> are integers, the smallest values of <math>x</math> and <math>k</math> that satisfy the above equation are <math>2</math> and <math>7</math> respectively. Substituting these back in, we arrive with an answer of <math>\boxed{\textbf{(A) } 7}.</math>
  
−
==Solution 4==
+
==Solution 4 (Substitution)==
−
Graph the regions <math>y > \frac{5}{9}x</math> and <math>y < \frac{4}{7}x</math>. Note that the lattice point <math>(16,9)</math> is the smallest magnitude one which appears within the region bounded by the two graphs. Thus, our fraction is <math>\frac{9}{16}</math> and the answer is <math>16-9= \boxed{\textbf{(A)}\ 7}</math>.
+
Because <math>q</math> and <math>p</math> are positive integers with <math>p<q,</math> we can let <math>q=p+k</math> where <math>k\in{\mathbb{Z}}.</math> Now, the problem condition reduces to <cmath>\frac{5}{9}<\frac{p}{p+k}<\frac{4}{7}.</cmath>
  
−
Remark: This also gives an intuitive geometric proof of the mediant using vectors.
+
Our first inequality is <math>\frac{5}{9}<\frac{p}{p+k},</math> which gives us <math>5p+5k<9p,</math> or <math>\frac{5}{4}k<p.</math>
  
−
==Solution 5 (Using answer choices to prove mediant)==
+
Our second inequality is <math>\frac{p}{p+k}<\frac{4}{7},</math> which gives us <math>7p<4p+4k,</math> or <math>p<\frac{4}{3}k.</math>
−
As the other solutions do, the mediant <math>=\frac{9}{16}</math> is between the two fractions, with a difference of <math>\boxed{\textbf{(A)}\ 7}</math>. Suppose that the answer was not <math>A</math>, then the answer must be <math>B</math> or <math>C</math> as otherwise <math>p</math> would be negative. Then, the possible fractions with lower denominator would be <math>\frac{k-11}{k}</math> for <math>k=12,13,14,15</math> and <math>\frac{k-13}{k}</math> for <math>k=14,15,</math> which are clearly not anywhere close to <math>\frac{4}{7}\approx 0.6</math>
 
  
−
==Solution 6==
+
Hence, we have <math>\frac{5}{4}k<p<\frac{4}{3}k,</math> or <math>15k<12p<16k.</math>
  
−
Inverting the given inequality we get
+
It is clear that we are aiming to find the least positive integer value of <math>k</math> such that there is at least one value of <math>p</math> that satisfies the inequality.
−
<cmath>\frac{7}{4} < \frac{q}{p} < \frac{9}{5}</cmath>
 
  
−
which simplifies to <cmath>35p < 20q < 36p</cmath>
+
Now, simple casework through the answer choices of the problem reveals that <math>q-p=p+k-p=k\ge{\boxed{\textbf{(A) } 7}}.</math>
  
−
We can now substitute <math>q = p + k</math>. Note we need to find <math>k</math>.
+
==Solution 5 (Manipulation)==
 +
We subtract <math>\frac{1}{2}</math> from both sides of the equation, so <cmath>\frac{1}{18} < \frac{p}{q}-\frac{1}{2} < \frac{1}{14}.</cmath> Then for <math>q</math> to be as small as possible, <math>\frac{p}{q}-\frac{1}{2}</math> has to be <math>\frac{1}{16},</math> so <math>\frac{p}{q}</math> is <math>\frac{9}{16}</math> and <math>q-p</math> is <math>\boxed{\textbf{(A) } 7}.</math>
  
−
<cmath>35p < 20p + 20k < 36p</cmath>
+
~purplepenguin2
  
−
which simplifies to <cmath>15p < 20k < 16p</cmath>
+
==Solution 6 (Solves for p)==
 +
Cross-multiply the inequality to get <cmath>35q < 63p < 36q.</cmath>
 +
Then, we have <math>0 < 63p-35q < q,</math> or <cmath>0 < 7(9p-5q) < q.</cmath>
 +
Since <math>p</math> and <math>q</math> are integers, <math>9p-5q</math> is an integer. To minimize <math>q,</math> start from <math>9p-5q=1,</math> which gives <math>p=\frac{5q+1}{9}.</math> This limits <math>q</math> to be greater than <math>7,</math> so test values of <math>q</math> starting from <math>q=8.</math> However, <math>q=8</math> to <math>q=14</math> do not give integer values of <math>p.</math>  
  
−
Cleary <math>p</math> is greater than <math>k</math>. We will now substitute <math>p = k + x</math> to get
+
Once <math>q>14,</math> it is possible for <math>9p-5q</math> to be equal to <math>2,</math> so <math>p</math> could also be equal to <math>\frac{5q+2}{9}.</math> The next value, <math>q=15,</math> is not a solution, but <math>q=16</math> gives <math>p=\frac{5\cdot 16 + 1}{9} = 9.</math> Thus, the smallest possible value of <math>q</math> is <math>16,</math> and the answer is <math>16-9= \boxed{\textbf{(A) } 7}.</math>
  
−
<cmath>15k + 15x < 20k < 16k + 16x</cmath>
+
==Solution 7 (Inspection)==
 +
Start with <math>\frac{5}{9}.</math> Repeat the following process until you arrive at the answer: if the fraction is less than or equal to <math>\frac{5}{9},</math> add <math>1</math> to the numerator; otherwise, if it is greater than or equal to <math>\frac{4}{7},</math> add one <math>1</math> to the denominator. We have <cmath>\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}.</cmath>
  
−
The inequality <math>15k + 15x < 20k</math> simplifies to <math>3x < k</math>.
+
Therefore, the answer is <math>16 - 9 = \boxed{\textbf{(A) } 7}.</math>
−
The inequality <math>20k < 16k + 16x</math> simplifies to <math>k < 4x</math>.
 
−
Combining the two we get
 
−
<cmath>3x < k < 4x</cmath>
 
  
−
Since <math>x</math> and <math>k</math> are integers, the smallest values of <math>x</math> and <math>k</math> that satisfy the above equation are <math>2</math> and <math>7</math> respectively. Substituting these back in, we arrive with an answer of <math>\boxed{\textbf{(A)}\ 7}</math>.
+
== Solution 8 (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 <math>0.5556<x<0.5714.</math> This represents fraction with the numerator a little bit more than half the denominator. Every fraction we consider must not exceed this range.  
  
−
==Solution 7==
+
The denominators to be considered are <math>9,10,11,12,\ldots.</math> We check <math>\frac{6}{10}, \frac{6}{11}, \frac{7}{12}, \frac{7}{13}, \frac{8}{15}, \frac{9}{16}.</math> At this point we know that we've got our fraction and our answer is <math>16-9=\boxed{\textbf{(A) } 7}.</math>
−
Start with <math>\frac{5}{9}</math>. Repeat the following process until you arrive at the answer: if the fraction is less than or equal to <math>\frac{5}{9}</math>, add <math>1</math> to the numerator; otherwise, if it is greater than or equal to <math>\frac{4}{7}</math>, add one <math>1</math> to the denominator. We have:
 
  
−
<cmath>\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}</cmath>
+
The inspection was made faster by considering the fact that <math>\frac{a+1}{b+1}>\frac{a}{b}.</math>
  
−
<math>16 - 9 = \boxed{\textbf{(A)}\ 7}</math>.
+
So, once a fraction was gotten which was greater than <math>\frac{4}{7}</math> we jump to the next denominator.  
  
−
==Solution 8==
+
We then make sure we consider fractions with higher positive difference between the denominator and numerator. And we also do not forget that the numerator must be greater than half of the denominator.
−
Because q and p are positive integers with <math>p<q</math>, we can let <math>q=p+k</math> where <math>k\in{\mathbb{Z}}</math>. Now, the problem condition reduces to
 
  
−
<math>\frac{5}{9}<\frac{p}{p+k}<\frac{4}{7}</math>
+
(<math>\frac{8}{14}</math> was obviously skipped because it is equal to <math>\frac{4}{7}.</math>)
  
−
Our first inequality is <math>\frac{5}{9}<\frac{p}{p+k}</math> which gives us <math>5p+5k<9p\implies \frac{5}{4}k<p</math>.
+
~OlutosinNGA
  
−
Our second inequality is <math>\frac{p}{p+k}<\frac{4}{7}</math> which gives us <math>7p<4p+4k\implies p<\frac{4}{3}k</math>.
+
==Solution 9 (Graphing)==
 +
Graph the regions <math>y > \frac{5}{9}x</math> and <math>y < \frac{4}{7}x.</math> Note that the lattice point <math>(16,9)</math> is the smallest magnitude one which appears within the region bounded by the two graphs. Thus, our fraction is <math>\frac{9}{16}</math> and the answer is <math>16-9= \boxed{\textbf{(A) } 7}.</math>
  
−
Hence, <math>\frac{5}{4}k<p<\frac{4}{3}k\implies 15k<12p<16k</math>.
+
Remark: This also gives an intuitive geometric proof of the mediant using vectors.
  
−
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.
+
==Solution 10 (Answer Choices)==
 +
As the other solutions do, the mediant <math>\frac{9}{16}</math> is between the two fractions, with a difference of <math>\boxed{\textbf{(A) } 7}.</math> Suppose that the answer was not <math>\textbf{(A)},</math> then the answer must be <math>\textbf{(B)}</math> or <math>\textbf{(C)}</math> as otherwise <math>p</math> would be negative. Then, the possible fractions with lower denominator would be <math>\frac{k-11}{k}</math> for <math>k=12,13,14,15</math> and <math>\frac{k-13}{k}</math> for <math>k=14,15,</math> which are clearly not anywhere close to <math>\frac{4}{7}\approx 0.6.</math>
  
−
Now, simple casework through the answer choices of the problem reveals that <math>q-p=p+k-p=k\implies k\ge{\boxed{7}}</math>.
+
==Solution 11 (Answer Choices)==
  
−
== Solution 9 (Quick inspection) ==
+
In ascending order, we can use answer choices, values for <math>q-p,</math> as a method of figuring out our answer through the means of substitution. Let the assumed difference be <math>7.</math> Then, <math>p=q-7.</math> We thus have two inequalities: <math>\frac{5}{9} < \frac{q-7}{q}</math> and <math>\frac{q-7}{q} < \frac{4}{7}.</math>
−
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 <math>0.5556<x<0.5714</math>. 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 <math>9,10,11,12...</math>. We check <math>\frac{6}{10}, \frac{6}{11}, \frac{7}{12}, \frac{7}{13}, \frac{8}{15}, \frac{9}{16}</math>. At this point we know that we've got our fraction and our answer is <math>16-9=\boxed{\textbf{A } 7}</math>
+
Solving for <math>q</math> in these equalities, we get <math>\frac{63}{4} < q < \frac{49}{3}.</math> So, <math>q</math> is between <math>15.75</math> and <math>16.\overline{3},</math> making it <math>16</math> as <math>q</math> is a positive integer (again, at this point, this is still an assumption). This would set <math>p=16-7=9.</math>
  
−
The inspection was made faster by considering the fact that <math>\frac{a+1}{b+1}>\frac{a}{b}</math>.
+
Since <math>\frac{5}{9} < \frac{9}{16} < \frac{4}{7},</math> the minimum difference is <math>\boxed{\textbf{(A) } 7}.</math>
−
 
 
−
So, once a fraction was gotten which was greater than <math>\frac{4}{7}</math> we jump to the next denominator.
 
−
 
 
−
We then make sure we consider fractions with higher positive difference between the denominator and numerator. And we also do not forget that the numerator must be greater than half of the denominator.
 
−
 
 
−
(<math>\frac{8}{14}</math> was obviously skipped because it is equal to <math>\frac{4}{7}</math>.)
 
−
 
 
−
 
 
−
~OlutosinNGA
 
  
−
==Solution 10 (testing answer choices)==
+
~mesmore
  
−
In ascending order, we can use answer choices, values for <math>q-p</math>, as a method of figuring out our answer through the means of substitution. Let the assumed difference be 7. Then, <math>p=q-7</math>. We thus have two inequalities: <math>\frac{5}{9} < \frac{q-7}{q}</math> and <math>\frac{q-7}{q} < \frac{4}{7}</math>.
+
==Solution 12 (Educated Guess)==
  
−
Solving for <math>q</math> in these equalities, we get <math>\frac{63}{4} < q < \frac{49}{3}</math>. <math>q</math> is between <math>15.75</math> and <math>16.\overline{3}</math>, making it 16 as <math>q</math> is a positive integer (again, at this point, this is still an assumption). This would set <math>p=16-7=9</math>. <math>\frac{5}{9} < \frac{9}{16} < \frac{4}{7}</math>, so the minimum difference is, in fact, indeed <math>\boxed{\textbf{(A)}\ 7}</math>.
+
Assume that the difference <math>\frac{p}{q} - \frac{5}{9}</math> results in a fraction of the form <math>\frac{1}{9q}.</math> Then, <cmath>9p - 5q = 1.</cmath>
 +
Also assume that the difference <math>\frac{4}{7} - \frac{p}{q}</math> results in a fraction of the form <math>\frac{1}{7q}.</math> Then, <cmath>4q - 7p = 1.</cmath>
 +
Solving the system of equations yields <math>q=16</math> and <math>p=9.</math> Therefore, the answer is <math>\boxed{\textbf{(A) } 7}.</math>
  
−
~ mesmore
+
Refer to Solution 1 for the full justification.
  
 
==See Also==
 
==See Also==

Latest revision as of 23:18, 22 October 2023

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 (Generalization)

More generally, let $a,b,c,d,p,$ and $q$ be positive integers such that $bc-ad=1$ and \[\frac ab < \frac pq < \frac cd.\] From $\frac ab < \frac pq,$ we have $bp-aq>0,$ or \[bp-aq\geq1. \hspace{15mm} (1)\] From $\frac pq < \frac cd,$ we have $cq-dp>0,$ or \[cq-dp\geq1. \hspace{15mm} (2)\] Since $bc-ad=1,$ note that:

  1. Multiplying $(1)$ by $d,$ multiplying $(2)$ by $b,$ and adding the results, we get $q\geq b+d.$

  2. Multiplying $(1)$ by $c,$ multiplying $(2)$ by $a,$ and adding the results, we get $p\geq a+c.$

To minimize $q,$ we set $q=b+d,$ from which $p=a+c.$ Together, we can prove that \[\frac{a+c-1}{b+d}\leq\frac ab<\frac{a+c}{b+d}<\frac cd\leq\frac{a+c+1}{b+d}. \hspace{15mm} (\bigstar)\] For this problem, we have $a=5,b=9,c=4,$ and $d=7,$ so $p=a+c=9$ and $q=b+d=16.$ The answer is $q-p=\boxed{\textbf{(A) } 7}.$

Remark

We will prove each part of the compound inequality in $(\bigstar):$

  1. $\frac{a+c-1}{b+d}\leq\frac ab$ and $\frac cd\leq\frac{a+c+1}{b+d}$

    2. Let $\frac ab=k,$ so $a=bk.$ The precondition $bc-ad=1$ becomes $bc-bdk=1,$ so $c-dk=\frac1b.$

    It follows that \[\frac{a+c-1}{b+d}=\frac{bk+c-1}{b+d}=k+\frac{c-dk-1}{b+d}=k+\frac{\frac1b-1}{b+d}=k+\frac{1-b}{b(b+d)}\leq k.\] Moreover, the equality case occurs if and only if $b=1.$

    We can prove $\frac cd\leq\frac{a+c+1}{b+d}$ by the same process. Similarly, the equality case occurs if and only if $d=1.$

  2. $\frac ab<\frac{a+c}{b+d}<\frac cd$

    3. Let $\frac ab=k_1$ and $\frac cd=k_2,$ so $a=bk_1$ and $c=dk_2.$

    It follows that \begin{alignat*}{10} \frac{a+c}{b+d}&=\frac{bk_1+dk_2}{b+d}&&=k_1+\frac{dk_2-dk_1}{b+d}&&=k_1+\frac{d(k_2-k_1)}{b+d}&&>k_1, \\ \frac{a+c}{b+d}&=\frac{bk_1+dk_2}{b+d}&&=k_2+\frac{bk_1-bk_2}{b+d}&&=k_2+\frac{b(k_1-k_2)}{b+d}&&<k_2. \end{alignat*} Moreover, this part of $(\bigstar)$ is independent of the precondition $bc-ad=1.$

~MRENTHUSIASM

Solution 2 (Generalization)

Define variables $a,b,c,d,p,$ and $q$ as Solution 1 does. Moreover, this solution refers to inequalities $(1)$ and $(2)$ in Solution 1.

Note that \begin{align*} \frac{1}{bd}&=\frac{bc-ad}{bd} \\ &=\frac cd - \frac ab \\ &=\left(\frac cd - \frac pq\right)+\left(\frac pq - \frac ab\right) \\ &=\frac{cq-dp}{dq}+\frac{bp-aq}{bp} \\ &\geq\frac{1}{dq}+\frac{1}{bq}. \end{align*} Multiplying both sides of $\frac{1}{bd}\geq\frac{1}{dq}+\frac{1}{bq}$ by $bdq,$ we get $q\geq b+d.$

For this problem, we have $a=5,b=9,c=4,$ and $d=7,$ so $q\geq b+d=16.$ At $q=16,$ we have \[\frac{8}{16}<\frac59<\frac{9}{16}<\frac47<\frac{10}{16},\] from which $p=9.$ Therefore, the answer is $q-p=\boxed{\textbf{(A) } 7}.$

Alternatively, refer to the Remark section in Solution 1 for further generalizations.

~pieater314159 ~MRENTHUSIASM

Solution 3 (Substitution)

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.\] Clearly $p>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 inequalities, 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 4 (Substitution)

Because $q$ and $p$ are positive integers with $p<q,$ 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,$ or $\frac{5}{4}k<p.$

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

Hence, we have $\frac{5}{4}k<p<\frac{4}{3}k,$ or $15k<12p<16k.$

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\ge{\boxed{\textbf{(A) } 7}}.$

Solution 5 (Manipulation)

We subtract $\frac{1}{2}$ from both sides of the equation, so \[\frac{1}{18} < \frac{p}{q}-\frac{1}{2} < \frac{1}{14}.\] Then for $q$ to be as small as possible, $\frac{p}{q}-\frac{1}{2}$ has to be $\frac{1}{16},$ so $\frac{p}{q}$ is $\frac{9}{16}$ and $q-p$ is $\boxed{\textbf{(A) } 7}.$

~purplepenguin2

Solution 6 (Solves for p)

Cross-multiply the inequality to get \[35q < 63p < 36q.\] Then, we have $0 < 63p-35q < q,$ or \[0 < 7(9p-5q) < q.\] Since $p$ and $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 7 (Inspection)

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}.\]

Therefore, the answer is $16 - 9 = \boxed{\textbf{(A) } 7}.$

Solution 8 (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<x<0.5714.$ 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,\ldots.$ We check $\frac{6}{10}, \frac{6}{11}, \frac{7}{12}, \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.

We then make sure we consider fractions with higher positive difference between the denominator and numerator. And we also do not forget that the numerator must be greater than half of the denominator.

($\frac{8}{14}$ was obviously skipped because it is equal to $\frac{4}{7}.$)

~OlutosinNGA

Solution 9 (Graphing)

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 10 (Answer Choices)

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 $\textbf{(A)},$ then the answer must be $\textbf{(B)}$ or $\textbf{(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 11 (Answer Choices)

In ascending order, we can use answer choices, values for $q-p,$ as a method of figuring out our answer through the means of substitution. Let the assumed difference be $7.$ Then, $p=q-7.$ We thus have two inequalities: $\frac{5}{9} < \frac{q-7}{q}$ and $\frac{q-7}{q} < \frac{4}{7}.$

Solving for $q$ in these equalities, we get $\frac{63}{4} < q < \frac{49}{3}.$ So, $q$ is between $15.75$ and $16.\overline{3},$ making it $16$ as $q$ is a positive integer (again, at this point, this is still an assumption). This would set $p=16-7=9.$

Since $\frac{5}{9} < \frac{9}{16} < \frac{4}{7},$ the minimum difference is $\boxed{\textbf{(A) } 7}.$

~mesmore

Solution 12 (Educated Guess)

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}.$

Refer to Solution 1 for the full justification.

See Also

2018 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 16 		Followed by
Problem 18
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_AMC_12B_Problems/Problem_17&oldid=200047"