Difference between revisions of "2018 AMC 12B Problems/Problem 17"
Happy-byron (talk | contribs) m (→Solution 3 (Substitution)) |
|||
(65 intermediate revisions by 12 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) == |
− | + | 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> | ||
− | < | + | <u><b>Remark</b></u> |
− | |||
− | == | + | 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 | ||
− | + | == 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. | ||
− | < | + | 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> | ||
− | + | 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> | ||
− | < | + | Alternatively, refer to the <u><b>Remark</b></u> section in Solution 1 for further generalizations. |
− | + | ~pieater314159 ~MRENTHUSIASM | |
− | ==Solution 3== | + | ==Solution 3 (Substitution)== |
+ | |||
+ | Inverting the given inequality we get <cmath>\frac{7}{4} < \frac{q}{p} < \frac{9}{5},</cmath> | ||
+ | which simplifies to <cmath>35p < 20q < 36p.</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> | ||
+ | |||
+ | The inequality <math>20k < 16k + 16x</math> simplifies to <math>k < 4x.</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 (Substitution)== | ||
+ | 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> | ||
+ | |||
+ | 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> | ||
+ | |||
+ | 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> | ||
+ | |||
+ | Hence, we have <math>\frac{5}{4}k<p<\frac{4}{3}k,</math> or <math>15k<12p<16k.</math> | ||
+ | |||
+ | 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. | ||
+ | |||
+ | 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> | ||
+ | |||
+ | ==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> | ||
+ | |||
+ | ~purplepenguin2 | ||
+ | |||
+ | ==Solution 6 (Solves for p)== | ||
Cross-multiply the inequality to get <cmath>35q < 63p < 36q.</cmath> | 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> | ||
+ | |||
+ | 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> | ||
+ | |||
+ | ==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> | ||
+ | |||
+ | Therefore, the answer is <math>16 - 9 = \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. | ||
+ | |||
+ | 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> | ||
+ | |||
+ | The inspection was made faster by considering the fact that <math>\frac{a+1}{b+1}>\frac{a}{b}.</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 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> | ||
+ | |||
+ | Remark: This also gives an intuitive geometric proof of the mediant using vectors. | ||
− | + | ==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> |
− | < | ||
− | + | ==Solution 11 (Answer Choices)== | |
− | + | 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> | |
− | + | 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> | |
− | |||
− | + | Since <math>\frac{5}{9} < \frac{9}{16} < \frac{4}{7},</math> the minimum difference is <math>\boxed{\textbf{(A) } 7}.</math> | |
− | ==Solution | + | ~mesmore |
− | + | ||
+ | ==Solution 12 (Educated Guess)== | ||
+ | |||
+ | 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> | ||
+ | |||
+ | Refer to Solution 1 for the full justification. | ||
==See Also== | ==See Also== | ||
Line 47: | Line 147: | ||
{{AMC12 box|year=2018|ab=B|num-b=16|num-a=18}} | {{AMC12 box|year=2018|ab=B|num-b=16|num-a=18}} | ||
{{MAA Notice}} | {{MAA Notice}} | ||
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] |
Latest revision as of 00:18, 23 October 2023
Contents
- 1 Problem
- 2 Solution 1 (Generalization)
- 3 Solution 2 (Generalization)
- 4 Solution 3 (Substitution)
- 5 Solution 4 (Substitution)
- 6 Solution 5 (Manipulation)
- 7 Solution 6 (Solves for p)
- 8 Solution 7 (Inspection)
- 9 Solution 8 (Inspection)
- 10 Solution 9 (Graphing)
- 11 Solution 10 (Answer Choices)
- 12 Solution 11 (Answer Choices)
- 13 Solution 12 (Educated Guess)
- 14 See Also
Problem
Let and
be positive integers such that
and
is as small as possible. What is
?
Solution 1 (Generalization)
More generally, let and
be positive integers such that
and
From
we have
or
From
we have
or
Since
note that:
- Multiplying
by
multiplying
by
and adding the results, we get
- Multiplying
by
multiplying
by
and adding the results, we get
To minimize we set
from which
Together, we can prove that
For this problem, we have
and
so
and
The answer is
Remark
We will prove each part of the compound inequality in
and
Let so
The precondition
becomes
so
It follows that Moreover, the equality case occurs if and only if
We can prove by the same process. Similarly, the equality case occurs if and only if
Let and
so
and
It follows that
Moreover, this part of
is independent of the precondition
~MRENTHUSIASM
Solution 2 (Generalization)
Define variables and
as Solution 1 does. Moreover, this solution refers to inequalities
and
in Solution 1.
Note that
Multiplying both sides of
by
we get
For this problem, we have and
so
At
we have
from which
Therefore, the answer is
Alternatively, refer to the Remark section in Solution 1 for further generalizations.
~pieater314159 ~MRENTHUSIASM
Solution 3 (Substitution)
Inverting the given inequality we get
which simplifies to
We can now substitute
Note we need to find
which simplifies to
Clearly
We will now substitute
to get
The inequality
simplifies to
The inequality simplifies to
Combining the two inequalities, we get
Since
and
are integers, the smallest values of
and
that satisfy the above equation are
and
respectively. Substituting these back in, we arrive with an answer of
Solution 4 (Substitution)
Because and
are positive integers with
we can let
where
Now, the problem condition reduces to
Our first inequality is which gives us
or
Our second inequality is which gives us
or
Hence, we have or
It is clear that we are aiming to find the least positive integer value of such that there is at least one value of
that satisfies the inequality.
Now, simple casework through the answer choices of the problem reveals that
Solution 5 (Manipulation)
We subtract from both sides of the equation, so
Then for
to be as small as possible,
has to be
so
is
and
is
~purplepenguin2
Solution 6 (Solves for p)
Cross-multiply the inequality to get
Then, we have
or
Since
and
are integers,
is an integer. To minimize
start from
which gives
This limits
to be greater than
so test values of
starting from
However,
to
do not give integer values of
Once it is possible for
to be equal to
so
could also be equal to
The next value,
is not a solution, but
gives
Thus, the smallest possible value of
is
and the answer is
Solution 7 (Inspection)
Start with Repeat the following process until you arrive at the answer: if the fraction is less than or equal to
add
to the numerator; otherwise, if it is greater than or equal to
add one
to the denominator. We have
Therefore, the answer is
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 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 We check
At this point we know that we've got our fraction and our answer is
The inspection was made faster by considering the fact that
So, once a fraction was gotten which was greater than 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.
( was obviously skipped because it is equal to
)
~OlutosinNGA
Solution 9 (Graphing)
Graph the regions and
Note that the lattice point
is the smallest magnitude one which appears within the region bounded by the two graphs. Thus, our fraction is
and the answer is
Remark: This also gives an intuitive geometric proof of the mediant using vectors.
Solution 10 (Answer Choices)
As the other solutions do, the mediant is between the two fractions, with a difference of
Suppose that the answer was not
then the answer must be
or
as otherwise
would be negative. Then, the possible fractions with lower denominator would be
for
and
for
which are clearly not anywhere close to
Solution 11 (Answer Choices)
In ascending order, we can use answer choices, values for as a method of figuring out our answer through the means of substitution. Let the assumed difference be
Then,
We thus have two inequalities:
and
Solving for in these equalities, we get
So,
is between
and
making it
as
is a positive integer (again, at this point, this is still an assumption). This would set
Since the minimum difference is
~mesmore
Solution 12 (Educated Guess)
Assume that the difference results in a fraction of the form
Then,
Also assume that the difference
results in a fraction of the form
Then,
Solving the system of equations yields
and
Therefore, the answer is
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.