Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1998 IMO Problems/Problem 3"
(→‎Solution)
 
(7 intermediate revisions by 3 users 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===
 +
 
 +
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 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
 +
 
 +
<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 <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.
 +
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>. It is sufficient to show that <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+1}/{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 01:39, 17 September 2024

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 $d(n^2)/d(n) = k$ for some $n$.

Solution

First we must $d$etermine gener$a$l values for $d(n)$: Let $n=p1 ^ a1 * p2 ^ a2 * .. * pc ^ ac$, if $d$ is an ar$b$itr$a$ry divisor of $n$ then $d$ must have the same prime factors of $n$, each with an exponent $b_i$ being: $0\leq b_i\leq a_i$. Hence there are $Ai + 1$ choices for each exponent of Pi in the number d => there are $(a_1 + 1)(a_2 + 1)..(a_c + 1)$ such d

$\implies d(n) = (a_1 + 1)(a_2+1)..(a_c+1)$ where $a_i$ are exponents of the prime numbers in the prime factorisation of $n$.

$\implies d(n^2)/d(n) = {(2a_1 + 1)(2a_2 + 1)..(2a_c + 1)}/{(a_1+1)..(a_c+1)}$

So we want to find all integers $k$ that can $b$e represented by the product of fractions of the form $(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 $(2n+1)/(n+1)$

Base case: $k = 1: (2(0) + 1) / (0 + 1)$ Now assume that for $k\geq 3$ it's possible for all odds < $k$.

Since $k$ is odd, $k+1 = 2^zy$ where $y$ is odd and $y$ < $k$

Let there be a number $x$ s.t $k-y=x\implies k+1 = 2^z(k-x)\implies (2^zx+1)/(2^z-1)=k$

Also consider $k/y$. It is sufficient to show that $k/y$ can be represented by a product of fractions of the form $2n+1/n+1$ in order to show $k$ can be represented by product of fractions $2n+1/n+1$, since $y$ can be represented in such a manner too.

$k/y = k/(k-x) = 1/(1 - x/k)$

Using our definition of $k$ in terms of $x$:

$k/y = 1/({1 - {2^z-x}/{2^zx+1}}) = {2^zx+1}/{x+1}$

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 $k/y$ can be written s.t it's a product of fractions of the form ${2n+1}/{n+1}\implies k$ can be written in such a way too.

Hence we have shown that all odds less than $k$ satisfies $P(n)\implies P(k)$ is true. Since we have shown P(1) is true, it must hence be true for all odd integers.

Therefore, $d(n^2)/d(n) = k\iff k$ is odd, for some n. I.E all odd $k$ 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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1998_IMO_Problems/Problem_3&oldid=227381"