Difference between revisions of "2004 AIME II Problems/Problem 8"
(→Solution 2 (bash)) |
|||
| (21 intermediate revisions by 14 users not shown) | |||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | How many positive integer divisors of <math> 2004^{2004} </math> are divisible by exactly 2004 positive integers? | + | How many positive integer divisors of <math>2004^{2004}</math> are divisible by exactly 2004 positive integers? |
| − | == Solution == | + | == Solution 1 == |
| + | The [[prime factorization]] of 2004 is <math>2^2\cdot 3\cdot 167</math>. Thus the prime factorization of <math>2004^{2004}</math> is <math>2^{4008}\cdot 3^{2004}\cdot 167^{2004}</math>. | ||
| + | |||
| + | We can [[divisor function | count the number of divisors]] of a number by multiplying together one more than each of the [[exponentiation | exponents]] of the prime factors in its prime factorization. For example, the number of divisors of <math>2004=2^2\cdot 3^1\cdot 167^1</math> is <math>(2+1)(1+1)(1+1)=12</math>. | ||
| + | |||
| + | A positive integer divisor of <math>2004^{2004}</math> will be of the form <math>2^a\cdot 3^b\cdot 167^c</math>. Thus we need to find how many <math>(a,b,c)</math> satisfy | ||
| + | |||
| + | <center><math>(a+1)(b+1)(c+1)=2^2\cdot 3\cdot 167.</math></center> | ||
| + | |||
| + | We can think of this as [[partition]]ing the exponents to <math>a+1,</math> <math>b+1,</math> and <math>c+1</math>. So let's partition the 2's first. There are two 2's so this is equivalent to partitioning two items in three containers. We can do this in <math>{4 \choose 2} = 6</math> ways. We can partition the 3 in three ways and likewise we can partition the 167 in three ways. So we have <math>6\cdot 3\cdot 3 = \boxed{54}</math> as our answer. | ||
| + | |||
| + | ==Solution 2 (bash)== | ||
| + | Clearly we need to find a group of numbers that multiply to 2004. We can list them all out since we know that 2004 is only <math>167 \cdot 2^2 \cdot 3</math>. | ||
| + | |||
| + | 167, 2, 2, 3 | ||
| + | |||
| + | 4, 3, 167 | ||
| + | |||
| + | 12, 167 | ||
| + | |||
| + | 4, 501 | ||
| + | |||
| + | 2, 1002 | ||
| + | |||
| + | 2, 3, 334 | ||
| + | |||
| + | 2, 2, 501* | ||
| + | |||
| + | 6, 2, 167 | ||
| + | |||
| + | 3, 668 | ||
| + | |||
| + | 6, 334 | ||
| + | |||
| + | 2004* | ||
| + | |||
| + | To begin, the first multiple doesn't work because there are only 3 prime divisors of 2004. We can apply all multiples because the prime factorization of <math>2004^{2004}</math> is <math>2^{4008} \cdot 3^{2004} \cdot 167^{2004}.</math> Every multiple has six ways of distributing numbers to become powers of 167, 3, and 2, except for the ones with a star. | ||
| + | For a single power of 2004, we have three choices (2, 3, and 167) to give a power of 2003 to. | ||
| + | For 2, 2, 501, there are three choices to give a power of 500 to and the rest get a power of 1. | ||
| + | |||
| + | Therefore we have <math>8 \cdot 6</math> normal multiples and <math>3 \cdot 2</math> "half" multiples. Sum to get <math>\boxed{54}</math> as our answer. | ||
== See also == | == See also == | ||
| − | + | {{AIME box|year=2004|n=II|num-b=7|num-a=9}} | |
| + | |||
| + | [[Category:Intermediate Number Theory Problems]] | ||
| + | [[Category:Intermediate Combinatorics Problems]] | ||
| + | {{MAA Notice}} | ||
Latest revision as of 18:58, 24 December 2024
Problem
How many positive integer divisors of 
are divisible by exactly 2004 positive integers?
Solution 1
The prime factorization of 2004 is 
. Thus the prime factorization of is 
.
We can count the number of divisors of a number by multiplying together one more than each of the exponents of the prime factors in its prime factorization. For example, the number of divisors of 
is 
.
A positive integer divisor of will be of the form 
. Thus we need to find how many 
satisfy
We can think of this as partitioning the exponents to 
and 
. So let's partition the 2's first. There are two 2's so this is equivalent to partitioning two items in three containers. We can do this in 
ways. We can partition the 3 in three ways and likewise we can partition the 167 in three ways. So we have 
as our answer.
Solution 2 (bash)
Clearly we need to find a group of numbers that multiply to 2004. We can list them all out since we know that 2004 is only 
.
167, 2, 2, 3
4, 3, 167
12, 167
4, 501
2, 1002
2, 3, 334
2, 2, 501*
6, 2, 167
3, 668
6, 334
2004*
To begin, the first multiple doesn't work because there are only 3 prime divisors of 2004. We can apply all multiples because the prime factorization of is 
Every multiple has six ways of distributing numbers to become powers of 167, 3, and 2, except for the ones with a star.
For a single power of 2004, we have three choices (2, 3, and 167) to give a power of 2003 to.
For 2, 2, 501, there are three choices to give a power of 500 to and the rest get a power of 1.
Therefore we have 
normal multiples and 
"half" multiples. Sum to get 
as our answer.
See also
| 2004 AIME II (Problems • Answer Key • Resources) | ||
| Preceded by Problem 7 |
Followed by Problem 9 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
