Difference between revisions of "2005 AIME II Problems/Problem 4"
(new solution) |
(→Solution 2) |
||
(One intermediate revision by the same user not shown) | |||
Line 23: | Line 23: | ||
We can rewrite the three numbers as <math>10^{10} = 2^{10}\cdot 5^{10}</math>, <math>15^7 = 3^7\cdot5^7</math>, and <math>18^{11} = 2^{11}\cdot3^{22}</math>. | We can rewrite the three numbers as <math>10^{10} = 2^{10}\cdot 5^{10}</math>, <math>15^7 = 3^7\cdot5^7</math>, and <math>18^{11} = 2^{11}\cdot3^{22}</math>. | ||
Assume that <math>n</math> (a positive integer) is a divisor of one of the numbers. Therefore, <math>n</math> can be expressed as <math>{p_1}^{e_1}</math> or as <math>{p_2}^{e_2}{p_3}^{e_3}</math> where <math>p_1</math>, <math>p_2</math> are in <math>\{2,3,5\}</math> and <math>e_1</math>, <math>e_2</math> are positive integers. | Assume that <math>n</math> (a positive integer) is a divisor of one of the numbers. Therefore, <math>n</math> can be expressed as <math>{p_1}^{e_1}</math> or as <math>{p_2}^{e_2}{p_3}^{e_3}</math> where <math>p_1</math>, <math>p_2</math> are in <math>\{2,3,5\}</math> and <math>e_1</math>, <math>e_2</math> are positive integers. | ||
+ | |||
If <math>n</math> is the power of a single prime, then there are 11 possibilities (<math>2^1</math> to <math>2^{11}</math>) for <math>p_1=2</math>, 22 possibilities (<math>3^1</math> to <math>3^{22}</math>) for <math>p_1=3</math>, 10 possibilities (<math>5^1</math> to <math>5^{10}</math>) for <math>p_1=5</math>, and 1 possibility if <math>n=1</math>. From this case, there are <math>11+22+10+1=44</math> possibilities. | If <math>n</math> is the power of a single prime, then there are 11 possibilities (<math>2^1</math> to <math>2^{11}</math>) for <math>p_1=2</math>, 22 possibilities (<math>3^1</math> to <math>3^{22}</math>) for <math>p_1=3</math>, 10 possibilities (<math>5^1</math> to <math>5^{10}</math>) for <math>p_1=5</math>, and 1 possibility if <math>n=1</math>. From this case, there are <math>11+22+10+1=44</math> possibilities. | ||
+ | |||
If <math>n</math> is the product of the powers of two primes, then we can just multiply the exponents of each rewritten product to get the number of possibilities, since each exponent of the product must be greater than 0. From this case, there are <math>10*10+11*22+7*7=100+242+49=391</math> possibilities. | If <math>n</math> is the product of the powers of two primes, then we can just multiply the exponents of each rewritten product to get the number of possibilities, since each exponent of the product must be greater than 0. From this case, there are <math>10*10+11*22+7*7=100+242+49=391</math> possibilities. | ||
+ | |||
Adding up the two cases, there are <math>44+391=\boxed{435}</math> positive integers. | Adding up the two cases, there are <math>44+391=\boxed{435}</math> positive integers. | ||
+ | |||
+ | -alpha_2 | ||
== See also == | == See also == |
Latest revision as of 18:36, 1 January 2024
Contents
Problem
Find the number of positive integers that are divisors of at least one of
Solution 1
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
.
Solution 2
We can rewrite the three numbers as ,
, and
.
Assume that
(a positive integer) is a divisor of one of the numbers. Therefore,
can be expressed as
or as
where
,
are in
and
,
are positive integers.
If is the power of a single prime, then there are 11 possibilities (
to
) for
, 22 possibilities (
to
) for
, 10 possibilities (
to
) for
, and 1 possibility if
. From this case, there are
possibilities.
If is the product of the powers of two primes, then we can just multiply the exponents of each rewritten product to get the number of possibilities, since each exponent of the product must be greater than 0. From this case, there are
possibilities.
Adding up the two cases, there are positive integers.
-alpha_2
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.