IMO ShortList 2002, number theory problem 2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#1 h Sep 28, 2004, 1:05 PM • 12 Y

Y by Davi-8191, dangerousliri, mathematicsy, leozitz, Adventure10, megarnie, TFIRSTMGMEDALIST, son7, ImSh95, Mango247, Captainscrubz, ItsBesi

Let $n\geq2$ be a positive integer, with divisors $1=d_1<d_2<\,\ldots<d_k=n$ . Prove that $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ is always less than $n^2$ , and determine when it is a divisor of $n^2$ .

Attachments:

This post has been edited 3 times. Last edited by orl, Sep 27, 2005, 5:00 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

orl

3647 posts

orl

#2 h Sep 28, 2004, 1:05 PM • 5 Y

Y by Adventure10, son7, ImSh95, Mango247, Math_.only.

Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pavel25

122 posts

pavel25

#3 h Nov 3, 2005, 2:55 PM • 6 Y

Y by Adventure10, son7, ImSh95, Mango247, DroneChaudhary, math_gold_medalist28

$d_k = {n\over d_1}$
$d_{k-1} = {n\over d_2}$
$d_1 = {n\over d_k}$
So we can write it like this:
$d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ = ${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k}$
The Maximum that can be is:
${{n^2}\over 1*2}+{{n^2}\over 2*3}+\,\ldots\,+{{n^2}\over (n-1)n}$
We can see that the sum starting with the form:
${m\over {m+1}}{n^2}$
We check what happens if we add the next term:
${m\over {m+1}}{n^2} + {1\over {(m+1)(m+2)}}{n^2} = {{(m+1)^2}\over {(m+1)(m+2)}}{n^2} = {{m+1}\over {m+2}}{n^2}$
From here is easy to define that $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ = ${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k}<{n^2}$

$d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ = ${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k}$ is a divisor of ${n^2}$ when $n$ is a prime number:

$d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ = ${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k} = n$

if $n$ isn't a prime we have at least 3 divisors of $n$
We proved that $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ = ${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k}<{n^2}$

So if it's a divisor of ${n^2}$ the maximum that can be: ${{n^2}\over d_2}$

$d_1 = 1$

$d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ = ${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k} = {{n^2}\over d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k} > {{n^2}\over d_2}$
We see from here that $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ is a divisor of ${n^2}$ only if $n$ is a prime!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

abdurashidjon

119 posts

abdurashidjon

#4 h Jun 10, 2006, 3:39 PM • 4 Y

Y by Adventure10, son7, ImSh95, DroneChaudhary

pavel25 wrote:

$d_k = {n\over d_1}$
$d_{k-1} = {n\over d_2}$
$d_1 = {n\over d_k}$
So we can write it like this:
$d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ = ${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k}$
The Maximum that can be is:
${{n^2}\over 1*2}+{{n^2}\over 2*3}+\,\ldots\,+{{n^2}\over (n-1)n}$
We can see that the sum starting with the form:
${m\over {m+1}}{n^2}$
We check what happens if we add the next term:
${m\over {m+1}}{n^2} + {1\over {(m+1)(m+2)}}{n^2} = {{(m+1)^2}\over {(m+1)(m+2)}}{n^2} = {{m+1}\over {m+2}}{n^2}$
From here is easy to define that $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ = ${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k}<{n^2}$

$d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ = ${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k}$ is a divisor of ${n^2}$ when $n$ is a prime number:

$d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ = ${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k} = n$

if $n$ isn't a prime we have at least 3 divisors of $n$
We proved that $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ = ${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k}<{n^2}$

So if it's a divisor of ${n^2}$ the maximum that can be: ${{n^2}\over d_2}$

$d_1 = 1$

$d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ = ${{n^2}\over d_1d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k} = {{n^2}\over d_2}+{{n^2}\over d_2d_3}+\,\ldots\,+{{n^2}\over d_{k-1}d_k} > {{n^2}\over d_2}$
We see from here that $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ is a divisor of ${n^2}$ only if $n$ is a prime!

I have asked this question as another link sorry for the same question <http://www.mathlinks.ro/Forum/viewtopic.php?p=531646#531646>

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Davron

484 posts

Davron

#5 h Jun 11, 2006, 2:08 PM • 4 Y

Y by Adventure10, son7, ImSh95, Mango247

see i was right about the imo 2002

davron

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

me@home

2349 posts

me@home

#6 h Apr 22, 2009, 5:48 AM • 3 Y

Y by son7, ImSh95, Adventure10

Sorry to revive

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JuanOrtiz

366 posts

JuanOrtiz

#7 h May 26, 2014, 2:30 AM • 6 Y

Y by son7, ImSh95, Chokechoke, Adventure10, Mango247, DroneChaudhary

Notice that because of the famous Cauchy Inequality applied to $d_1,...,d_{k-1}$ and $d_2,...,d_k$ we will have

