2005 AIME II Problems/Problem 4

From AoPSWiki

Problem

Find the number of positive integers that are divisors of at least one of $10^{10},15^7,18^{11}.$

Solution

$10^{10} = 2^{10}\cdot 5^{10}$ so $10^{10}$ has $11\cdot11 = 121$ divisors.

$15^7 = 3^7\cdot5^7$ so $15^7$ has $8\cdot8 = 64$ divisors.

$18^{11} = 2^{11}\cdot3^{22}$ so $18^{11}$ has $12\cdot23 = 276$ divisors.

Now, we use the Principle of Inclusion-Exclusion. We have $121 + 64 + 276$ total potential divisors so far, but we've overcounted those factors which divide two or more of our three numbers. Thus, we must subtract off the divisors of their pair-wise greatest common divisors.

$\gcd(10^{10},15^7) = 5^7$ which has 8 divisors.

$\gcd(15^7, 18^{11}) = 3^7$ which has 8 divisors.

$\gcd(18^{11}, 10^{10}) = 2^{10}$ which has 11 divisors.

So now we have $121 + 64 + 276 - 8 -8 -11$ potential divisors. However, we've now undercounted those factors which divide all three of our numbers. Luckily, we see that the only such factor is 1, so we must add 1 to our previous sum to get an answer of $121 + 64 + 276 - 8 - 8 - 11 + 1 = 435$ .

2005 AIME II (Problems • Resources)
Preceded by Problem 3	Followed by Problem 5
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Personal tools

Navigation

Search

Toolbox

2005 AIME II Problems/Problem 4

From AoPSWiki

Problem

Solution

See also