Difference between revisions of "1987 AIME Problems/Problem 7"
m (→Solution: trying to organize my thoughts better..) |
Serengeti22 (talk | contribs) m (→Solution 1) |
||
(18 intermediate revisions by 9 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | Let <math> | + | Let <math>[r,s]</math> denote the [[least common multiple]] of [[positive integer]]s <math>r</math> and <math>s</math>. Find the number of [[ordered tuple | ordered triples]] <math>(a,b,c)</math> of positive integers for which <math>[a,b] = 1000</math>, <math>[b,c] = 2000</math>, and <math>[c,a] = 2000</math>. |
− | == Solution == | + | __TOC__ |
− | <math> | + | ==Solution 1== |
+ | It's clear that we must have <math>a = 2^j5^k</math>, <math>b = 2^m 5^n</math> and <math>c = 2^p5^q</math> for some [[nonnegative]] [[integer]]s <math>j, k, m, n, p, q</math>. Dealing first with the powers of 2: from the given conditions, <math>\max(j, m) = 3</math>, <math>\max(m, p) = \max(p, j) = 4</math>. Thus we must have <math>p = 4</math> and at least one of <math>m, j</math> equal to 3. This gives 7 possible triples <math>(j, m, p)</math>: <math>(0, 3, 4), (1, 3, 4), (2, 3, 4), (3, 3, 4), (3, 2, 4), (3, 1, 4)</math> and <math>(3, 0, 4)</math>. | ||
− | + | Now, for the powers of 5: we have <math>\max(k, n) = \max(n, q) = \max(q, k) = 3</math>. Thus, at least two of <math>k, n, q</math> must be equal to 3, and the other can take any value between 0 and 3. This gives us a total of 10 possible triples: <math>(3, 3, 3)</math> and three possibilities of each of the forms <math>(3, 3, n)</math>, <math>(3, n, 3)</math> and <math>(n, 3, 3)</math>. | |
+ | Since the [[exponent]]s of 2 and 5 must satisfy these conditions independently, we have a total of <math>7 \cdot 10 = 70</math> possible valid triples. | ||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | <math>1000 = 2^35^3</math> and <math>2000 = 2^45^3</math>. By [[LCM#Using prime factorization|looking at the prime factorization]] of <math>2000</math>, <math>c</math> must have a [[factor]] of <math>2^4</math>. If <math>c</math> has a factor of <math>5^3</math>, then there are two [[casework|cases]]: either (1) <math>a</math> or <math>b = 5^32^3</math>, or (2) one of <math>a</math> and <math>b</math> has a factor of <math>5^3</math> and the other a factor of <math>2^3</math>. For case 1, the other number will be in the form of <math>2^x5^y</math>, so there are <math>4 \cdot 4 = 16</math> possible such numbers; since this can be either <math>a</math> or <math>b</math> there are a total of <math>2(16)-1=31</math> possibilities. For case 2, <math>a</math> and <math>b</math> are in the form of <math>2^35^x</math> and <math>2^y5^3</math>, with <math>x < 3</math> and <math>y < 3</math> (if they were equal to 3, it would overlap with case 1). Thus, there are <math>2(3 \cdot 3) = 18</math> cases. | ||
+ | |||
+ | If <math>c</math> does not have a factor of <math>5^3</math>, then at least one of <math>a</math> and <math>b</math> must be <math>2^35^3</math>, and both must have a factor of <math>5^3</math>. Then, there are <math>4</math> solutions possible just considering <math>a = 2^35^3</math>, and a total of <math>4 \cdot 2 - 1 = 7</math> possibilities. Multiplying by three, as <math>0 \le c \le 2</math>, there are <math>7 \cdot 3 = 21</math>. Together, that makes <math>31 + 18 + 21 = 70</math> solutions for <math>(a, b, c)</math>.<!-- | ||
{| border="1px" style="width:25%" align=center | {| border="1px" style="width:25%" align=center | ||
|- | |- | ||
Line 19: | Line 27: | ||
|- | |- | ||
| rowspan = 1 | <math>5^x2^4</math> || <math>2^35^3</math> || <math>5^y2^z</math> || 24 | | rowspan = 1 | <math>5^x2^4</math> || <math>2^35^3</math> || <math>5^y2^z</math> || 24 | ||
− | |} | + | |}--> |
== See also == | == See also == | ||
{{AIME box|year=1987|num-b=6|num-a=8}} | {{AIME box|year=1987|num-b=6|num-a=8}} | ||
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] | ||
+ | [[Category:Intermediate Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 09:00, 18 June 2024
Problem
Let denote the least common multiple of positive integers and . Find the number of ordered triples of positive integers for which , , and .
Contents
[hide]Solution 1
It's clear that we must have , and for some nonnegative integers . Dealing first with the powers of 2: from the given conditions, , . Thus we must have and at least one of equal to 3. This gives 7 possible triples : and .
Now, for the powers of 5: we have . Thus, at least two of must be equal to 3, and the other can take any value between 0 and 3. This gives us a total of 10 possible triples: and three possibilities of each of the forms , and .
Since the exponents of 2 and 5 must satisfy these conditions independently, we have a total of possible valid triples.
Solution 2
and . By looking at the prime factorization of , must have a factor of . If has a factor of , then there are two cases: either (1) or , or (2) one of and has a factor of and the other a factor of . For case 1, the other number will be in the form of , so there are possible such numbers; since this can be either or there are a total of possibilities. For case 2, and are in the form of and , with and (if they were equal to 3, it would overlap with case 1). Thus, there are cases.
If does not have a factor of , then at least one of and must be , and both must have a factor of . Then, there are solutions possible just considering , and a total of possibilities. Multiplying by three, as , there are . Together, that makes solutions for .
See also
1987 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 6 |
Followed by Problem 8 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.