Difference between revisions of "2018 AMC 10A Problems/Problem 22"
Ga mathelete (talk | contribs) m (→Solution 1) |
|||
Line 4: | Line 4: | ||
== Solution 1 == | == Solution 1 == | ||
+ | |||
+ | The gcd information tells us that 24 divides <math>a</math>, both 24 and 36 divide <math>b</math>, both 36 and 54 divide <math>c</math>, and 54 divides <math>d</math>. Note that we have the prime factorizations: | ||
+ | <cmath>\begin{align*} | ||
+ | 24 &= 2^3\cdot 3,\\ | ||
+ | 36 &= 2^2\cdot 3^2,\\ | ||
+ | 54 &= 2\cdot 3^3. | ||
+ | \end{align*}</cmath> | ||
+ | |||
+ | Hence we can write | ||
+ | <cmath>\begin{align*} | ||
+ | a &= 2^3\cdot 3\cdot w\\ | ||
+ | b &= 2^3\cdot 3^2\cdot x\\ | ||
+ | c &= 2^2\cdot 3^3\cdot y\\ | ||
+ | d &= 2\cdot 3^3\cdot z | ||
+ | \end{align*}</cmath> | ||
+ | for some positive integers <math>w,x,y,z</math>. Now if 3 divdes <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 3 does not divide <math>w</math>. Similarly, if 2 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 2 does not divide <math>z</math>. Therefore, | ||
+ | <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> are divisible only by primes that are at least 5. The only number of this form between 70 and 100 is <math>78=2\cdot3\cdot13</math>, so the answer is <math>\boxed{\textbf{(D) }13}</math>. | ||
+ | |||
+ | == Solution 2 == | ||
We can say that <math>a</math> and <math>b</math> 'have' <math>2^3 * 3</math>, that <math>b</math> and <math>c</math> have <math>2^2 * 3^2</math>, and that <math>c</math> and <math>d</math> have <math>3^3 * 2</math>. Combining <math>1</math> and <math>2</math> yields <math>b</math> has (at a minimum) <math>2^3 * 3^2</math>, and thus <math>a</math> has <math>2^3 * 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 * 2^2</math>, and thus <math>d</math> has <math>3^3 * 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 * 3</math> and <math>d = 3^3 * 2</math>. According to this base case, we have <math>gcd(a, d) = 2 * 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 * 13</math> is the only one that works. Therefore the answer is <math>\boxed{\textbf{(D) } 13}</math> | We can say that <math>a</math> and <math>b</math> 'have' <math>2^3 * 3</math>, that <math>b</math> and <math>c</math> have <math>2^2 * 3^2</math>, and that <math>c</math> and <math>d</math> have <math>3^3 * 2</math>. Combining <math>1</math> and <math>2</math> yields <math>b</math> has (at a minimum) <math>2^3 * 3^2</math>, and thus <math>a</math> has <math>2^3 * 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 * 2^2</math>, and thus <math>d</math> has <math>3^3 * 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 * 3</math> and <math>d = 3^3 * 2</math>. According to this base case, we have <math>gcd(a, d) = 2 * 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 * 13</math> is the only one that works. Therefore the answer is <math>\boxed{\textbf{(D) } 13}</math> | ||
Line 9: | Line 29: | ||
Solution by JohnHankock | Solution by JohnHankock | ||
− | == Solution | + | == Solution 2.1 == |
Elaborating on to what Solution 1 stated, we are not able to add any extra factor of 2 or 3 to <math>gcd(a, d)</math> because doing so would later the <math>gcd</math> of <math>(a, b)</math> and <math>(c, d)</math>. This is why: | Elaborating on to what Solution 1 stated, we are not able to add any extra factor of 2 or 3 to <math>gcd(a, d)</math> because doing so would later the <math>gcd</math> of <math>(a, b)</math> and <math>(c, d)</math>. This is why: | ||
Line 16: | Line 36: | ||
Thus, the <math>gcd</math> of <math>(a, d)</math> can be expressed in the form <math>2 * 3 * k</math> for which <math>k</math> is a number not divisible by <math>2</math> or <math>3</math>. The only answer choice that satisfies this (and the other condition) is <math>\boxed{\textbf{(D) } 13}</math>. | Thus, the <math>gcd</math> of <math>(a, d)</math> can be expressed in the form <math>2 * 3 * k</math> for which <math>k</math> is a number not divisible by <math>2</math> or <math>3</math>. The only answer choice that satisfies this (and the other condition) is <math>\boxed{\textbf{(D) } 13}</math>. | ||
− | ==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> similiarly. Now, translate the <math>lcm</math>s into the following: | 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> similiarly. Now, translate the <math>lcm</math>s into the following: |
Revision as of 00:35, 11 December 2018
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 24 divides , both 24 and 36 divide
, both 36 and 54 divide
, and 54 divides
. Note that we have the prime factorizations:
Hence we can write
for some positive integers
. Now if 3 divdes
, then
would be at least
which is too large, hence 3 does not divide
. Similarly, if 2 divides
, then
would be at least
which is too large, so 2 does not divide
. Therefore,
where neither 2 nor 3 divide
. In other words,
are divisible only by primes that are at least 5. The only number of this form between 70 and 100 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
Elaborating on to what Solution 1 stated, we are not able to add any extra factor of 2 or 3 to because doing so would later the
of
and
. This is why:
The is
and the
of
is
. However, the
of
(meaning both are divisible by 36). Therefore,
is only divisible by
(and no higher power of 3), while
is divisible by only
(and no higher power of 2).
Thus, the of
can be expressed in the form
for which
is a number not divisible by
or
. The only answer choice that satisfies this (and the other condition) is
.
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
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.