Difference between revisions of "2018 AMC 10A Problems/Problem 22"
Isabelchen (talk | contribs) |
Mannsnothot (talk | contribs) (Completed the unfinished solution) |
||
(7 intermediate revisions by 5 users not shown) | |||
Line 31: | Line 31: | ||
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)== | ||
Line 50: | Line 50: | ||
~Williamgolly | ~Williamgolly | ||
− | ==Solution 5 | + | ==Solution 5== |
Line 87: | Line 87: | ||
==Solution 6== | ==Solution 6== | ||
− | ~isabelchen | + | <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 == | == Video Solution by Richard Rusczyk == | ||
Line 100: | Line 157: | ||
~savannahsolver | ~savannahsolver | ||
− | == Video Solution (Meta-Solving Technique) == | + | == Video Solution by OmegaLearn (Meta-Solving Technique) == |
https://youtu.be/GmUWIXXf_uk?t=1003 | https://youtu.be/GmUWIXXf_uk?t=1003 | ||
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.