$d_1d_2+...+d_{k-1}d_k \le \left( d_1^2+...+d_{k-1}^2 \right)^2 \left( d_2^2+...+d_k^2 \right)^2$ .

Let $X=d_1^2+...+d_k^2$ , we will have that

$d_1d_2+...+d_{k-1}d_k \le \left( X-n^2 \right)^2 \left( X-1 \right)^2$

So, in order to finish the first part it is enough to prove

$X^2-(n^2+1)X+(n^2-n^4) < 0$

which simplifies, by the general equation, to proving that

$X < \displaystyle\frac{n^2+1+\sqrt{5n^4-4n^2+1}}{2}$

Since $\sqrt{5n^4-4n^2+1} > (2n^2-1)$ , it is enough to prove that

$X \le \displaystyle\frac{3n^2}{2}$

Let $n=p_1^{e_1}...p_m^{e_m}$ , we will have

$X=\prod_{i=1}^m (1+p_i^2+...+p_i^{2e_i})$

and so it will be enough to prove that, for each $i \le m$ , if $p=p_i$ and $e=e_i$ ,

$3p^{2e}/2 \ge 1+p^2+...+p^{2e}$

This is equivalent to

$p^{2e}/2 \ge 1+p^2+...+p^{2e-2} = \displaystyle\frac{p^{2e}-1}{p^2-1}$

Notice that $p^2-1 \ge 4-1 = 3$ and so the above is true.

So we are done with the first part.

Now for the second part, assume that $X=d_1d_2+...+d_{k-1}d_k | n^2$ . If $n$ is not prime then $k >2$ and so $X > d_kd_{k-1}=n^2/p$ , where $p$ is the smallest prime divisor of $n$ (which exists because $n>1$ ). And so if $X | n^2$ then there exists a $q$ such that $qX=n^2$ . Notice that $X < n^2$ by the first part and so $q > 1$ . Since $q | n$ , then $q \ge p$ and we get $pX \le n^2$ which is false because $X > n^2/p$ .

So $n$ must be prime, and it is easy to see $X=1*n|n^2$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

godfjock

194 posts

godfjock

#8 h Apr 9, 2016, 11:52 PM • 3 Y

Y by ImSh95, Adventure10, Mango247

Part a: Notice that $d_i d_j = n$ if and only if $i+j = k+1$
So we have that $d_1d_2 +d_2d_3+...+d_{k-1}d_k < n^2 \iff$
$d_{k-1}d_k (d_1d_2+...+d_{k-1}d_k) < n^2 (d_{k-1}d_k)$
Wich is equal to
$n^2 + d_{k-1}d_k(d_2d_3+...+d_{k-1}d_k) < RHS$
Multiplying by the other terms we have that
$n^2(d_1d_2)(...)(d_{k-2}d_{k-1}) + n^2 (d_2d_3+...+d_{k-1}d_k) < n^2 (d_1d_2)(...)(d_{k-1}d_k)$
Wich is equal to
$n^2(( \frac {(k-1) n^2} {d_{k-1}d_k})+(d_2d_3+...+d_{k-1}d_k)) < n^2 ((k-1) n^2))$
we have that clearly $d_id_{i+1}<n^2$ for every i
So we just have to show that
$\frac {(k-1) n^2} {d_{k-1}d_k} \le n^2 \iff$
$(k-1) \le d_{k-1}d_k$
We know that $1< d(n) < n$ so clearly this inequality holds
( $k-1<k=d(n)<n\le d_{k-1}n$ )

For part b: we have that the greatest divisor of $n^2$ is $\frac {n^2} {d_2} = d_{k-1} d_k$
And by part a we know that $n^2 > LHS \ge d_{k-1} d_k$ and equality holds only when n is a prime so thats the only posible case

This post has been edited 8 times. Last edited by godfjock, Apr 18, 2016, 1:59 PM
Reason: Latex

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

solver6

259 posts

solver6

#9 h Oct 27, 2016, 6:34 PM • 3 Y

Y by ImSh95, Adventure10, ehuseyinyigit

Solution :

Note that $\frac{d_1d_2 + d_2d_3 +\ldots + d_{k-1}d_k}{n^2} = \frac{1}{d_1d_2} + \frac{1}{d_2d_3} +\ldots + \frac{1}{d_{k-1}d_k}$ . And use that $\frac{1}{d_1d_2} + \frac{1}{d_2d_3} +\ldots + \frac{1}{d_{k-1}d_k}$ $\leq$

$\frac{1}{1*2} + \frac{1}{2*3} + \frac{1}{3*4}+\ldots + \frac{1}{(k-1)k}$ $\leq$

$(1-\frac{1}{2}) + (\frac{1}{2} - \frac{1}{3}) + (\frac{1}{3} - \frac{1}{4}) +\ldots + (\frac{1}{k-1} - \frac{1}{k}) = 1 - \frac{1}{k} < 1$ . So $\frac{d_1d_2 + d_2d_3 +\ldots + d_{k-1}d_k}{n^2}< 1$ . $\Box$

