Difference between revisions of "2016 AMC 10A Problems/Problem 25"
m (→Solution) |
m (→Problem) |
||
(31 intermediate revisions by 20 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 | + | How many ordered triples <math>(x,y,z)</math> of positive integers satisfy <math>\text{lcm}(x,y) = 72, \text{lcm}(x,z) = 600 \text{ and 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== | + | ==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{15 (A)}</math>. | + | 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}} | {{AMC12 box|year=2016|ab=A|num-b=21|num-a=23}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 09:28, 5 September 2022
Contents
Problem
How many ordered triples of positive integers satisfy
?
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.