Difference between revisions of "2016 AMC 10A Problems/Problem 25"
(→Problem) |
|||
(30 intermediate revisions by 21 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Problem | + | ==Problem== |
How many ordered triples <math>(x,y,z)</math> of positive integers satisfy <math>\text{lcm}(x,y) = 72, \text{lcm}(x,z) = 600</math> and <math>\text{lcm}(y,z)=900</math>? | How many ordered triples <math>(x,y,z)</math> of positive integers satisfy <math>\text{lcm}(x,y) = 72, \text{lcm}(x,z) = 600</math> and <math>\text{lcm}(y,z)=900</math>? | ||
<math>\textbf{(A)}\ 15\qquad\textbf{(B)}\ 16\qquad\textbf{(C)}\ 24\qquad\textbf{(D)}\ 27\qquad\textbf{(E)}\ 64</math> | <math>\textbf{(A)}\ 15\qquad\textbf{(B)}\ 16\qquad\textbf{(C)}\ 24\qquad\textbf{(D)}\ 27\qquad\textbf{(E)}\ 64</math> | ||
− | + | ==Solution 1== | |
+ | |||
+ | We prime factorize <math>72,600,</math> and <math>900</math>. The prime factorizations are <math>2^3\times 3^2</math>, <math>2^3\times 3\times 5^2</math> and <math>2^2\times 3^2\times 5^2</math>, respectively. Let <math>x=2^a\times 3^b\times 5^c</math>, <math>y=2^d\times 3^e\times 5^f</math> and <math>z=2^g\times 3^h\times 5^i</math>. We know that <cmath>\max(a,d)=3</cmath> <cmath>\max(b,e)=2</cmath> <cmath>\max(a,g)=3</cmath> <cmath>\max(b,h)=1</cmath> <cmath>\max(c,i)=2</cmath> <cmath>\max(d,g)=2</cmath> <cmath>\max(e,h)=2</cmath> and <math>c=f=0</math> since <math>\text{lcm}(x,y)</math> isn't a multiple of 5. Since <math>\max(d,g)=2</math> we know that <math>a=3</math>. We also know that since <math>\max(b,h)=1</math> that <math>e=2</math>. So now some equations have become useless to us...let's take them out. <cmath>\max(b,h)=1</cmath> <cmath>\max(d,g)=2</cmath> are the only two important ones left. We do casework on each now. If <math>\max(b,h)=1</math> then <math>(b,h)=(1,0),(0,1)</math> or <math>(1,1)</math>. Similarly if <math>\max(d,g)=2</math> then <math>(d,g)=(2,0),(2,1),(2,2),(1,2),(0,2)</math>. Thus our answer is <math>5\times 3=\boxed{\textbf{(A)15}}</math>. | ||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | It is well known that if the <math>\text{lcm}(a,b)=c</math> and <math>c</math> can be written as <math>p_1^ap_2^bp_3^c\dots</math>, then the highest power of all prime numbers <math>p_1,p_2,p_3\dots</math> must divide into either <math>a</math> and/or <math>b</math>. Or else a lower <math>c_0=p_1^{a-\epsilon}p_2^{b-\epsilon}p_3^{c-\epsilon}\dots</math> is the <math>\text{lcm}</math>. | ||
+ | |||
+ | Start from <math>x</math>:<math>\text{lcm}(x,y)=72</math> so <math>8\mid x</math> or <math>9\mid x</math> or both. But <math>9\nmid x</math> because <math>\text{lcm}(x,z)=600</math> and <math>9\nmid 600</math>. | ||
+ | So <math>x=8,24</math>. | ||
+ | |||
+ | <math>y</math> can be <math>9,18,36</math> in both cases of <math>x</math> but NOT <math>72</math> because <math>\text{lcm}(y,z)=900</math> and <math>72\nmid 900</math>. | ||
+ | |||
+ | So there are six sets of <math>x,y</math> and we will list all possible values of <math>z</math> based on those. | ||
+ | |||
+ | <math>25\mid z</math> because <math>z</math> must source all powers of <math>5</math>. <math>z\in\{25,50,75,100,150,300\}</math>. <math>z\ne\{200,225\}</math> because of <math>\text{lcm}</math> restrictions. | ||
+ | |||
+ | By different sourcing of powers of <math>2</math> and <math>3</math>, | ||
+ | |||
+ | <cmath>(8,9):z=300</cmath> | ||
+ | <cmath>(8,18):z=300</cmath> | ||
+ | <cmath>(8,36):z=75,150,300</cmath> | ||
+ | <cmath>(24,9):z=100,300</cmath> | ||
+ | <cmath>(24,18):z=100,300</cmath> | ||
+ | <cmath>(24,36):z=25,50,75,100,150,300</cmath> | ||
+ | |||
+ | <math>z=100</math> is "enabled" by <math>x</math> sourcing the power of <math>3</math>. <math>z=75,150</math> is uncovered by <math>y</math> sourcing all powers of <math>2</math>. And <math>z=25,50</math> is uncovered by <math>x</math> and <math>y</math> both at full power capacity. | ||
+ | |||
+ | Counting the cases, <math>1+1+3+2+2+6=\boxed{\textbf{(A) }15}.</math> | ||
+ | |||
+ | ==Solution 3 (Less Casework!)== | ||
+ | As said in previous solutions, start by factoring <math>72, 600,</math> and <math>900</math>. The prime factorizations are as follows: <cmath>72=2^3\cdot 3^2,</cmath> <cmath>600=2^3\cdot 3\cdot 5^2,</cmath> <cmath> \text{and } 900=2^2\cdot 3^2\cdot 5^2</cmath> | ||
+ | To organize <math>x,y, \text{ and } z</math> and their respective LCMs in a simpler way, we can draw a triangle as follows such that <math>x,y, \text{and } z</math> are the vertices and the LCMs are on the edges. | ||
+ | |||
+ | <asy> | ||
+ | //Variable Declarations | ||
+ | defaultpen(0.45); | ||
+ | size(200pt); | ||
+ | fontsize(15pt); | ||
+ | pair X, Y, Z; | ||
+ | real R; | ||
+ | path tri; | ||
+ | |||
+ | //Variable Definitions | ||
+ | R = 1; | ||
+ | X = R*dir(90); | ||
+ | Y = R*dir(210); | ||
+ | Z = R*dir(-30); | ||
+ | tri = X--Y--Z--cycle; | ||
+ | |||
+ | //Diagram | ||
+ | draw(tri); | ||
+ | label("$x$",X,N); | ||
+ | label("$y$",Y,SW); | ||
+ | label("$z$",Z,SE); | ||
+ | label("$2^33^25^0$",X--Y,2W); | ||
+ | label("$2^33^15^2$",X--Z,2E); | ||
+ | label("$2^23^25^2$",Y--Z,2S); | ||
+ | </asy> | ||
+ | |||
+ | Now we can split this triangle into three separate ones for each of the three different prime factors <math>2,3, \text{and } 5</math>. | ||
+ | |||
+ | <asy> | ||
+ | //Variable Declarations | ||
+ | defaultpen(0.45); | ||
+ | size(200pt); | ||
+ | fontsize(15pt); | ||
+ | pair X, Y, Z; | ||
+ | real R; | ||
+ | path tri; | ||
+ | |||
+ | //Variable Definitions | ||
+ | R = 1; | ||
+ | X = R*dir(90); | ||
+ | Y = R*dir(210); | ||
+ | Z = R*dir(-30); | ||
+ | tri = X--Y--Z--cycle; | ||
+ | |||
+ | //Diagram | ||
+ | draw(tri); | ||
+ | label("$x$",X,N); | ||
+ | label("$y$",Y,SW); | ||
+ | label("$z$",Z,SE); | ||
+ | label("$2^3$",X--Y,2W); | ||
+ | label("$2^3$",X--Z,2E); | ||
+ | label("$2^2$",Y--Z,2S); | ||
+ | </asy> | ||
+ | |||
+ | Analyzing for powers of <math>2</math>, it is quite obvious that <math>x</math> must have <math>2^3</math> as one of its factors since neither <math>y \text{ nor } z</math> can have a power of <math>2</math> exceeding <math>2</math>. Turning towards the vertices <math>y</math> and <math>z</math>, we know at least one of them must have <math>2^2</math> as its factors. Therefore, we have <math>5</math> ways for the powers of <math>2</math> for <math>y \text{ and } z</math> since the only ones that satisfy the previous conditions are for ordered pairs <math>(y,z) \{(2,0)(2,1)(0,2)(1,2)(2,2)\}</math>. | ||
+ | |||
+ | <asy> | ||
+ | //Variable Declarations | ||
+ | defaultpen(0.45); | ||
+ | size(200pt); | ||
+ | fontsize(15pt); | ||
+ | pair X, Y, Z; | ||
+ | real R; | ||
+ | path tri; | ||
+ | |||
+ | //Variable Definitions | ||
+ | R = 1; | ||
+ | X = R*dir(90); | ||
+ | Y = R*dir(210); | ||
+ | Z = R*dir(-30); | ||
+ | tri = X--Y--Z--cycle; | ||
+ | |||
+ | //Diagram | ||
+ | draw(tri); | ||
+ | label("$x$",X,N); | ||
+ | label("$y$",Y,SW); | ||
+ | label("$z$",Z,SE); | ||
+ | label("$3^2$",X--Y,2W); | ||
+ | label("$3^1$",X--Z,2E); | ||
+ | label("$3^2$",Y--Z,2S); | ||
+ | </asy> | ||
+ | |||
+ | Using the same logic as we did for powers of <math>2</math>, it becomes quite easy to note that <math>y</math> must have <math>3^2</math> as one of its factors. Moving onto <math>x \text{ and } z</math>, we can use the same logic to find the only ordered pairs <math>(x,z)</math> that will work are <math>\{(1,0)(0,1)(1,1)\}</math>. | ||
+ | |||
+ | The final and last case is the powers of <math>5</math>. | ||
+ | |||
+ | <asy> | ||
+ | //Variable Declarations | ||
+ | defaultpen(0.45); | ||
+ | size(200pt); | ||
+ | fontsize(15pt); | ||
+ | pair X, Y, Z; | ||
+ | real R; | ||
+ | path tri; | ||
+ | |||
+ | //Variable Definitions | ||
+ | R = 1; | ||
+ | X = R*dir(90); | ||
+ | Y = R*dir(210); | ||
+ | Z = R*dir(-30); | ||
+ | tri = X--Y--Z--cycle; | ||
+ | |||
+ | //Diagram | ||
+ | draw(tri); | ||
+ | label("$x$",X,N); | ||
+ | label("$y$",Y,SW); | ||
+ | label("$z$",Z,SE); | ||
+ | label("$5^0$",X--Y,2W); | ||
+ | label("$5^2$",X--Z,2E); | ||
+ | label("$5^2$",Y--Z,2S); | ||
+ | </asy> | ||
+ | |||
+ | This is actually quite a simple case since we know <math>z</math> must have <math>5^2</math> as part of its factorization while <math>x \text{ and } y</math> cannot have a factor of <math>5</math> in their prime factorization. | ||
+ | |||
+ | Multiplying all the possible arrangements for prime factors <math>2,3, \text{ and } 5</math>, we get the answer: | ||
+ | <cmath>5\cdot3\cdot1=\boxed{\textbf{(A) }15}</cmath> | ||
+ | |||
+ | (Diagrams by ColtsFan10) | ||
+ | |||
+ | ==Video Solution== | ||
+ | |||
+ | https://www.youtube.com/watch?v=ja1KZ8tVwI8 | ||
==See Also== | ==See Also== | ||
+ | |||
{{AMC10 box|year=2016|ab=A|num-b=24|after=Last Problem}} | {{AMC10 box|year=2016|ab=A|num-b=24|after=Last Problem}} | ||
+ | {{AMC12 box|year=2016|ab=A|num-b=21|num-a=23}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 23:15, 29 January 2021
Contents
Problem
How many ordered triples of positive integers satisfy and ?
Solution 1
We prime factorize and . The prime factorizations are , and , respectively. Let , and . We know that and since isn't a multiple of 5. Since we know that . We also know that since that . So now some equations have become useless to us...let's take them out. are the only two important ones left. We do casework on each now. If then or . Similarly if then . Thus our answer is .
Solution 2
It is well known that if the and can be written as , then the highest power of all prime numbers must divide into either and/or . Or else a lower is the .
Start from : so or or both. But because and . So .
can be in both cases of but NOT because and .
So there are six sets of and we will list all possible values of based on those.
because must source all powers of . . because of restrictions.
By different sourcing of powers of and ,
is "enabled" by sourcing the power of . is uncovered by sourcing all powers of . And is uncovered by and both at full power capacity.
Counting the cases,
Solution 3 (Less Casework!)
As said in previous solutions, start by factoring and . The prime factorizations are as follows: To organize and their respective LCMs in a simpler way, we can draw a triangle as follows such that are the vertices and the LCMs are on the edges.
Now we can split this triangle into three separate ones for each of the three different prime factors .
Analyzing for powers of , it is quite obvious that must have as one of its factors since neither can have a power of exceeding . Turning towards the vertices and , we know at least one of them must have as its factors. Therefore, we have ways for the powers of for since the only ones that satisfy the previous conditions are for ordered pairs .
Using the same logic as we did for powers of , it becomes quite easy to note that must have as one of its factors. Moving onto , we can use the same logic to find the only ordered pairs that will work are .
The final and last case is the powers of .
This is actually quite a simple case since we know must have as part of its factorization while cannot have a factor of in their prime factorization.
Multiplying all the possible arrangements for prime factors , we get the answer:
(Diagrams by ColtsFan10)
Video Solution
https://www.youtube.com/watch?v=ja1KZ8tVwI8
See Also
2016 AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 24 |
Followed by Last Problem | |
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 |
2016 AMC 12A (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 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.