This post has been edited 4 times. Last edited by solver6, Oct 27, 2016, 6:37 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ferid.---.

1008 posts

Ferid.---.

#10 h Jul 20, 2017, 10:12 PM • 2 Y

Y by ImSh95, Adventure10

My solution:
We must to prove that
$S=d_1d_2+...+d_{k-1}d_k=\frac{n^2}{d_1d_2}+...+\frac{n^2}{d_{k-1}d_k}<n^2.$
We know
$n^2(\frac{1}{d_1d_2}+...\frac{1}{d_{k-1}d_k})\le n^2(\frac{1}{1\cdot 2}+...+\frac{1}{(k-1)\cdot k})=n^2(1-\frac{1}{k})<n^2.$
For part $b,$ we know $S\mid n^2,$ and $n=d_1d_k,n=d_2d_{k-1}\to n^2=d_2d_{k-1}d_k.$
Also we know $1<\frac{n^2}{S}\le \frac{n^2}{d_{k-1}d_k}=d_2.$
Equality: $S=d_{k-1}d_k\to k=2\to n=d_1\cdot d_2=d_2$ where $d_2$ is prime.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pad

1671 posts

pad

#11 h Apr 5, 2019, 6:00 AM • 6 Y

Y by ImSh95, PEKKA, Adventure10, Mango247, Mango247, Mango247

(a) Clearly, $d_id_{k+1-i}=n$ , so
$d_id_{i+1} = \frac{n^2}{d_{k+1-i}d_{k-i}} = \frac{n^2}{d_{k+1-i}-d_{k-i}}\left(\frac{1}{d_{k-i}} - \frac{1}{d_{k+1-i}}\right) \le n^2\left(\frac{1}{d_{k-i}} - \frac{1}{d_{k+1-i}}\right),$ since $d_{k+1-i} - d_{k-i}\ge 1$ . Summing, we get
$\sum_{i=1}^n d_id_{i+1} \le n^2 \sum_{i=1}^n \frac{1}{d_{k-i}} - \frac{1}{d_{k+1-i}} = n^2\left(\frac{1}{d_1}-\frac{1}{d_k}\right)=n^2(1-1/n) < n^2.$ (b) Let $S=d_1d_2+\cdots+d_{k-1}d_k$ . First consider the case where $n$ is composite. We know $d_2$ is the smallest prime divisor of $n$ . Let $d_2=p$ . Since $d_{k-1}d_k=\tfrac{n}{p}\cdot n = \tfrac{n^2}{p}$ , so $S>n^2/p$ . But $p$ is also the smallest prime divisor of $n^2$ , so $n^2/p$ is the largest proper divisor of $n^2$ . Therefore, $S=n^2$ , which is impossible, since it is at most $n^2(1-1/n)$ . Hence, no composite $n$ works. Now consider the case where $n$ is prime. Then $d_1=1,d_2=n$ , so $S=d_1d_2=n$ , which divides $n^2$ . Therefore, $S\mid n^2$ if and only if $n$ is prime.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6877 posts

v_Enhance

#12 h Apr 8, 2019, 12:14 PM • 21 Y

Y by nguyenhaan2209, Vaijan_Mama, Wizard0001, A-Thought-Of-God, Haaaa, v4913, Tafi_ak, megarnie, guptaamitu1, TFIRSTMGMEDALIST, ImSh95, IMUKAT, Derpy_Creeper, TheMathCruncher_007, DanielALM, surpidism., Adventure10, Mango247, Ritwin, DroneChaudhary, Math_.only.

We always have $\begin{align*} d_k d_{k-1} + d_{k-1} d_{k-2} + \dots + d_2 d_1 &< n \cdot \frac n2 + \frac n2 \cdot \frac n3 + \dots \\ &= \left( \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \dots \right) n^2 = n^2. \end{align*}$ This proves the first part.

For the second, we claim that this only happens when $n$ is prime (in which case we get $d_1 d_2 = n$ ). Now assume $n$ is not prime (meaning $k \ge 2$ ) and let $p$ be the smallest prime dividing $n$ . Then $d_k d_{k-1} + d_{k-1} d_{k-2} + \dots + d_2 d_1 > d_k d_{k-1} = \frac{n^2}{p}$ exceeds the largest proper divisor of $n^2$ , but is less than $n^2$ , so does not divide $n^2$ .

This post has been edited 1 time. Last edited by v_Enhance, Apr 8, 2019, 12:14 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

anantmudgal09

1980 posts

anantmudgal09

#13 h May 19, 2019, 6:38 PM • 6 Y

Y by ELMOliveslong, amar_04, A-Thought-Of-God, ImSh95, Adventure10, ProMaskedVictor

orl wrote:

