Difference between revisions of "1998 IMO Problems/Problem 3"
m |
Dabab kebab (talk | contribs) |
||
| Line 1: | Line 1: | ||
| + | ===Problem=== | ||
| + | |||
For any positive integer n, let d(n) denote the number of positive divisors | For any positive integer n, let d(n) denote the number of positive divisors | ||
of n (including 1 and n itself). Determine all positive integers k such that | of n (including 1 and n itself). Determine all positive integers k such that | ||
| − | d(n^2)/d(n) = k for some n. | + | <math>d(n^2)/d(n) = k</math> for some n. |
| + | |||
| + | ===Solution=== | ||
| + | |||
| + | First we must determine general values for d(n): | ||
| + | Let <math>n=P1^(A1) * P2^(A2) * .. * Pc^(Ac)</math>, if d is an arbitrary divisor of n then d must have the same prime factors of n, each with an exponent <math>Bi</math> being: <math>0\leq Bi\leq Ai</math>. | ||
| + | Hence there are <math>Ai + 1</math> choices for each exponent of Pi in the number d => there are <math>(A1 + 1)(A2 + 1)..(Ac + 1)</math> such d | ||
| + | |||
| + | => <math>d(n) = (A1 + 1)(A2+1)..(Ac+1)</math> where Ai are exponents of the prime numbers in the prime factorisation of n. | ||
| + | |||
| + | => <math>d(n^2)/d(n) = {(2A1 + 1)(2A2 + 1)..(2Ac + 1)}/{A1+1)..(Ac+1)} | ||
| + | |||
| + | So we want to find all integers k that can be 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. | ||
| + | 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. | ||
| + | |||
| + | P(k): It's possible to represent k as the product of fractions </math>(2n+1)/(n+1)<math> | ||
| + | Base case: k = 1: (2(0) + 1) / (0 + 1) | ||
| + | Now assume that for </math>k\geq 3<math> it's possible for all odds < k. | ||
| + | |||
| + | Since k is odd, </math>k+1 = 2^z * y$ where y is odd and y < k | ||
Revision as of 01:27, 2 April 2022
Problem
For any positive integer n, let d(n) denote the number of positive divisors
of n (including 1 and n itself). Determine all positive integers k such that
for some n.
Solution
First we must determine general values for d(n):
Let 
, if d is an arbitrary divisor of n then d must have the same prime factors of n, each with an exponent 
being: 
.
Hence there are 
choices for each exponent of Pi in the number d => there are 
such d
=> 
where Ai are exponents of the prime numbers in the prime factorisation of n.
=> $d(n^2)/d(n) = {(2A1 + 1)(2A2 + 1)..(2Ac + 1)}/{A1+1)..(Ac+1)}
So we want to find all integers k that can be represented by the product of fractions of the form$ (Error compiling LaTeX. Unknown error_msg)(2n+1)/(n+1)$Obviously k 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.
P(k): It's possible to represent k as the product of fractions$ (Error compiling LaTeX. Unknown error_msg)(2n+1)/(n+1)
k\geq 3$it's possible for all odds < k.
Since k is odd,$ (Error compiling LaTeX. Unknown error_msg)k+1 = 2^z * y$ where y is odd and y < k
