Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2005 AIME II Problems/Problem 4"

 
(→‎Solution 2)
 
(10 intermediate revisions by 7 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
The director of a marching band wishes to place the members into a formation that includes all of them and has no unfilled positions. If they are arranged in a square formation, there are 5 members left over. The director realizes that if he arranges the group in a formation with 7 more rows than columns, there are no members left over. Find the maximum number of members this band can have.  
+
Find the number of [[positive integer]]s that are divisors of at least one of <math> 10^{10},15^7,18^{11}. </math>
−
== Solution ==
+
 
−
== See Also ==
+
== Solution 1 ==
−
*[[2005 AIME II Problems]]
+
<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>.
 +
 
 +
== Solution 2 ==
 +
 
 +
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.
 +
 
 +
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.
 +
 
 +
Adding up the two cases, there are <math>44+391=\boxed{435}</math> positive integers.
 +
 
 +
-alpha_2
 +
 
 +
== 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 17:36, 1 January 2024

Problem

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

Solution 1

$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 = \boxed{435}$.

Solution 2

We can rewrite the three numbers as $10^{10} = 2^{10}\cdot 5^{10}$, $15^7 = 3^7\cdot5^7$, and $18^{11} = 2^{11}\cdot3^{22}$. Assume that $n$ (a positive integer) is a divisor of one of the numbers. Therefore, $n$ can be expressed as ${p_1}^{e_1}$ or as ${p_2}^{e_2}{p_3}^{e_3}$ where $p_1$, $p_2$ are in $\{2,3,5\}$ and $e_1$, $e_2$ are positive integers.

If $n$ is the power of a single prime, then there are 11 possibilities ($2^1$ to $2^{11}$) for $p_1=2$, 22 possibilities ($3^1$ to $3^{22}$) for $p_1=3$, 10 possibilities ($5^1$ to $5^{10}$) for $p_1=5$, and 1 possibility if $n=1$. From this case, there are $11+22+10+1=44$ possibilities.

If $n$ 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 $10*10+11*22+7*7=100+242+49=391$ possibilities.

Adding up the two cases, there are $44+391=\boxed{435}$ 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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_AIME_II_Problems/Problem_4&oldid=209412"