Difference between revisions of "2018 AMC 10A Problems/Problem 22"
Justin6688 (talk | contribs) (→Solution 4 (Fastest)) |
|||
Line 49: | Line 49: | ||
In the case where there can be 2 possible answers, we can do casework on gcd(d,a) | In the case where there can be 2 possible answers, we can do casework on gcd(d,a) | ||
~Williamgolly | ~Williamgolly | ||
+ | |||
+ | ==Solution 5 (FIREDRAGONMATH16's Solution)== | ||
+ | |||
+ | |||
+ | 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 | ||
==Hardness of problem== | ==Hardness of problem== |
Revision as of 06:38, 8 May 2021
Contents
[hide]- 1 Problem
- 2 Solution 1
- 3 Solution 2
- 4 Solution 2.1 (updated with better notation)
- 5 Solution 3 (Better notation)
- 6 Solution 4 (Fastest)
- 7 Solution 5 (FIREDRAGONMATH16's Solution)
- 8 Hardness of problem
- 9 Video Solution by Richard Rusczyk
- 10 Video Solution
- 11 Video Solution (Meta-Solving Technique)
- 12 See Also
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 2.1 (updated with better notation)
Do casework on and
Notice that we must have
and
and the values of
does not matter. Therefore,
where
is not divisible by
or
We see that
is the only possible answer.
-Williamgolly
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
similiarly. Now, translate the
s into the following:
.
(Unfinished) ~Rowechen Zhong
Solution 4 (Fastest)
Notice that , so
must be a multiple of
. The only answer choice that gives a value between
and
when multiplied by 6 is
. - mathleticguyyy + einstein
In the case where there can be 2 possible answers, we can do casework on gcd(d,a) ~Williamgolly
Solution 5 (FIREDRAGONMATH16's Solution)
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
Hardness of problem
The ranking of this number theory problem is easy hard(just starting to be hard) or a 7 out of 10. This is because you've got to think through out although it is more of which and easy solution
~justin6688
Video Solution by Richard Rusczyk
https://artofproblemsolving.com/videos/amc/2018amc10a/467
~ dolphin7
Video Solution
~savannahsolver
Video Solution (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.