2002 IMO Problems/Problem 4

Problem: Let be an integer and let be all of its positive divisors in increasing order. Show that

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 \).

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 `` needs to be zero.

See Also

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