Difference between revisions of "Mock AIME 1 2007-2008 Problems/Problem 9"

m (Solution)
m (Solution)
 
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 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 00:32, 31 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