Difference between revisions of "1987 AIME Problems/Problem 7"
(→Solution) |
(→Solution 2) |
||
Line 14: | Line 14: | ||
<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. | <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 = | + | 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 = 070</math> solutions for <math>(a, b, c)</math>.<!-- |
{| border="1px" style="width:25%" align=center | {| border="1px" style="width:25%" align=center | ||
|- | |- |
Revision as of 16:29, 18 February 2013
Problem
Let denote the least common multiple of positive integers
and
. Find the number of ordered triples
of positive integers for which
,
, and
.
Contents
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 |