Let $n\geq2$ be a positive integer, with divisors $1=d_1<d_2<\,\ldots<d_k=n$ . Prove that $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ is always less than $n^2$ , and determine when it is a divisor of $n^2$ .

Notice that $\begin{align*} \sum^{k-1}_{i=1} d_id_{i+1} &=n^2 \cdot \left( \sum^{k-1}_{i=1} \frac{1}{d_id_{i+1}}\right) \\ & \le n^2 \cdot \left( \sum^{k-1}_{i=1} \frac{(d_{i+1}-d_i)}{d_id_{i+1}} \right) \\ &= n^2 \cdot \left(\sum^{k-1}_{i=1} \left(\frac{1}{d_i}-\frac{1}{d_{i+1}} \right) \right) \\ &= n^2 \cdot \left(1-\frac{1}{n}\right) <n^2, \end{align*}$ so the first assertion is true. Observe that $d_{k-1}=\frac{n}{p}$ where $p$ is the smallest prime factor of $n$ ; so if $k>2$ then $1<\frac{n^2}{\sum^{k-1}_{i=1} d_id_{i+1}}<\frac{n^2}{d_{k-1}d_k}=p,$ contradicting that this quotient is a divisor of $n^2$ . So, $k=2$ and $n=p$ . For all prime numbers $n$ , the assertion holds; hence these are the only solutions.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yayups

1614 posts

yayups

#14 h Aug 9, 2019, 7:21 PM • 3 Y

Y by ImSh95, neel2003, Adventure10

Note that
$S:=d_1d_2+\cdots+d_{k-1}d_k=n^2\left(\frac{1}{d_1d_2}+\cdots+\frac{1}{d_{k-1}d_k}\right)\le n^2\left(\left(\frac{1}{d_1}-\frac{1}{d_2}\right)+\cdots+\left(\frac{1}{d_{k-1}}-\frac{1}{d_k}\right)\right),$ so
$S\le n^2(1-1/n)=n^2-n<n^2,$ as desired.

Now suppose that $S\mid n^2$ . Any divisor of $n^2$ can be written as a product of two divisors of $n$ , so suppose $S=d_ad_b$ where $b>a$ . We'll show that this isn't possible for size reasons. To do so, we have the following ``smoothing'' lemma.

Lemma: If $0<x\le z\le y$ , then $xy<xz+zy$ .

Proof: Over the interval $[x,y]$ , the extrema of the linear function $z(x+y)$ will be at the edges, so
$x^2+xy\le xz+zy\le y^2+xy,$ so certainly $xy<xz+zy$ . $\blacksquare$

Suppose for now that $b-a\le 2$ Using the lemma, we see that
$d_ad_b<d_ad_{a+1}+d_{a+1}d_{a+2}+\cdots+d_{b-1}d_b,$ so $d_ad_b<S$ . If $b-a=1$ , then the only way $S=d_ad_{a+1}$ is if $n$ has only two factors, so $n$ is prime. Primes clearly work as $S=1\cdot p\mid p^2$ . Thus, the answer is $\boxed{n\text{ is prime}}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ubermensch

820 posts

ubermensch

#15 h Sep 9, 2019, 1:34 PM • 3 Y

Y by ImSh95, Adventure10, Mango247

Cute problem

Notice that $d_k \leq \frac n1, d_{k-1} \leq \frac{n}2, d_{k-2} \leq \frac{n}3,$ and so on.
Thus the sum $X = d_kd_{k-1}+d_{k-1}d_{k-2}+...+d_2d_1 \leq \frac{n^2}{1 \cdot 2} + \frac{n^2}{2 \cdot 3} +...+ \text{(k-1 terms)} < n^2(\frac 1{1 \cdot 2} +\frac 1{2 \cdot 3}+... \text{(infinite sum)})=n^2( \frac 11 -\frac 12 + \frac 12 - \frac 13 +\frac 13 -... )=n^2$ .
$=>$ $a$ part over.
After a little playing around, or even otherwise, we see that the only $n$ that'll work should be prime $n$ - once we realise this, it basically becomes a one-liner: consider $n$ non-prime with smallest divisor $p$ . Notice that the largest divisor of $n^2<n^2$ must be $\frac{n^2}p$ , and as our sum $X<n^2$ but $d_k d_{k-1} = \frac{n^2}p =>$ if there are more than $2$ factors, $X> \frac{n^2}p$ can't divide $n^2$ . Verifying, we see that each $n$ prime indeed works, hence the only $n$ that work are primes.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

gladIasked

648 posts

gladIasked

#47 h Dec 27, 2023, 1:54 AM

Y by

