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"

 
m (Boxed the final answer.)
(7 intermediate revisions by 5 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 ==
 
== Solution ==
−
== See Also ==
+
<math>10^{10} = 2^{10}\cdot 5^{10}</math> so <math>10^{10}</math> has <math>11\cdot11 = 121</math> [[divisor]]s.
−
*[[2005 AIME II Problems]]
+
 
 +
<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}}

Revision as of 01:17, 30 July 2015

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

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=71388"