Difference between revisions of "2002 IMO Problems/Problem 4"

Latest revision as of 22:27, 20 August 2025

Problem: Let $n>1$ be an integer and let $1=d_{1}<d_{2}<d_{3} \cdots <d_{r}=n$ be all of its positive divisors in increasing order. Show that $d=d_1d_2+d_2d_3+ \cdots +d_{r-1}d_r <n^2$

Solution 1

We proceed with two parts:

Part 1: Proof of Inequality

We have: \[ \sum_{i=1}^{r-1} d_i d_{i+1} = d_1d_2 + d_2d_3 + \cdots + d_{r-1}d_r \] For each term $ d_i d_{i+1} $, note that $ d_{i+1} \leq \frac{n}{d_i} $ (since divisors come in pairs). Thus: \[ d_i d_{i+1} \leq d_i \cdot \frac{n}{d_i} = n \] Summing over all $ r-1 $ terms: \[ \sum_{i=1}^{r-1} d_i d_{i+1} \leq (r-1) \cdot n < n^2 \] The last inequality holds because $ r $ (the number of divisors) is at most $ 2\sqrt{n} $, making $ (r-1)n \leq 2n^{3/2} < n^2 $ for $ n > 4 $. Smaller cases can be verified directly.

Part 2: Equality Condition

Equality occurs **only** when $ n $ is prime: - For prime $ n $, the divisors are $ 1 $ and $ n $, so:

- For composite $ n $, there exists at least one additional divisor $ d_2 $ (where $ 1 < d_2 < n $), making the sum strictly larger than $ n $ but still less than $ n^2 $.

Template:INO box

Solution 2

We rewrote the expression so we have to show \[ \frac{1}{d_1 d_2} + \frac{1}{d_2 d_3} + \cdots + \frac{1}{d_{k-1} d_k} < 1. \]

Then we showed that if two terms of any sequence of the form \[ \frac{1}{a_1 a_2} + \frac{1}{a_2 a_3} + \cdots \] where $1 < a_2 < a_3 < \cdots < a_k$, are of the form $d_i = d_{i-1}+1$ and $d_{i+1} = d_i+1$, then the two terms containing them are maximized.

Next, we showed that if \[ \frac{1}{d_1 d_2} + \cdots = B, \] then cross multiplying denominators means that $k-1$ terms are multiplied by a term of $(1+k_1+k_2+\cdots)$ whereas $k$ terms are multiplied in the denominator, implying the multiplication of $(1+k_1+k_2+\cdots)$. Thus if the expression is equivalent to $B$, multiplication by $(1+k_1+\cdots)$ yields \[ \frac{(1+k_1+k_2+\cdots)(B-a)}{1+k_1+k_2+\cdots} + \frac{a}{k_1+k_2+k_3+\cdots} = B-a + \frac{a}{k_1+k_2+k_3+\cdots}, \] which is minimized if $k_1 = k_2 = k_3 = 1$.

Since we have shown the maximizing configuration for the sequence, we can proceed to show that the infinite sum is maximizing: \[ \frac{1}{2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + \cdots. \]

Moreover this sum is \[ < \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \cdots < 1, \] which means the first part is shown.

Finally, for the second part, if \[ \frac{1}{d_1 d_2} + \frac{1}{d_2 d_3} + \cdots = \frac{1}{d_i}, \] then if $d_i > d_2$ it is impossible. Also if $d_i = 1$ it is impossible from the first part. Thus $d_i = d_2$.

This only works when $n$ is prime, as we have \[ \frac{1}{d_2} + \cdots = \frac{1}{d_2} \] and the `` $+\cdots$ needs to be zero.

2002 IMO (Problems) • Resources
Preceded by Problem 3	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 5
All IMO Problems and Solutions

Page

Toolbox

Search