Note that $d_k\le \frac n1$ , $d_{k-1} \le \frac n2$ , $d_{k-2} \le \frac n3$ , $\ldots$ , $d_2 \le \frac{n}{k-1}$ , $d_1\le \frac{n}{k}$ . In general, $d_i\le \frac{n}{k-i+1}$ . Thus, we have the inequality $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k\le n^2\sum^{k-1}_{i=1}\frac 1{i(i+1)}.$ The summation telescopes into $1-\frac 1k$ , so we have $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k\le n^2\left(1-\frac 1k\right)<n^2$ , as desired.

Now, I claim that $d_1d_2+d_2d_3+\,\ldots\,+d_{k-1}d_k$ divides $n$ only if $n$ is prime. Suppose the smallest divisor of $n$ other than $1$ is $p$ . Obviously, $p$ is prime. Note also that $p$ is the smallest divisor of $n^2$ other than $1$ . Then, we have that $d_2 = p$ and $d_{k-1} = \frac np$ . We then have that our sum is equal to $p+\frac{n^2}{p} + d_2d_3+d_3d_4\ldots + d_{k-2}d_{k-1}>\frac{n^2}{p}$ $\implies \frac{n^2}{p+n^2+d_2d_3+d_3d_4+\ldots + d_{k-2}d_{k-1}}<p.$ However, if $p+\frac{n^2}{p} + d_2d_3 + d_3d_4+\ldots + d_{k-2}d_{k-1}\mid n^2$ , then the LHS of the inequality is an integer, contradicting the minimality of $p$ . Thus, the sum cannot divide $n^2$ if $n$ is composite, as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

R4H33M

4 posts

R4H33M

#48 h Jan 16, 2024, 5:24 PM

Y by

Note that $d_id_{k-i+1} = n$ for all $1 \leq i \leq k$ .
Then, $D = d_1d_2 + d_2d_3 + \cdots \ d_{k-1}d_k$ has
$D = n^2 (\frac{1}{d_{1}d_{2}} + \frac{1}{d_{2}d_{3}} + \cdots + \frac{1}{d_{k-1}d_{k}})$ Since $1 = d_1 < d_2 < \cdots < d_k$ , we have $i < d_i$ for all $1 \leq i \leq k$ .
This gives:
$\frac{1}{d_{1}d_{2}} + \frac{1}{d_{2}d_{3}} + \cdots + \frac{1}{d_{k-1}d_{k}} \leq \sum_{i = 1}^{k-1}\frac{1}{(i)(i+1)} = \sum_{i = 1}^{k-1}\frac{1}{i} - \frac{1}{i+1}$ By telescoping, the above sum is equal to $1 - \frac{1}{k} < 1$ , so $D < n^2 \cdot 1 = n^2$ .

Claim: $D \mid n^2$ if and only if $n$ is prime.
It is easy to check that when $n$ is prime, $D = 1 \cdot n = n$ , and trivially $n = D \mid n^2$ .
Otherwise, assume $n$ is not prime and proceed by contradiction. If $D \mid n^2$ , then $Dp = n^2$ for some positive integer $p$ . By the above, $p$ cannot be one, so it has to be $\geq$ the smallest non-one divisor of $n^2$ . This is the smallest prime in the prime factorization of $n^2$ , which is also the smallest prime in the prime factorization of $n$ , and therefore $p \geq d_2$ .

This means that $d_2d_{k-1}d_k = n^2 \leq Dp$ . Equality is only when $d_{k-1}d_k$ is the only term in $D$ , i.e. $k = 2$ , implying that $n$ is prime, which is a contradiction. Otherwise $n^2 < Dp$ , contradicting $Dp \mid n^2$ .

This post has been edited 2 times. Last edited by R4H33M, Jan 16, 2024, 5:27 PM
Reason: correction

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AlanLG

241 posts

AlanLG

#49 h Jan 24, 2024, 4:36 PM

Y by

By considering the divisors in the form $\frac{n}{d}$ we get it suffices to prove
$\frac{1}{d_1d_2}+\frac{1}{d_2d_3}+\cdots +\frac{1}{d_{k-1}d_k}\leq 1$ Now note that
$\frac{1}{d_1d_2}+\cdots +\frac{1}{d_{k-1}d_k}\leq\frac{d_2-d_1}{d_1d_2}+\cdots \frac{d_k-d_{k-1}}{d_{k-1}d_k}=\frac{1}{d_1}-\frac{1}{d_2}+\cdots +\frac{1}{d_{k-1}}-\frac{1}{d_k}=1-\frac{1}{n}<1$ For the other part, note that
$n^2>d_1d_2+\cdots d_{k-1}d_{k}\geq d_{k-1}d_{k}=\frac{n}{d_2}\cdot n=\frac{n^2}{d_2}$ But $n^2$ and $\frac{n^2}{d_2}$ are the bigger and the second bigger divisors of $n^2$ , and the equality is satisfied only when $n$ is prime

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sagnik123Biswas

420 posts

Sagnik123Biswas

#50 h Mar 15, 2024, 4:29 PM

Y by

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

blueberryfaygo_55

340 posts

blueberryfaygo_55

