Difference between revisions of "1987 AIME Problems/Problem 7"

Revision as of 22:14, 23 November 2007

Problem

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

Solution

Solution 1

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 10 possible triples: $(3, 3, 3)$ and three possibilities of each of the forms $(3, 3, n)$ , $(3, n, 3)$ and $(n, 3, 3)$ .

Since the exponents of 2 and 5 must satisfy these conditions independently, we have a total of $7 \cdot 10 = 070$ possible valid triples.

Solution 2

$1000 = 2^35^3$ and $2000 = 2^45^3$ . By looking at the prime factorization of $2000$ , $c$ must have a factor of $2^4$ . If $c$ has a factor of $5^3$ , then there are two cases: either (1) $a$ or $b = 5^32^3$ , or (2) one of $a$ and $b$ has a factor of $5^3$ and the other a factor of $2^3$ . For case 1, the other number will be in the form of $2^x5^y$ , so there are $4 \cdot 4 = 16$ possible such numbers; since this can be either $a$ or $b$ there are a total of $2(16)-1=31$ possibilities. For case 2, $a$ and $b$ are in the form of $2^35^x$ and $2^y5^3$ , with $x < 3$ and $y < 3$ (if they were equal to 3, it would overlap with case 1). Thus, there are $2(3 \cdot 3) = 18$ cases.

If $c$ does not have a factor of $5^3$ , then at least one of $a$ and $b$ must be $2^35^3$ , and both must have a factor of $5^3$ . Then, there are $4$ solutions possible just considering $a = 2^35^3$ , and a total of $4 \cdot 2 - 1 = 7$ possibilities. Multiplying by three, as $0 \le c \le 2$ , there are $7 \cdot 3 = 21$ . Together, that makes $31 + 18 + 21 = 70$ solutions for $(a, b, c)$ .

@@ Line 2: / Line 2: @@
 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>.
+__TOC__
 == Solution ==
-__TOC__
 ===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>.

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

Page

Toolbox

Search