Difference between revisions of "2005 AIME II Problems/Problem 4"
Ragnarok23 (talk | contribs) |
m (Boxed the final answer.) |
||
(7 intermediate revisions by 5 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | + | Find the number of [[positive integer]]s that are divisors of at least one of <math> 10^{10},15^7,18^{11}. </math> | |
+ | |||
== Solution == | == Solution == | ||
− | == | + | <math>10^{10} = 2^{10}\cdot 5^{10}</math> so <math>10^{10}</math> has <math>11\cdot11 = 121</math> [[divisor]]s. |
− | + | ||
+ | <math>15^7 = 3^7\cdot5^7</math> so <math>15^7</math> has <math>8\cdot8 = 64</math> divisors. | ||
+ | |||
+ | <math>18^{11} = 2^{11}\cdot3^{22}</math> so <math>18^{11}</math> has <math>12\cdot23 = 276</math> divisors. | ||
+ | |||
+ | Now, we use the [[Principle of Inclusion-Exclusion]]. We have <math>121 + 64 + 276</math> 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 divisor]]s. | ||
+ | |||
+ | <math>\gcd(10^{10},15^7) = 5^7 </math> which has 8 divisors. | ||
+ | |||
+ | <math>\gcd(15^7, 18^{11}) = 3^7 </math> which has 8 divisors. | ||
+ | |||
+ | <math>\gcd(18^{11}, 10^{10}) = 2^{10} </math> which has 11 divisors. | ||
+ | |||
+ | So now we have <math>121 + 64 + 276 - 8 -8 -11</math> 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 <math>121 + 64 + 276 - 8 - 8 - 11 + 1 = \boxed{435}</math>. | ||
+ | |||
+ | == See also == | ||
+ | {{AIME box|year=2005|n=II|num-b=3|num-a=5}} | ||
+ | |||
+ | [[Category:Introductory Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 00:17, 30 July 2015
Problem
Find the number of positive integers that are divisors of at least one of
Solution
so has divisors.
so has divisors.
so has divisors.
Now, we use the Principle of Inclusion-Exclusion. We have 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.
which has 8 divisors.
which has 8 divisors.
which has 11 divisors.
So now we have 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 .
See also
2005 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
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.