#51 h May 1, 2024, 10:40 PM • 1 Y

Y by megarnie

Solved with megarnie.

We can rewrite the given sum as follows:
$\begin{align*} d_1d_2 + d_2d_3 + \cdots + d_{k-1}d_k &= \dfrac{n}{d_k}\cdot \dfrac{n}{d_{k-1}} + \dfrac{n}{d_{k-1}} \cdot \dfrac{n}{d_{k-2}} + \cdots + \dfrac{n}{d_2} \cdot \dfrac{n}{d_1} \\ &= \dfrac{n^2}{d_kd_{k-1}} + \dfrac{n^2}{d_{k-1}d_{k-2}} + \cdots + \dfrac{n^2}{d_2d_1} \\ &= n^2 \left(\dfrac{1}{d_kd_{k-1}} + \dfrac{1}{d_{k-1}d_{k-2}} + \cdots + \dfrac{1}{d_2d_1} \right) \end{align*}$ Thus, we just need to show that $\dfrac{1}{d_kd_{k-1}} + \dfrac{1}{d_{k-1}d_{k-2}} + \cdots + \dfrac{1}{d_2d_1} < 1$ Indeed, we know that $d_2 \geq 2$ , $d_3 \geq 3$ , $\cdots$ , so it follows that
$\begin{align*} \dfrac{1}{d_kd_{k-1}} + \dfrac{1}{d_{k-1}d_{k-2}} + \cdots + \dfrac{1}{d_2d_1} &\leq \dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \cdots + \dfrac{1}{n(n-1)} \\ &= \dfrac{1}{1} - \dfrac 12 + \dfrac 12 - \dfrac 13 + \cdots - \dfrac{1}{n-1} + \dfrac{1}{n-1} - \dfrac 1n \\ &= 1 - \dfrac 1n \\ &< 1 \end{align*}$ and the desired inequality follows.

Now, we claim that $d_1d_2 + d_2d_3 + \cdots + d_{k-1}d_k$ divides $n^2$ if and only if $n$ is a prime.

We first show that all primes work. Indeed, the only divisors of $n$ are $1,n$ , so the given sum is equal to $1 \cdot n = n \mid n^2$ .

To see that all composite $n$ do not work, let $p$ be the smallest prime that divides $n$ . Then, $d_2 = p$ , and $d_{k-1}d_k = \dfrac{n}{d_2} \cdot n = \dfrac{n^2}{p}$ . For $d_1d_2 + d_2d_3 + \cdots + d_{k-1}d_k$ to divide $n$ , we must have $d_1d_2 + d_2d_3 + \cdots + d_{k-1}d_k = d_1d_2 + d_2d_3 + \cdots + \dfrac{n^2}{p} = \dfrac{n^2}{a}$ for some positive integer $a$ . Since $n$ is composite and has at least $3$ positive divisors, we must have $\dfrac{n^2}{p} < \dfrac{n^2}{a}$ which is equivalent to $p > a$ . However, since $p$ is the smallest prime that divides $n$ , $p$ is also the smallest prime that divides $n^2$ , so such $a$ cannot exist, and we reach a contradiction if $n$ is composite. If $n$ is prime, then we could have $p=a$ as then we only have $2$ divisors, and the condition is satisfied as shown above. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lnzhonglp

120 posts

lnzhonglp

#52 h Jun 23, 2024, 6:02 AM

Y by

We have $d_{k-1} \leq \frac{n}{2}$ , $d_{k-2} \leq \frac{n}{3}$ , $\dots$ so $d_{1}d_{2} + d_{2}d_{3} + \dots + d_{k-1}d_{k} < n^2\left(1 \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{3} + \dots\right) = n^2.$ For the second part, we claim the answer is when $n$ is prime. Let $p$ be the smallest prime factor of $n$ . If $n = p$ , then $d_1d_2 = n \mid n^2$ , so prime $n$ work. If $n$ is not prime, and suppose $d_1d_2 + \dots d_{k-1}d_k = n^2/a$ . Since $p$ is the smallest prime dividing $n$ , we have $a \geq p$ . But $d_1d_2 + d_2d_3 + \dots + d_{k-1}d_k > n^2\left(1\cdot \frac{1}{p}\right),$ so $a < p$ , contradiction. Therefore, only prime $n$ work.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ywgh1

139 posts

Ywgh1

#53 h Aug 20, 2024, 8:12 PM

Y by

IMO 2002 p4

We first show that.
$d_{1}d_{2} + d_{2}d_{3} + \dots + d_{k-1}d_{k} < n^2.$
So since we have that $d_i=\frac{n}{d_k-i}$ , hence we have that.

