Difference between revisions of "1998 IMO Problems/Problem 3"
Dabab kebab (talk | contribs) |
(→Solution) |
||
(6 intermediate revisions by one other user not shown) | |||
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=== | ===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= | + | 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>( | + | 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 k 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 k 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 (5/3 * 9/5), 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. |
− | P(k): It's possible to represent k as the product of fractions < | + | <math>P(k)</math>: It's possible to represent <math>k</math> as the product of fractions <math>(2n+1)/(n+1)</math> |
− | |||
− | |||
− | Since k is odd, </math>k+1 = 2^z * y | + | 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}</math>. | ||
+ | |||
+ | 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</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) | ||
+ | |||
+ | ==See Also== | ||
+ | |||
+ | {{IMO box|year=1998|num-b=2|num-a=4}} |
Latest revision as of 23:48, 18 November 2023
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)
See Also
1998 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |