Difference between revisions of "2018 AMC 10A Problems/Problem 22"
Ga mathelete (talk | contribs) m (→Solution 1) |
|||
(21 intermediate revisions by 15 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 4: | Line 6: | ||
== Solution 1 == | == 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 <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 31: | ||
Solution by JohnHankock | Solution by JohnHankock | ||
− | == Solution | + | == 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)== | |
− | |||
− | ==Solution | ||
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: | ||
Line 23: | Line 43: | ||
(Unfinished) | (Unfinished) | ||
~Rowechen Zhong | ~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 | ||
+ | |||
+ | ==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== | ||
+ | |||
+ | 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== | ==See Also== |
Latest revision as of 07:38, 8 May 2021
Contents
- 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.