Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(solution)
m (→‎Solution: trying to organize my thoughts better..)
Line 5: Line 5:
 
<math>\displaystyle 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>\displaystyle 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 + 24 = 70</math> solutions for <math>(a, b, c)</math>.
+
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 = 70</math> solutions for <math>(a, b, c)</math>.
 +
 
 +
{| border="1px" style="width:25%" align=center
 +
|-
 +
! c || a || b || solutions
 +
|-
 +
| rowspan = 2 | <math>5^32^4</math>
 +
| <math>2^35^3</math>
 +
| <math>5^x2^y</math>
 +
| 31
 +
|-
 +
| <math>2^x5^3</math> || <math>2^35^y</math> || 18
 +
|-
 +
| rowspan = 1 | <math>5^x2^4</math> || <math>2^35^3</math> || <math>5^y2^z</math> || 24
 +
|}
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=1987|num-b=6|num-a=8}}
 
{{AIME box|year=1987|num-b=6|num-a=8}}

Revision as of 19:47, 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

$\displaystyle 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)$.

c a b solutions
$5^32^4$ $2^35^3$ $5^x2^y$ 31
$2^x5^3$ $2^35^y$ 18
$5^x2^4$ $2^35^3$ $5^y2^z$ 24

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1987_AIME_Problems/Problem_7&oldid=13251"