$\begin{align*} d_1d_2 + d_2d_3 + \cdots + d_{k-1}d_k &= \dfrac{n}{d_k}\cdot \dfrac{n}{d_{k-1}} + \dfrac{n}{d_{k-1}} \cdot \dfrac{n}{d_{k-2}} + \cdots + \dfrac{n}{d_2} \cdot \dfrac{n}{d_1} \\ &= n^2 \left(\dfrac{1}{d_kd_{k-1}} + \dfrac{1}{d_{k-1}d_{k-2}} + \cdots + \dfrac{1}{d_2d_1} \right) \end{align*}$
So we need to show that.
$\dfrac{1}{d_kd_{k-1}} + \dfrac{1}{d_{k-1}d_{k-2}} + \cdots + \dfrac{1}{d_2d_1}<1$ .
Which is easy.

Now for the second part, we claim that it hold if and only if $n$ is a prime.
Assume that $n$ is a prime, this case is trivial.
Now assuming that $n$ is composite, then we have that.
$d_kd_{k-1}=\frac{n^2}{p}$ Where $p$ is the smallest prime of $n$ .
We want to show that $d_1d_2 + d_2d_3 + \dots + d_{k-1}d_k= \frac{n^2}{q}$ where $q$ is a divisor of $n$ .
But we have that $p<q$ , hence only prime $n$ works.

This post has been edited 1 time. Last edited by Ywgh1, Aug 20, 2024, 8:12 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alexanderhamilton124

389 posts

alexanderhamilton124

#54 h Aug 30, 2024, 5:08 PM

Y by

Note that $d_k \leq n$ , $d_{k - 1} \leq \frac{n}{2}$ , $d_{k - 2} \leq \frac{n}{3}$ , $\dots$ , $d_{1} \leq \frac{n}{n}$ . Observe that:
$d_1d_2 + d_2d_3 + ... + d_{k - 1}d_{k} \leq n^2(1 - \frac{1}{n})$ Now, since $1 - \frac{1}{n} < 1$ , we are done.

For the second part, note that if $n$ is composite, we have $d_{k - 1} = \frac{n}{p}$ , where $p$ is the smallest prime divisor of $n$ . Observe that $d_1d_2 + d_2d_3 + ... + d_{k - 1}d_{k} > \frac{n^2}{p}$ , however this is the largest divisor of $n^2$ , so we have a contradiction. If $n$ is prime, it works.

This post has been edited 1 time. Last edited by alexanderhamilton124, Aug 30, 2024, 5:10 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1262 posts

ezpotd

#55 h Oct 16, 2024, 4:32 AM

Y by

This expression is bounded by $n^2 (\frac 11 \frac 12 + \frac 12 \frac 13 + \cdots + \frac{1}{n - 1} \frac 1n) = n^2 - n$ , as desired. We claim it is a divisor of $n^2$ only when $n$ is prime. It is easy to see all prime numbers work. To see that nothing else works, take the smallest prime divisor of $n^2$ as $p$ , clearly the second largest divisor of $n^2$ is $\frac{n^2}{p}$ , but $d_{k -1}d_k = \frac 1p n^2$ , so we must have this being the only term in the summation, so $k = 2$ forces $n$ prime.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Saucepan_man02

1331 posts

Saucepan_man02

#56 h Oct 22, 2024, 11:42 AM

Y by

a) Notice that: $d_1 d_2 + d_2 d_3 + \cdots + d_{k-1} d_{k} = n^2 \cdot \left( \frac{1}{d_1 d_2} + \frac{1}{d_2 d_3} + \cdots + \frac{1}{d_{k-1} d_{k}}\right).$ Notice that: $\frac{1}{d_1 d_2} + \frac{1}{d_2 d_3} + \cdots + \frac{1}{d_{k-1} d_{k}} < \sum_{i=1}^{\infty} \frac{1}{i(i+1)} = 1$
Thus, we have: $d_1 d_2 + d_2 d_3 + \cdots + d_{k-1} d_{k} = n^2 \cdot \left( \frac{1}{d_1 d_2} + \frac{1}{d_2 d_3} + \cdots + \frac{1}{d_{k-1} d_{k}}\right) < n^2.$
b) Note that: $d_1=1, d_2=p$ where $p$ is a the smallest prime factor of $n$ . Then, notice that: $d_{k-1} d_k = \frac{n^2}{p}$ is the largest divisor of $n^2$ . Thus, it should be the only term in the summation: $S = d_1 d_2 + d_2 d_3 + \cdots + d_{k-1} d_{k}$ inorder to have $S|n^2$ . Therefore, $k=2$ which implies $n$ is a prime and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eg4334

637 posts

eg4334

#57 h Dec 27, 2024, 8:02 PM

Y by

