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 integers <math>\displaystyle r</math> and <math>\displaystyle s</math>.  Find the number of ordered triples <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>.
+
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 ==
* [[1987 AIME Problems]]
 
 
 
{{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 19:51, 15 February 2007

Problem

Let $\displaystyle [r,s]$ denote the least common multiple of positive integers $\displaystyle r$ and $\displaystyle s$. Find the number of ordered triples $\displaystyle (a,b,c)$ of positive integers for which $\displaystyle [a,b] = 1000$, $\displaystyle [b,c] = 2000$, and $\displaystyle [c,a] = 2000$.

Solution

It's clear that we must have $a = 2^j5^k$, $b = 2^m 5^n$ and $c = 2^p5^q$ for some nonnegative integers $j, k, m, n, p, q$. Dealing first with the powers of 2: from the given conditions, $\max(j, m) = 3$, $\max(m, p) = \max(p, j) = 4$. Thus we must have $p = 4$ and at least one of $m, j$ equal to 3. This gives 7 possible triples $(j, m, p)$: $(0, 3, 4), (1, 3, 4), (2, 3, 4), (3, 3, 4), (3, 2, 4), (3, 1, 4)$ and $(3, 0, 4)$.

Now, for the powers of 5: we have $\max(k, n) = \max(n, q) = \max(q, k) = 3$. Thus, at least two of $k, n, q$ 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 $7 \cdot 12 = 084$ possible valid triples.

See also

1987 AIME (ProblemsAnswer KeyResources)
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