Difference between revisions of "1987 AIME Problems/Problem 7"
(place differently) |
m (hmm.. by convention I tend to put the TOC here, but I've got no issue w/ changing that I suppose) |
||
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>. | 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 == | == Solution == | ||
− | |||
− | |||
===Solution 1=== | ===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>. | 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>. |
Revision as of 23:19, 23 November 2007
Problem
Let denote the least common multiple of positive integers
and
. Find the number of ordered triples
of positive integers for which
,
, and
.
Solution
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 |