Difference between revisions of "1998 IMO Problems/Problem 3"
Dabab kebab (talk | contribs) (→Solution) |
Dabab kebab (talk | contribs) (→Solution) |
||
Line 7: | Line 7: | ||
===Solution=== | ===Solution=== | ||
− | First we must | + | First we must <math>d</math>etermine gener<math>a</math>l values for <math>d(n)</math>: |
− | Let <math>n=p1 ^ a1 * p2 ^ a2 * .. * pc ^ ac</math>, if <math>d</math> is an | + | Let <math>n=p1 ^ a1 * p2 ^ a2 * .. * pc ^ ac</math>, if <math>d</math> is an ar<math>b</math>itr<math>a</math>ry 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 | 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 | ||
Line 15: | Line 15: | ||
<math>\implies d(n^2)/d(n) = {(2a_1 + 1)(2a_2 + 1)..(2a_c + 1)}/{(a_1+1)..(a_c+1)}</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 | + | So we want to find all integers <math>k</math> that can <math>b</math>e 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. | 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. | 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. | ||
Line 43: | Line 43: | ||
Therefore, <math>d(n^2)/d(n) = k\iff k</math> is odd, for some n. I.E all odd <math>k</math> satisfy the condition posed in the question.∎ | Therefore, <math>d(n^2)/d(n) = k\iff k</math> is odd, for some n. I.E all odd <math>k</math> satisfy the condition posed in the question.∎ | ||
+ | |||
+ | |||
+ | |||
+ | -dabab_kebab (wrote this solution) |
Revision as of 13:09, 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 etermine gener
l values for
:
Let
, if
is an ar
itr
ry 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
e 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: .
We have shown that can be written s.t it's a product of fractions of the form
can be written in such a way too.
Hence we have shown that all odds less than satisfies
is true. Since we have shown P(1) is true, it must hence be true for all odd integers.
Therefore, is odd, for some n. I.E all odd
satisfy the condition posed in the question.∎
-dabab_kebab (wrote this solution)