Difference between revisions of "1998 IMO Problems/Problem 3"
Dabab kebab (talk | contribs) |
Dabab kebab (talk | contribs) (→Problem and Solution) |
||
Line 1: | Line 1: | ||
===Problem=== | ===Problem=== | ||
− | For any positive integer n, let d(n) denote the number of positive divisors | + | For any positive integer <math>n</math>, let <math>d(n)</math> denote the number of positive divisors |
− | of n (including 1 and n itself). Determine all positive integers k such that | + | of <math>n</math> (including 1 and <math>n</math> itself). Determine all positive integers <math>k</math> such that |
− | <math>d(n^2)/d(n) = k</math> for some n. | + | <math>d(n^2)/d(n) = k</math> for some <math>n</math>. |
+ | |||
+ | ===Solution=== | ||
+ | |||
+ | First we must determine general values for d(n): | ||
+ | Let <math>n=p1 ^ a1 * p2 ^ a2 * .. * pc ^ ac</math>, if <math>d</math> is an arbitrary divisor of <math>n</math> then <math>d</math> must have the same prime factors of <math>n</math>, each with an exponent <math>b_i</math> being: <math>0\leq b_i\leq a_i</math>. | ||
+ | Hence there are <math>Ai + 1</math> choices for each exponent of Pi in the number d => there are <math>(a_1 + 1)(a_2 + 1)..(a_c + 1)</math> such d | ||
+ | |||
+ | <math>\implies d(n) = (a_1 + 1)(a_2+1)..(a_c+1)</math> where <math>a_i</math> are exponents of the prime numbers in the prime factorisation of <math>n</math>. | ||
+ | |||
+ | <math>\implies d(n^2)/d(n) = {(2a_1 + 1)(2a_2 + 1)..(2a_c + 1)}/{(a_1+1)..(a_c+1)}</math> | ||
+ | |||
+ | So we want to find all integers <math>k</math> that can be represented by the product of fractions of the form <math>(2n+1)/(n+1)</math> | ||
+ | Obviously <math>k</math> is odd as the numerator is always odd. | ||
+ | It's possible for 1 (1/1) and 3 <math>(5/3 * 9/5)</math>, which suggests that it may be possible for all odd integers, which we can show by induction. | ||
+ | |||
+ | <math>P(k)</math>: It's possible to represent <math>k</math> as the product of fractions <math>(2n+1)/(n+1)</math> | ||
+ | |||
+ | Base case: <math>k = 1: (2(0) + 1) / (0 + 1)</math> | ||
+ | Now assume that for <math>k\geq 3</math> it's possible for all odds < <math>k</math>. | ||
+ | |||
+ | Since <math>k</math> is odd, <math>k+1 = 2^zy</math> where <math>y</math> is odd and <math>y</math> < <math>k</math> | ||
+ | |||
+ | Let there be a number <math>x</math> s.t <math>k-y=x\implies k+1 = 2^z(k-x)\implies (2^zx+1)/(2^z-1)=k</math> | ||
+ | |||
+ | Also consider <math>k/y</math>. ISTS <math>k/y</math> can be represented by a product of fractions of the form <math>2n+1/n+1</math> in order to show <math>k</math> can be represented by product of fractions <math>2n+1/n+1</math>, since <math>y</math> can be represented in such a manner too. | ||
+ | |||
+ | <math>k/y = k/(k-x) = 1/(1 - x/k)</math> | ||
+ | |||
+ | Using our definition of <math>k</math> in terms of <math>x</math>: | ||
+ | |||
+ | <math>k/y = 1/{1 - {2^z-x}/{2^zx+1}} = {2^zx+1}/{x+1}</math> | ||
+ | |||
+ | And that is simply the product of fractions: <math>{2x+1}/{x+1} * {4x+1}/{2x+1} * .. * {2^zx+1}/{2^{z-1}x}. | ||
+ | |||
+ | We have shown that </math>k/y<math> can be written s.t it's a product of fractions of the form </math>{2n+!}/{n+1}\implies k<math> can be written in such a way too. | ||
+ | |||
+ | Hence we have shown that all odds less than </math>k<math> satisfies </math>P(n)\implies P(k)<math> is true. Since we have shown P(1) is true, it must hence be true for all odd integers. | ||
+ | |||
+ | Therefore, </math>d(n^2)/d(n) = k\iff k$ is odd. ∎ |
Revision as of 13:06, 2 April 2022
Problem
For any positive integer , let
denote the number of positive divisors
of
(including 1 and
itself). Determine all positive integers
such that
for some
.
Solution
First we must determine general values for d(n):
Let , if
is an arbitrary divisor of
then
must have the same prime factors of
, each with an exponent
being:
.
Hence there are
choices for each exponent of Pi in the number d => there are
such d
where
are exponents of the prime numbers in the prime factorisation of
.
So we want to find all integers that can be represented by the product of fractions of the form
Obviously
is odd as the numerator is always odd.
It's possible for 1 (1/1) and 3
, which suggests that it may be possible for all odd integers, which we can show by induction.
: It's possible to represent
as the product of fractions
Base case:
Now assume that for
it's possible for all odds <
.
Since is odd,
where
is odd and
<
Let there be a number s.t
Also consider . ISTS
can be represented by a product of fractions of the form
in order to show
can be represented by product of fractions
, since
can be represented in such a manner too.
Using our definition of in terms of
:
And that is simply the product of fractions: ${2x+1}/{x+1} * {4x+1}/{2x+1} * .. * {2^zx+1}/{2^{z-1}x}.
We have shown that$ (Error compiling LaTeX. Unknown error_msg)k/y{2n+!}/{n+1}\implies k$can be written in such a way too.
Hence we have shown that all odds less than$ (Error compiling LaTeX. Unknown error_msg)kP(n)\implies P(k)$is true. Since we have shown P(1) is true, it must hence be true for all odd integers.
Therefore,$ (Error compiling LaTeX. Unknown error_msg)d(n^2)/d(n) = k\iff k$ is odd. ∎