2004 AIME II Problems/Problem 8
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.