Difference between revisions of "2018 AMC 10A Problems/Problem 22"
Mannsnothot (talk | contribs) (Completed the unfinished solution) |
|||
(28 intermediate revisions by 20 users not shown) | |||
Line 1: | Line 1: | ||
+ | ==Problem== | ||
+ | |||
Let <math>a, b, c,</math> and <math>d</math> be positive integers such that <math>\gcd(a, b)=24</math>, <math>\gcd(b, c)=36</math>, <math>\gcd(c, d)=54</math>, and <math>70<\gcd(d, a)<100</math>. Which of the following must be a divisor of <math>a</math>? | Let <math>a, b, c,</math> and <math>d</math> be positive integers such that <math>\gcd(a, b)=24</math>, <math>\gcd(b, c)=36</math>, <math>\gcd(c, d)=54</math>, and <math>70<\gcd(d, a)<100</math>. Which of the following must be a divisor of <math>a</math>? | ||
Line 5: | Line 7: | ||
== Solution 1 == | == Solution 1 == | ||
− | The | + | The GCD information tells us that <math>24</math> divides <math>a</math>, both <math>24</math> and <math>36</math> divide <math>b</math>, both <math>36</math> and <math>54</math> divide <math>c</math>, and <math>54</math> divides <math>d</math>. Note that we have the prime factorizations: |
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
24 &= 2^3\cdot 3,\\ | 24 &= 2^3\cdot 3,\\ | ||
Line 19: | Line 21: | ||
d &= 2\cdot 3^3\cdot z | d &= 2\cdot 3^3\cdot z | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | for some positive integers <math>w,x,y,z</math>. Now if 3 | + | for some positive integers <math>w,x,y,z</math>. Now if <math>3</math> divides <math>w</math>, then <math>\gcd(a,b)</math> would be at least <math>2^3\cdot 3^2</math> which is too large, hence <math>3</math> does not divide <math>w</math>. Similarly, if <math>2</math> divides <math>z</math>, then <math>\gcd(c,d)</math> would be at least <math>2^2\cdot 3^3</math> which is too large, so <math>2</math> does not divide <math>z</math>. Therefore, |
<cmath>\gcd(a,d)=2\cdot 3\cdot \gcd(w,z)</cmath> | <cmath>\gcd(a,d)=2\cdot 3\cdot \gcd(w,z)</cmath> | ||
− | where neither 2 nor 3 divide <math>\gcd(w,z)</math>. In other words, <math>\gcd(w,z)</math> is divisible only by primes that are at least 5. The only possible value of <math>\gcd(a,d)</math> between 70 and 100 and which fits this criterion is <math>78=2\cdot3\cdot13</math>, so the answer is <math>\boxed{\textbf{(D) }13}</math>. | + | where neither <math>2</math> nor <math>3</math> divide <math>\gcd(w,z)</math>. In other words, <math>\gcd(w,z)</math> is divisible only by primes that are at least <math>5</math>. The only possible value of <math>\gcd(a,d)</math> between <math>70</math> and <math>100</math> and which fits this criterion is <math>78=2\cdot3\cdot13</math>, so the answer is <math>\boxed{\textbf{(D) }13}</math>. |
== Solution 2 == | == Solution 2 == | ||
− | We can say that <math>a</math> and <math>b</math> 'have' <math>2^3 | + | We can say that <math>a</math> and <math>b</math> 'have' <math>2^3 \cdot 3</math>, that <math>b</math> and <math>c</math> have <math>2^2 \cdot 3^2</math>, and that <math>c</math> and <math>d</math> have <math>3^3 \cdot 2</math>. Combining <math>1</math> and <math>2</math> yields <math>b</math> has (at a minimum) <math>2^3 \cdot 3^2</math>, and thus <math>a</math> has <math>2^3 \cdot 3</math> (and no more powers of <math>3</math> because otherwise <math>\gcd(a,b)</math> would be different). In addition, <math>c</math> has <math>3^3 \cdot 2^2</math>, and thus <math>d</math> has <math>3^3 \cdot 2</math> (similar to <math>a</math>, we see that <math>d</math> cannot have any other powers of <math>2</math>). We now assume the simplest scenario, where <math>a = 2^3 \cdot 3</math> and <math>d = 3^3 \cdot 2</math>. According to this base case, we have <math>\gcd(a, d) = 2 \cdot 3 = 6</math>. We want an extra factor between the two such that this number is between <math>70</math> and <math>100</math>, and this new factor cannot be divisible by <math>2</math> or <math>3</math>. Checking through, we see that <math>6 \cdot 13</math> is the only one that works. Therefore the answer is <math>\boxed{\textbf{(D) } 13}</math> |
Solution by JohnHankock | Solution by JohnHankock | ||
− | == Solution | + | ==Solution 3 (Better notation)== |
− | |||
− | + | First off, note that <math>24</math>, <math>36</math>, and <math>54</math> are all of the form <math>2^x\times3^y</math>. The prime factorizations are <math>2^3\times 3^1</math>, <math>2^2\times 3^2</math> and <math>2^1\times 3^3</math>, respectively. Now, let <math>a_2</math> and <math>a_3</math> be the number of times <math>2</math> and <math>3</math> go into <math>a</math>, respectively. Define <math>b_2</math>, <math>b_3</math>, <math>c_2</math>, and <math>c_3</math> similarly. Now, translate the <math>lcm</math>s into the following: | |
+ | <cmath>1) \min(a_2,b_2)=3</cmath> <cmath>2) \min(a_3,b_3)=1</cmath> <cmath>3) \min(b_2,c_2)=2</cmath> <cmath>4) \min(b_3,c_3)=2</cmath> <cmath>5) \min(c_2,d_2)=1</cmath> <cmath>6) \min(c_3,d_3)=3</cmath> | ||
− | + | From <math>4)</math>, we see that <math>b_3 \geq 2</math>, thus from <math>2)</math>, <math>a_3 = 1</math>. Similarly, from <math>3)</math>, <math>c_2 \geq 2</math>, thus from <math>5)</math>, <math>d_2 = 1</math>. | |
− | == | + | Note also that <math>d_3 \geq 3</math> and <math>a_2 \geq 3</math>. Therefore <cmath>\min(a_2, d_2) = 1</cmath> <cmath>\min(a_3, d_3) = 1</cmath> Thus, <math>\gcd(a, d) = 2 \times 3 \times k</math> for some <math>k</math> having no factors of <math>2</math> or <math>3</math>. |
− | + | Since <math>70 < \gcd(a, d) < 100</math>, the only values for k are <math>12, 13, 14, 15, 16</math>, but all have either factors of <math>2</math> or <math>3</math>, except <math>\boxed{\textbf{(D)} 13}</math>. And we're done. | |
− | |||
− | + | ~Rowechen Zhong ~MannsNotHot | |
− | ~Rowechen Zhong | ||
==Solution 4 (Fastest)== | ==Solution 4 (Fastest)== | ||
− | Notice that <math>gcd (a,b,c,d)=gcd(gcd(a,b),gcd(b,c),gcd(c,d))=gcd(24,36,54)=6</math>, so <math>gcd(d,a)</math> must be a multiple of <math>6</math>. The only answer choice that gives a value between <math>70</math> and <math>100</math> when multiplied by 6 is <math>\boxed{\textbf{(D) } 13}</math>. - mathleticguyyy | + | Notice that <math>\gcd (a,b,c,d)=\gcd(\gcd(a,b),\gcd(b,c),\gcd(c,d))=\gcd(24,36,54)=6</math>, so <math>\gcd(d,a)</math> must be a multiple of <math>6</math>. The only answer choice that gives a value between <math>70</math> and <math>100</math> when multiplied by <math>6</math> is <math>\boxed{\textbf{(D) } 13}</math>. - mathleticguyyy + einstein |
+ | |||
+ | In the case where there can be 2 possible answers, we can do casework on <math>\gcd(d,a)</math> | ||
+ | ~Williamgolly | ||
+ | |||
+ | ==Solution 5== | ||
+ | |||
+ | |||
+ | Since <math>\gcd (a,b) = 24</math>, <math>a = 24j</math> and <math>b = 24k</math> for some positive integers <math>j,k</math> such that <math>j</math> and <math>k</math> are relatively prime. | ||
+ | |||
+ | Similarly , since <math>\gcd (b,c) = 36</math>, we have <math>b = 24k</math> and <math>c=36m</math> with the same criteria. However, since <math>24</math> is not a multiple of <math>36</math>, we must contribute an extra <math>3</math> to <math>b</math> in order to make it a multiple of <math>36</math>. So, <math>k</math> is a multiple of three, and it is relatively prime to <math>m</math>. | ||
+ | |||
+ | Finally, <math>\gcd (c,d) = 54</math>, so using the same logic, <math>m</math> is a multiple of <math>3</math> and is relatively prime to <math>n</math> where <math>d = 54n</math>. | ||
+ | |||
+ | Since we can't really do anything with these messy expressions, we should try some sample cases of <math>a,b,c</math> and <math>d</math>. Specifically, we let <math>j = 5, 7, 11, 13</math> or <math>17</math>, and see which one works. | ||
+ | |||
+ | First we let <math>j= 5</math>. Note that all of these values of <math>j</math> work for the first <math>\gcd</math> expression because they are all not divisible by <math>3</math>. | ||
+ | |||
+ | Without the loss of generality, we let <math>k=m=3</math> for all of our sample cases. We can also adjust the value of <math>n</math> in <math>d=54n</math>, since there is no fixed value for <math>\gcd(a,d)</math>; there is only a bound. | ||
+ | |||
+ | So we try to make our bound <math>70 < \gcd(a,d) < 100</math> satisfactory. We do so by letting <math>j=n</math>. | ||
+ | |||
+ | Testing our first case <math>a=24 \cdot 5</math> and <math>d = 54 \cdot 5</math>, we find that <math>\gcd(a,d) = 30</math>. To simplify our work, we note that <math>\gcd(24,54) = 6</math>, so <math>\gcd(24k, 54k)</math> for all <math>k>1</math> is equal to <math>6k</math>. | ||
+ | |||
+ | So now, we can easily find our values of <math>\gcd(a,b)</math>: | ||
+ | |||
+ | <cmath>\gcd(24 \cdot 5, 54 \cdot 5) = 6 \cdot 5 = 30</cmath> | ||
+ | |||
+ | <cmath>\gcd(24 \cdot 7, 54 \cdot 7) = 6 \cdot 7 = 42</cmath> | ||
+ | |||
+ | <cmath>\gcd(24 \cdot 11, 54 \cdot 11) = 6 \cdot 11 = 66</cmath> | ||
+ | |||
+ | <cmath>\boxed{\gcd(24 \cdot 13, 54 \cdot 13) = 6 \cdot 13 = 78}</cmath> | ||
+ | |||
+ | <cmath>\gcd(24 \cdot 17, 54 \cdot 17) = 6 \cdot 17 = 104</cmath> | ||
+ | |||
+ | We can clearly see that only <math>j=n=13</math> is in the bound <math>70 < \gcd(a,d) < 100</math>. So, <math>13</math> must be a divisor of <math>a</math>, which is answer choice <math>\boxed{\textbf{(D)}}</math>. | ||
+ | |||
+ | -FIREDRAGONMATH16 | ||
+ | |||
+ | ==Solution 6== | ||
+ | |||
+ | <asy> | ||
+ | //Variable Declarations | ||
+ | defaultpen(0.45); | ||
+ | size(200pt); | ||
+ | fontsize(15pt); | ||
+ | pair X, Y, Z, W; | ||
+ | real R; | ||
+ | path quad; | ||
+ | |||
+ | //Variable Definitions | ||
+ | R = 1; | ||
+ | X = R*dir(45); | ||
+ | Y = R*dir(135); | ||
+ | Z = R*dir(-135); | ||
+ | W = R*dir(-45); | ||
+ | quad = X--Y--Z--W--cycle; | ||
+ | |||
+ | //Diagram | ||
+ | draw(quad); | ||
+ | label("$b$",X,NE); | ||
+ | label("$a=2^3 \cdot 3 \cdot p$",Y,NW); | ||
+ | label("$d=2 \cdot 3^3 \cdot q$",Z,SW); | ||
+ | label("$c$",W,SE); | ||
+ | label("$2^3 \cdot 3$",X--Y); | ||
+ | label("$2^2 \cdot 3^2$",X--W); | ||
+ | label("$2 \cdot 3^3$",Z--W); | ||
+ | label("$2 \cdot 3 \cdot k$",Z--Y); | ||
+ | </asy> | ||
+ | |||
+ | The relationship of <math>a</math>, <math>b</math>, <math>c</math>, and <math>d</math> is shown in the above diagram. <math>gcd(a,d)=2 \cdot 3 \cdot k</math>. | ||
+ | <math>70 < 6k < 100</math>, <math>12 \le k \le 16</math>, <math>k=\boxed{\textbf{(D) }13}</math> | ||
+ | |||
+ | Note that <math>gcd(b,c)=36</math> is not required to solve the problem. | ||
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ||
+ | |||
+ | |||
+ | ==Solution 7 (Easier version of Solution 1)== | ||
+ | |||
+ | Just as in solution <math>1</math>, we prime factorize <math>a, b, c</math> and <math>d</math> to observe that | ||
+ | |||
+ | <math>a=2^3\cdot{3}\cdot{w}</math> | ||
+ | |||
+ | <math>b=2^3\cdot{3^2}\cdot{x}</math> | ||
+ | |||
+ | <math>c=2^2\cdot{3^3}\cdot{y}</math> | ||
+ | |||
+ | <math>d=2\cdot{3^3}\cdot{z}.</math> | ||
+ | |||
+ | Substituting these expressions for <math>a</math> and <math>d</math> into the final given, | ||
+ | |||
+ | <math>70<\text{gcd}(2\cdot{3^3}\cdot{z}, 2^3\cdot{3}\cdot{w})<100.</math> | ||
+ | |||
+ | The greatest common divisor of these two numbers is already <math>6</math>. If <math>k</math> is what we wish to multiply <math>6</math> by to obtain the gcd of these two numbers, then | ||
+ | |||
+ | <math>70<6k<100</math>. Testing the answer choices, only <math>13</math> works for <math>k</math> (in order for the compound inequality to hold). so our gcd is <math>78</math>, which means that <math>\boxed{\textbf{(D) }13}</math> must divide <math>a</math>. | ||
+ | |||
+ | -Benedict T (countmath1) | ||
+ | |||
+ | == Video Solution by Richard Rusczyk == | ||
+ | |||
+ | https://artofproblemsolving.com/videos/amc/2018amc10a/467 | ||
+ | |||
+ | ~ dolphin7 | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/yjrqINsQP5c | ||
+ | |||
+ | ~savannahsolver | ||
+ | |||
+ | == Video Solution by OmegaLearn (Meta-Solving Technique) == | ||
+ | https://youtu.be/GmUWIXXf_uk?t=1003 | ||
+ | |||
+ | ~ pi_is_3.14 | ||
==See Also== | ==See Also== |
Latest revision as of 04:51, 6 August 2023
Contents
Problem
Let and
be positive integers such that
,
,
, and
. Which of the following must be a divisor of
?
Solution 1
The GCD information tells us that divides
, both
and
divide
, both
and
divide
, and
divides
. Note that we have the prime factorizations:
Hence we have
for some positive integers
. Now if
divides
, then
would be at least
which is too large, hence
does not divide
. Similarly, if
divides
, then
would be at least
which is too large, so
does not divide
. Therefore,
where neither
nor
divide
. In other words,
is divisible only by primes that are at least
. The only possible value of
between
and
and which fits this criterion is
, so the answer is
.
Solution 2
We can say that and
'have'
, that
and
have
, and that
and
have
. Combining
and
yields
has (at a minimum)
, and thus
has
(and no more powers of
because otherwise
would be different). In addition,
has
, and thus
has
(similar to
, we see that
cannot have any other powers of
). We now assume the simplest scenario, where
and
. According to this base case, we have
. We want an extra factor between the two such that this number is between
and
, and this new factor cannot be divisible by
or
. Checking through, we see that
is the only one that works. Therefore the answer is
Solution by JohnHankock
Solution 3 (Better notation)
First off, note that ,
, and
are all of the form
. The prime factorizations are
,
and
, respectively. Now, let
and
be the number of times
and
go into
, respectively. Define
,
,
, and
similarly. Now, translate the
s into the following:
From , we see that
, thus from
,
. Similarly, from
,
, thus from
,
.
Note also that and
. Therefore
Thus,
for some
having no factors of
or
.
Since , the only values for k are
, but all have either factors of
or
, except
. And we're done.
~Rowechen Zhong ~MannsNotHot
Solution 4 (Fastest)
Notice that , so
must be a multiple of
. The only answer choice that gives a value between
and
when multiplied by
is
. - mathleticguyyy + einstein
In the case where there can be 2 possible answers, we can do casework on
~Williamgolly
Solution 5
Since ,
and
for some positive integers
such that
and
are relatively prime.
Similarly , since , we have
and
with the same criteria. However, since
is not a multiple of
, we must contribute an extra
to
in order to make it a multiple of
. So,
is a multiple of three, and it is relatively prime to
.
Finally, , so using the same logic,
is a multiple of
and is relatively prime to
where
.
Since we can't really do anything with these messy expressions, we should try some sample cases of and
. Specifically, we let
or
, and see which one works.
First we let . Note that all of these values of
work for the first
expression because they are all not divisible by
.
Without the loss of generality, we let for all of our sample cases. We can also adjust the value of
in
, since there is no fixed value for
; there is only a bound.
So we try to make our bound satisfactory. We do so by letting
.
Testing our first case and
, we find that
. To simplify our work, we note that
, so
for all
is equal to
.
So now, we can easily find our values of :
We can clearly see that only is in the bound
. So,
must be a divisor of
, which is answer choice
.
-FIREDRAGONMATH16
Solution 6
The relationship of ,
,
, and
is shown in the above diagram.
.
,
,
Note that is not required to solve the problem.
Solution 7 (Easier version of Solution 1)
Just as in solution , we prime factorize
and
to observe that
Substituting these expressions for and
into the final given,
The greatest common divisor of these two numbers is already . If
is what we wish to multiply
by to obtain the gcd of these two numbers, then
. Testing the answer choices, only
works for
(in order for the compound inequality to hold). so our gcd is
, which means that
must divide
.
-Benedict T (countmath1)
Video Solution by Richard Rusczyk
https://artofproblemsolving.com/videos/amc/2018amc10a/467
~ dolphin7
Video Solution
~savannahsolver
Video Solution by OmegaLearn (Meta-Solving Technique)
https://youtu.be/GmUWIXXf_uk?t=1003
~ pi_is_3.14
See Also
2018 AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 21 |
Followed by Problem 23 | |
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 10 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.