The first part follows from the very loose bound:
$\begin{align*} d_1 d_2 + d_2 d_3 + \dots + d_{k-1} d_k = n^2 \left( \frac{1}{d_1} \frac{1}{d_2} + \dots + \frac{1}{d_{k-1}} \frac{1}{d_k} \right) \\ < n^2 \left( \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \dots + \frac{1}{(k-1) \cdot k} \right) \\ < n^2 \left( 1 - \frac{1}{k} \right) \\ < n^2 \\ \end{align*}$ The second part is only true when $n=\boxed{p}$ for some prime $p$ . This works because $p | p^2$ . If $n$ was compoite, then consider the smallest prime $q$ dividing it. The desired sum is then strictly greater than $n \cdot \frac{n}{q}$ , implying the desired contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Eka01

204 posts

Eka01

#58 h Jan 3, 2025, 5:52 PM

Y by

It amounts to proving $\sum \frac{1}{d_i.d_{i+1}}$ is less than $1$ where $i$ varies from $1$ to $k-1$ . Note that $\frac{1}{d_id_{i+1}}$ is less than or equal to $\frac{1}{d_i} - \frac{1}{d_{i+1}}$ with equality holding iff $d_{i+1}-d_i=1$ . Now obviously, for each $n$ there must be atleast one pair of consecutive divisors with a difference greater than $1$ so the above sum is less than $1- \frac{1}{n}$ which is less than $1$ .

Now notice that second largest divisor of $n^2$ is $\frac{n^2}{d_2}$ but this is $d_{k-1}d_k$ so the given sum is greater than this unless there is only one term in the sequence, that is, $k=2$ . This implies $n$ must be a prime and all primes can easily be verified to work. So the answer to the second part is $n$ must be a prime.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

614 posts

cursed_tangent1434

#59 h Jan 25, 2025, 1:37 AM

Y by

We split the argument into two cases.

Case 1 : If $n \ge 2$ is a prime, $d_1=1$ and $d_2=n$ are all the divisors of $n$ . Then,
$d_1d_2=n \nmid n^2$ so the inequality holds with $n$ a divisor of $n^2$ .

Case 2 : $n$ is composite. Then, $k >2$ . Now note,
$d_1d_2+d_2d_3 + \dots + d_{k-1}d_k = \frac{n^2}{d_kd_{k-1}}+\frac{n^2}{d_{k-1}d_{k-2}}+\dots + \frac{n^2}{d_2d_1}$ First note,
$\frac{n^2}{d_kd_{k-1}}+\frac{n^2}{d_{k-1}d_{k-2}}+\dots + \frac{n^2}{d_2d_1} > \frac{n^2}{d_2d_1} = \frac{n^2}{d_2}$ Further, since clearly $d_i \ge i$ for all $1\le i \le k$ ,
$\frac{n^2}{d_kd_{k-1}}+\frac{n^2}{d_{k-1}d_{k-2}}+\dots + \frac{n^2}{d_2d_1} \le \frac{n^2}{k(k-1)}+\frac{n^2}{(k-1)(k-2)}+\dots + \frac{n^2}{2 \cdot 1} = n^2 \left(1- \frac{1}{k}\right) < n^2$ Since $d_2$ is the smallest divisor of $n$ , it must be prime and thus, it is also the smallest divisor of $n^2$ (every prime divisor of $n^2$ is a prime divisor of $n$ ). Thus, $\frac{n^2}{d_2}$ is the largest divisor of $n^2$ less than $n^2$ . But since,
$\frac{n^2}{d_2}<\frac{n^2}{d_kd_{k-1}}+\frac{n^2}{d_{k-1}d_{k-2}}+\dots + \frac{n^2}{d_2d_1} < n^2$ it cannot be a divisor of $n^2$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

575 posts

Maximilian113

#61 h Apr 24, 2025, 9:08 PM

Y by

Note that $d_1d_2+d_2d_3+\cdots+d_{k-1}d_k = n^2 \left( \frac{1}{d_1d_2} + \frac{1}{d_2d_3}+\cdots+ \frac{1}{d_{k-1}d_k}\right) \leq n^2\left( \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{(n-1) \cdot n} \right) = n^2 \left(1 - \frac{1}{n} \right) < n^2.$ Now if $n$ is composite $k \geq 2$ so $d_1d_2+d_2d_3+\cdots+d_{k-1}d_k > n^2/d_2,$ so this cannot possibly divide $n^2.$ But if $n$ is prime it clearly works. Hence that is the answer.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ilikeminecraft

614 posts

Ilikeminecraft

#62 h Apr 26, 2025, 4:05 AM

Y by

Note that $d_m\leq m$ for all $m.$ Hence, $d_1d_2 + d_2d_3 + \cdots + d_{k - 1} d_k \leq n^2 \left(\frac12 + \frac1{2 \cdot 3} + \cdots + \frac1{(k - 1)\cdot k}\right) = n^2(1 - \frac1k) < n^2$ For equality, observe that $d_kd_{k - 1} = \frac{n^2}{d_2}.$ Hence, $S \geq \frac{n^2}{d_2},$ but it also can't be $n^2$ since we proved earlier it is less than $n^2.$ Hence, $n$ has 2 prime factors. This obviously works.

Z K Y