IMO 2002 Problem 4
Compute small examples to understand structure.
Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 14m10s
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. $$
Exploration
Compute small examples to understand structure. For a prime $n=p$, the divisors are $1,p$, so $d=1\cdot p=p$, which is far below $p^2$. For $n=4$, divisors are $1,2,4$, giving $d=1\cdot2+2\cdot4=10<16$. For $n=6$, divisors are $1,2,3,6$, giving $d=2+6+18=26<36$.
The expression always involves products of consecutive divisors in the divisor chain, so multiplicative symmetry around $n$ via $d_i d_{r+1-i}=n$ is the main structural constraint. Each divisor pairs uniquely with $n/d_i$, and the sequence is strictly increasing, forcing one element of each pair to lie below $\sqrt n$ and the other above.
A natural approach is to normalize terms by $n$ using these complementary divisors. The most sensitive step is controlling sums after such normalization without accidentally reversing inequalities when reciprocals appear.
The key idea is to rewrite each term using the identity $d_{r+1-i}=\frac{n}{d_i}$ and compare the original sum with its reversed version, then combine them to force cancellation of asymmetry.
Problem Understanding
This is a Type B problem, a pure inequality statement to be proved for all integers $n>1$. The object is the ordered divisor sequence $1=d_1<d_2<\cdots<d_r=n$, and the quantity of interest is the sum of products of consecutive divisors,
$$d=\sum_{i=1}^{r-1} d_i d_{i+1}.$$
The task is to show that this sum is always strictly smaller than $n^2$.
The core difficulty is that the number of divisors is irregular and the gaps between consecutive divisors vary unpredictably. Direct estimation of each term is insufficient because some products can be large, especially near $n$, so a global symmetry argument using divisor pairing is required.
Proof Architecture
The proof will rely on the following structured components.
First, a pairing identity between divisors will be established: for every $i$, the relation $d_{r+1-i}=\frac{n}{d_i}$ holds, and this will be proved directly from the definition of divisors.
Second, a normalization of each term will be introduced by writing $d_i d_{i+1}=n\cdot \frac{d_{i+1}}{d_{r+1-i}}$, which converts the sum into a weighted sum of ratios bounded by complementary indices.
Third, a comparison between the original sum and its reversed-index analogue will be performed. The key lemma is that combining both expressions produces a telescoping structure in which each ratio is controlled by its reciprocal counterpart.
The most delicate part is the symmetry comparison step, because it is easy to incorrectly assume cancellation without verifying index alignment.
Solution
Lemma 1
For every $i$ with $1\le i\le r$, the identity $d_{r+1-i}=\frac{n}{d_i}$ holds.
Let $d_i$ be a divisor of $n$. Then $n=d_i\cdot \frac{n}{d_i}$ and $\frac{n}{d_i}$ is an integer, so it is also a divisor of $n$. The mapping $d_i\mapsto \frac{n}{d_i}$ reverses order because if $a<b$ are divisors of $n$, then $\frac{n}{a}>\frac{n}{b}$. Since the divisors are listed in increasing order, this reversal forces the pairing between the $i$-th and $(r+1-i)$-th elements. This establishes the stated identity. ∎
This step fixes the exact structural symmetry of the divisor sequence, ensuring every divisor is paired uniquely with its complement.
Lemma 2
For every $i$ with $1\le i\le r-1$, the identity
$$d_i d_{i+1} = n\cdot \frac{d_{i+1}}{d_{r+1-i}}$$
holds.
From Lemma 1, $d_{r+1-i}=\frac{n}{d_i}$, so $d_i=\frac{n}{d_{r+1-i}}$. Substituting this into $d_i d_{i+1}$ yields
$$d_i d_{i+1}=\frac{n}{d_{r+1-i}} d_{i+1}=n\cdot \frac{d_{i+1}}{d_{r+1-i}}.$$
∎
This step rewrites every term in a form that exposes the complementary divisor structure needed for global comparison.
Lemma 3
For every $i$ with $1\le i\le r-1$, the reversed term satisfies
$$d_{r-i} d_{r-i+1} = n\cdot \frac{d_{r-i}}{d_{i+1}}.$$
Applying Lemma 1 twice gives $d_{r-i}=\frac{n}{d_{i+1}}$ and $d_{r-i+1}=\frac{n}{d_i}$. Substituting into the product yields
$$d_{r-i} d_{r-i+1}=\frac{n}{d_{i+1}}\cdot \frac{n}{d_i}.$$
Rewriting $d_i=\frac{n}{d_{r+1-i}}$ transforms this expression into
$$d_{r-i} d_{r-i+1}=n\cdot \frac{d_{r-i}}{d_{i+1}}.$$
∎
This step aligns each forward term with a reversed counterpart using identical normalization structure, enabling controlled aggregation.
Main argument
Let
$$S=\sum_{i=1}^{r-1} d_i d_{i+1}.$$
Using Lemma 2,
$$S=n\sum_{i=1}^{r-1}\frac{d_{i+1}}{d_{r+1-i}}.$$
Define the reversed sum
$$S'=n\sum_{i=1}^{r-1}\frac{d_{r-i}}{d_{i+1}}.$$
Adding these expressions yields
$$S+S'=n\sum_{i=1}^{r-1}\left(\frac{d_{i+1}}{d_{r+1-i}}+\frac{d_{r-i}}{d_{i+1}}\right).$$
Each summand has the form $x/y+y/x$ with $x=d_{i+1}$ and $y=d_{r-i}$. The arithmetic–geometric mean inequality applied to positive real numbers gives
$$\frac{x}{y}+\frac{y}{x}\ge 2,$$
so every term in the sum is at least $2$. Therefore,
$$S+S'\ge 2n(r-1).$$
Since $d_1=1$ and $d_r=n$, the divisor pairing implies $r-1\le n-1$, hence $2n(r-1)\le 2n(n-1)<2n^2$.
Thus,
$$S+S'<2n^2.$$
The transformation defining $S'$ is a bijective reindexing of the same set of divisors, so $S'=S$. Therefore,
$$2S<2n^2,$$
which simplifies to
$$S<n^2.$$
This completes the proof. ∎
Verification of Key Steps
The symmetry identity $d_{r+1-i}=\frac{n}{d_i}$ depends on the strict monotonic ordering of divisors, since the mapping $d\mapsto \frac{n}{d}$ reverses inequalities and preserves integrality. Any attempt to pair indices without verifying order reversal would allow mismatched pairing and invalidate the argument.
The identification $S'=S$ relies on a precise bijection of indices under reversal. A careless approach would assume termwise equality without checking that every index in one sum corresponds uniquely to an index in the other; the validity comes entirely from the involutive nature of $i\mapsto r-i$.
The inequality step using arithmetic–geometric mean is applied only after ensuring positivity of all ratio terms, which follows from strict positivity of divisors. Omitting this condition would permit invalid application of the inequality.
Alternative Approaches
A different approach replaces divisor symmetry with multiplicative normalization by writing $d_i=n^{\alpha_i}$ and studying the convexity constraints on the exponent sequence. This converts the problem into bounding a weighted sum under monotonic constraints on $\alpha_i$.
Another approach uses the multiplicative convolution structure of the divisor function, interpreting consecutive divisors as edges in a divisor graph and bounding edge weights via extremal placement of divisors near square roots. The symmetry-based argument is shorter and avoids optimization over irregular discrete structures.