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 "Mock AIME 1 2007-2008 Problems/Problem 9"

(solution)
 
m (→‎Solution)
 
(One intermediate revision by one other user not shown)
Line 13: Line 13:
 
Clearly, to minimize <math>n</math>, we want to just use the prime factors <math>2,3,5</math>. The power of <math>2</math> must be divisible by <math>3,5</math>, and <math>2^{15}</math> works. Similarly, the powers of <math>3</math> and <math>5</math> must be <math>10</math> and <math>6</math>, respectively, both of which leave a residue of <math>1</math> upon division. Thus, we need the number of factors of <math>2^{15} \cdot 3^{10} \cdot 5^{6}</math> which are not multiples of <math>10</math>.
 
Clearly, to minimize <math>n</math>, we want to just use the prime factors <math>2,3,5</math>. The power of <math>2</math> must be divisible by <math>3,5</math>, and <math>2^{15}</math> works. Similarly, the powers of <math>3</math> and <math>5</math> must be <math>10</math> and <math>6</math>, respectively, both of which leave a residue of <math>1</math> upon division. Thus, we need the number of factors of <math>2^{15} \cdot 3^{10} \cdot 5^{6}</math> which are not multiples of <math>10</math>.
  
−
Applying the [[complement principle]], there are a total of <math>(15+1)(10+1)(6+1) = 1232</math> factors. We can draw a bijection between the number of divisors of <math>2^{15} \cdot 3^{10} \cdot 5^{6}</math> that are not divisible by <math>10</math> and the number of divisors of <math>2^{14} \cdot 3^{10} \cdot 5^{5}</math>, of which there are <math>(14+1)(10+1)(5+1) = 990</math>. The answer is <math>1232-990 = \boxed{242}</math>.
+
Applying the [[complement principle]], there are a total of <math>(15+1)(10+1)(6+1) = 1232</math> factors. We can draw a bijection between the number of divisors of <math>2^{15} \cdot 3^{10} \cdot 5^{6}</math> that are divisible by <math>10</math> and the number of divisors of <math>2^{14} \cdot 3^{10} \cdot 5^{5}</math> (as each of these divisors, when multiplied by 10, will provide a factor of the original number that is divisible by 10). There are <math>(14+1)(10+1)(5+1) = 990</math>. The answer is <math>1232-990 = \boxed{242}</math>.
  
 
== See also ==
 
== See also ==

Latest revision as of 23:32, 30 August 2015

Problem 9

Let $n$ represent the smallest integer that satisfies the following conditions:

$\frac n2$ is a perfect square.
$\frac n3$ is a perfect cube.
$\frac n5$ is a perfect fifth.

How many divisors does $n$ have that are not multiples of 10?

Solution

The first condition implies that the power of each prime factor of $n$ must be an even power (excluding $2$, which must be an odd power). The second condition implies that the power of each prime factor of $n$ must be divisible by $3$ (excluding $3$, which must leave a residue of $1$ upon division by $3$). The third condition implies that the power of each prime factor of $n$ must be divisible by $5$ (excluding $5$, which must leave a residue of $1$ upon division by $5$).

Clearly, to minimize $n$, we want to just use the prime factors $2,3,5$. The power of $2$ must be divisible by $3,5$, and $2^{15}$ works. Similarly, the powers of $3$ and $5$ must be $10$ and $6$, respectively, both of which leave a residue of $1$ upon division. Thus, we need the number of factors of $2^{15} \cdot 3^{10} \cdot 5^{6}$ which are not multiples of $10$.

Applying the complement principle, there are a total of $(15+1)(10+1)(6+1) = 1232$ factors. We can draw a bijection between the number of divisors of $2^{15} \cdot 3^{10} \cdot 5^{6}$ that are divisible by $10$ and the number of divisors of $2^{14} \cdot 3^{10} \cdot 5^{5}$ (as each of these divisors, when multiplied by 10, will provide a factor of the original number that is divisible by 10). There are $(14+1)(10+1)(5+1) = 990$. The answer is $1232-990 = \boxed{242}$.

See also

Mock AIME 1 2007-2008 (Problems, Source)
Preceded by
Problem 8 		Followed by
Problem 10
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_1_2007-2008_Problems/Problem_9&oldid=71887"