Difference between revisions of "1987 AIME Problems/Problem 7"
m |
|||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | Let <math>\displaystyle [r,s]</math> denote the least common multiple of positive | + | Let <math>\displaystyle [r,s]</math> denote the [[least common multiple]] of [[positive integer]]s <math>\displaystyle r</math> and <math>\displaystyle s</math>. Find the number of [[ordered triple]]s <math>\displaystyle (a,b,c)</math> of positive integers for which <math>\displaystyle [a,b] = 1000</math>, <math>\displaystyle [b,c] = 2000</math>, and <math>\displaystyle [c,a] = 2000</math>. |
== Solution == | == Solution == | ||
| + | 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 12 possible triples. | ||
| + | |||
| + | Since the [[exponent]]s of 2 and 5 must satisfy these conditions independently, we have a total of <math>7 \cdot 12 = 084</math> possible valid triples. | ||
== 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]] | ||
Revision as of 18:51, 15 February 2007
Problem
Let ![$\displaystyle [r,s]$](http://latex.artofproblemsolving.com/4/2/7/427cf30ddd37bf0e036473036ff4b4cbe7684821.png)
denote the least common multiple of positive integers 
and 
. Find the number of ordered triples 
of positive integers for which ![$\displaystyle [a,b] = 1000$](http://latex.artofproblemsolving.com/e/8/7/e87aa2708304964595a5039e2797295a5fb3fc8d.png)
, ![$\displaystyle [b,c] = 2000$](http://latex.artofproblemsolving.com/7/8/5/7857365927414a9f8bb3efea5eff9a950f189437.png)
, and ![$\displaystyle [c,a] = 2000$](http://latex.artofproblemsolving.com/a/0/5/a05efcd5db4b4375e7b3cf628f7bb37e2cb1a600.png)
.
Solution
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 12 possible triples.
Since the exponents of 2 and 5 must satisfy these conditions independently, we have a total of 
possible valid triples.
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 | ||
