Difference between revisions of "1995 AIME Problems/Problem 6"
m (fbox not rendering for me, + box, grammar) |
Pi is 3.14 (talk | contribs) (→Solution 3) |
||
(12 intermediate revisions by 8 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | Let <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 == | + | == Solution 1 == |
− | We know that <math>n^2</math> must have <math> | + | 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>. | ||
+ | |||
+ | == Video Solution by OmegaLearn == | ||
+ | https://youtu.be/jgyyGeEKhwk?t=259 | ||
+ | |||
+ | ~ pi_is_3.14 | ||
== See also == | == See also == | ||
− | + | {{AIME box|year=1995|num-b=5|num-a=7}} | |
− | {{ | + | [[Category:Intermediate Number Theory Problems]] |
+ | {{MAA Notice}} |
Latest revision as of 08:14, 4 November 2022
Problem
Let How many positive integer divisors of
are less than
but do not divide
?
Solution 1
We know that must have
factors by its prime factorization. If we group all of these factors (excluding
) into pairs that multiply to
, then one factor per pair is less than
, and so there are
factors of
that are less than
. There are
factors of
, which clearly are less than
, but are still factors of
. Therefore, using complementary counting, there are
factors of
that do not divide
.
Solution 2
Let for some prime
. Then
has
factors less than
.
This simplifies to .
The number of factors of less than
is equal to
.
Thus, our general formula for is
Number of factors that satisfy the above
Incorporating this into our problem gives .
Solution 3
Consider divisors of such that
.
WLOG, let
and
Then, it is easy to see that will always be less than
as we go down the divisor list of
until we hit
.
Therefore, the median divisor of is
.
Then, there are divisors of
. Exactly
of these divisors are
There are divisors of
that are
.
Therefore, the answer is .
Video Solution by OmegaLearn
https://youtu.be/jgyyGeEKhwk?t=259
~ pi_is_3.14
See also
1995 AIME (Problems • Answer Key • Resources) | ||
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.