Difference between revisions of "2018 AMC 10A Problems/Problem 22"
(→Video Solution by Richard Rusczyk) |
Mannsnothot (talk | contribs) (Completed the unfinished solution) |
||
(17 intermediate revisions by 11 users not shown) | |||
Line 21: | Line 21: | ||
d &= 2\cdot 3^3\cdot z | d &= 2\cdot 3^3\cdot z | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | for some positive integers <math>w,x,y,z</math>. Now if <math>3</math> | + | 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> | <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>. | 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>. | ||
Line 27: | Line 27: | ||
== Solution 2 == | == Solution 2 == | ||
− | We can say that <math>a</math> and <math>b</math> 'have' <math>2^3 | + | We can say that <math>a</math> and <math>b</math> 'have' <math>2^3 \cdot 3</math>, that <math>b</math> and <math>c</math> have <math>2^2 \cdot 3^2</math>, and that <math>c</math> and <math>d</math> have <math>3^3 \cdot 2</math>. Combining <math>1</math> and <math>2</math> yields <math>b</math> has (at a minimum) <math>2^3 \cdot 3^2</math>, and thus <math>a</math> has <math>2^3 \cdot 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 \cdot 2^2</math>, and thus <math>d</math> has <math>3^3 \cdot 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 \cdot 3</math> and <math>d = 3^3 \cdot 2</math>. According to this base case, we have <math>\gcd(a, d) = 2 \cdot 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 \cdot 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 | + | ==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)== | ||
− | 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 | + | 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 <math>6</math> 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) | + | In the case where there can be 2 possible answers, we can do casework on <math>\gcd(d,a)</math> |
~Williamgolly | ~Williamgolly | ||
+ | |||
+ | ==Solution 5== | ||
+ | |||
+ | |||
+ | 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 | ||
+ | |||
+ | ==Solution 6== | ||
+ | |||
+ | <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 62: | Line 156: | ||
~savannahsolver | ~savannahsolver | ||
+ | |||
+ | == Video Solution by OmegaLearn (Meta-Solving Technique) == | ||
+ | https://youtu.be/GmUWIXXf_uk?t=1003 | ||
+ | |||
+ | ~ pi_is_3.14 | ||
==See Also== | ==See Also== |
Latest revision as of 03: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.