Difference between revisions of "2018 AMC 10A Problems/Problem 22"
(→Solution) |
Justin6688 (talk | contribs) (→Solution 4 (Fastest)) |
||
(32 intermediate revisions by 23 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>? | ||
<math>\textbf{(A)} \text{ 5} \qquad \textbf{(B)} \text{ 7} \qquad \textbf{(C)} \text{ 11} \qquad \textbf{(D)} \text{ 13} \qquad \textbf{(E)} \text{ 17}</math> | <math>\textbf{(A)} \text{ 5} \qquad \textbf{(B)} \text{ 7} \qquad \textbf{(C)} \text{ 11} \qquad \textbf{(D)} \text{ 13} \qquad \textbf{(E)} \text{ 17}</math> | ||
− | == Solution == | + | == Solution 1 == |
+ | |||
+ | 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*} | ||
+ | 24 &= 2^3\cdot 3,\\ | ||
+ | 36 &= 2^2\cdot 3^2,\\ | ||
+ | 54 &= 2\cdot 3^3. | ||
+ | \end{align*}</cmath> | ||
+ | |||
+ | Hence we have | ||
+ | <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 <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> | ||
+ | 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 == | ||
− | We can say that a and b 'have' <math>2^3 * 3</math>, that b and c have 2^2 * 3^2, and that c and d have 3^3 * 2. Combining 1 and 2 yields b has (at a minimum) 2^3 * 3^2, and thus a has 2^3 * 3 (and no more powers of 3 because otherwise | + | 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> |
Solution by JohnHankock | Solution by JohnHankock | ||
+ | |||
+ | == Solution 2.1 (updated with better notation)== | ||
+ | Do casework on <math>v_2</math> and <math>v_3.</math> Notice that we must have <math>v_3(a) = 1</math> and <math>v_2(d)=1</math> and the values of <math>b,d</math> does not matter. Therefore, <math>\gcd(d,a) = 6k,</math> where <math>k</math> is not divisible by <math>2</math> or <math>3.</math> We see that <math>13</math> is the only possible answer. | ||
+ | |||
+ | -Williamgolly | ||
+ | |||
+ | ==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: | ||
+ | <cmath>\min(a_2,b_2)=3</cmath> <cmath>\min(a_3,b_3)=1</cmath> <cmath>\min(b_2,c_2)=2</cmath> <cmath>\min(b_3,c_3)=2</cmath> <cmath>\min(a_2,c_2)=1</cmath> <cmath>\min(a_3,c_3)=3</cmath> . | ||
+ | |||
+ | (Unfinished) | ||
+ | ~Rowechen Zhong | ||
+ | |||
+ | ==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 + einstein | ||
+ | |||
+ | In the case where there can be 2 possible answers, we can do casework on gcd(d,a) | ||
+ | ~Williamgolly | ||
+ | |||
+ | ==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== | ||
+ | https://youtu.be/yjrqINsQP5c | ||
+ | |||
+ | ~savannahsolver | ||
+ | |||
+ | == Video Solution (Meta-Solving Technique) == | ||
+ | https://youtu.be/GmUWIXXf_uk?t=1003 | ||
+ | |||
+ | ~ pi_is_3.14 | ||
+ | |||
+ | ==See Also== | ||
+ | {{AMC10 box|year=2018|ab=A|num-b=21|num-a=23}} | ||
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 20:55, 2 February 2021
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 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
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.