Difference between revisions of "1995 AIME Problems/Problem 6"

m
(13 intermediate revisions by 9 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
Let <math>\displaystyle n=2^{31}3^{19}.</math>  How many positive integer divisors of <math>\displaystyle n^2</math> are less than <math>\displaystyle n_{}</math> but do not divide <math>\displaystyle n_{}</math>?
+
Let <math>n=2^{31}3^{19}.</math>  How many positive [[integer]] [[divisor]]s of <math>n^2</math> are less than <math>n_{}</math> but do not divide <math>n_{}</math>?
 +
 
 +
== Solution 1 ==
 +
We know that <math>n^2 = 2^{62}3^{38}</math> must have <math>(62+1)\times (38+1)</math> [[factor]]s by its [[prime factorization]]. If we group all of these factors (excluding <math>n</math>) into pairs that multiply to <math>n^2</math>, then one factor per pair is less than <math>n</math>, and so there are <math>\frac{63\times 39-1}{2} = 1228</math> factors of <math>n^2</math> that are less than <math>n</math>. There are <math>32\times20-1 = 639</math> factors of <math>n</math>, which clearly are less than <math>n</math>, but are still factors of <math>n</math>. Therefore, using complementary counting, there are <math>1228-639=\boxed{589}</math> factors of <math>n^2</math> that do not divide <math>n</math>.
 +
 
 +
== Solution 2 ==
 +
 
 +
Let <math>n=p_1^{k_1}p_2^{k_2}</math> for some prime <math>p_1,p_2</math>. Then <math>n^2</math> has <math>\frac{(2k_1+1)(2k_2+1)-1}{2}</math> factors less than <math>n</math>.
 +
 
 +
This simplifies to <math>\frac{4k_1k_2+2k_1+2k_2}{2}=2k_1k_2+k_1+k_2</math>.
 +
 
 +
The number of factors of <math>n</math> less than <math>n</math> is equal to <math>(k_1+1)(k_2+1)-1=k_1k_2+k_1+k_2</math>.
 +
 
 +
Thus, our general formula for <math>n=p_1^{k_1}p_2^{k_2}</math> is
 +
 
 +
Number of factors that satisfy the above <math>=(2k_1k_2+k_1+k_2)-(k_1k_2+k_1+k_2)=k_1k_2</math>
 +
 
 +
Incorporating this into our problem gives <math>19\times31=\boxed{589}</math>.
 +
 
 +
== Solution 3 ==
 +
 
 +
Consider divisors of <math>n^2: a,b</math> such that
 +
<math>ab=n^2</math>.
 +
WLOG, let <math>b\ge{a}</math> and <math>b=\frac{n}{a}</math>
 +
 
 +
Then, it is easy to see that <math>a</math> will always be less than <math>b</math> as we go down the divisor list of <math>n^2</math> until we hit <math>n</math>.
 +
 
 +
Therefore, the median divisor of <math>n^2</math> is <math>n</math>.
 +
 
 +
Then, there are <math>(63)(39)=2457</math> divisors of <math>n^2</math>. Exactly <math>\frac{2457-1}{2}=1228</math> of these divisors are <math><n</math>
 +
 
 +
There are <math>(32)(20)-1=639</math> divisors of <math>n</math> that are <math><n</math>.
 +
 
 +
Therefore, the answer is <math>1228-639=\boxed{589}</math>.
 +
 
  
== Solution ==
 
 
== See also ==
 
== See also ==
* [[1995 AIME Problems/Problem 5 | Previous problem]]
+
{{AIME box|year=1995|num-b=5|num-a=7}}
* [[1995 AIME Problems/Problem 7 | Next problem]]
+
 
* [[1995 AIME Problems]]
+
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Revision as of 00:46, 20 August 2018

Problem

Let $n=2^{31}3^{19}.$ How many positive integer divisors of $n^2$ are less than $n_{}$ but do not divide $n_{}$?

Solution 1

We know that $n^2 = 2^{62}3^{38}$ must have $(62+1)\times (38+1)$ factors by its prime factorization. If we group all of these factors (excluding $n$) into pairs that multiply to $n^2$, then one factor per pair is less than $n$, and so there are $\frac{63\times 39-1}{2} = 1228$ factors of $n^2$ that are less than $n$. There are $32\times20-1 = 639$ factors of $n$, which clearly are less than $n$, but are still factors of $n$. Therefore, using complementary counting, there are $1228-639=\boxed{589}$ factors of $n^2$ that do not divide $n$.

Solution 2

Let $n=p_1^{k_1}p_2^{k_2}$ for some prime $p_1,p_2$. Then $n^2$ has $\frac{(2k_1+1)(2k_2+1)-1}{2}$ factors less than $n$.

This simplifies to $\frac{4k_1k_2+2k_1+2k_2}{2}=2k_1k_2+k_1+k_2$.

The number of factors of $n$ less than $n$ is equal to $(k_1+1)(k_2+1)-1=k_1k_2+k_1+k_2$.

Thus, our general formula for $n=p_1^{k_1}p_2^{k_2}$ is

Number of factors that satisfy the above $=(2k_1k_2+k_1+k_2)-(k_1k_2+k_1+k_2)=k_1k_2$

Incorporating this into our problem gives $19\times31=\boxed{589}$.

Solution 3

Consider divisors of $n^2: a,b$ such that $ab=n^2$. WLOG, let $b\ge{a}$ and $b=\frac{n}{a}$

Then, it is easy to see that $a$ will always be less than $b$ as we go down the divisor list of $n^2$ until we hit $n$.

Therefore, the median divisor of $n^2$ is $n$.

Then, there are $(63)(39)=2457$ divisors of $n^2$. Exactly $\frac{2457-1}{2}=1228$ of these divisors are $<n$

There are $(32)(20)-1=639$ divisors of $n$ that are $<n$.

Therefore, the answer is $1228-639=\boxed{589}$.


See also

1995 AIME (ProblemsAnswer KeyResources)
Preceded by
Problem 5
Followed by
Problem 7
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