Kvant Math Problem 13
Consider first small values of $n$ to understand the structure of the sum of pairwise differences.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m21s
Source on kvant.digital
Problem
Prove that if the difference between the largest and the smallest of the $n$ real numbers $a_1$, $a_2$, $\ldots$, $a_n$ is equal to $d$, and the sum of the absolute values of all $\dfrac{n(n-1)}{2}$ pairwise differences of these numbers $$\sum_{i \lt j} |a_i - a_j|$$ is equal to $s$, then $$(n-1)d \le s \le \frac{n^2}{4}d.$$
Exploration
Consider first small values of $n$ to understand the structure of the sum of pairwise differences. For $n=2$, with numbers $a_1$ and $a_2$, the sum of absolute differences is $|a_1 - a_2| = d$, which coincides with $(n-1)d = 1\cdot d$ and $\frac{n^2}{4}d = 1\cdot d$, so both bounds are tight. For $n=3$, let $a_1 \le a_2 \le a_3$ with $a_3 - a_1 = d$. The sum of differences is $|a_2 - a_1| + |a_3 - a_1| + |a_3 - a_2| = (a_2 - a_1) + (a_3 - a_1) + (a_3 - a_2) = 2(a_3 - a_1) = 2d$. This coincides with $(n-1)d = 2d$, giving the lower bound. The upper bound $\frac{n^2}{4}d = \frac{9}{4}d$ allows some flexibility, suggesting the sum can be increased by spreading the numbers differently. Testing numbers $0$, $d/2$, $d$ gives sum $d/2 + d + d/2 = 2d$, again the same as before. Testing $0$, $0$, $d$ gives $0 + d + d = 2d$, still within bounds. This indicates that the sum is minimal when numbers are clustered at extremes. The sum is likely maximized when numbers are evenly spread, as the differences between distant numbers increase. The largest sum should occur when half the numbers are at $0$ and half at $d$, giving $n_0 n_d$ pairs of difference $d$, where $n_0 + n_d = n$, and $n_0 n_d$ is maximized when $n_0 = n_d = n/2$, yielding $s = n^2 d /4$. The crucial step is justifying why no other configuration can exceed this upper bound.
Problem Understanding
The problem asks to bound the sum $s$ of all pairwise absolute differences of $n$ real numbers given that their spread (largest minus smallest) is $d$. This is a Type C problem because we are determining extremal values of $s$. The lower bound $(n-1)d$ is reached when all numbers except one coincide with either extreme, so each contributes minimal differences. The upper bound $n^2 d /4$ is reached when numbers are split evenly between the extremes, maximizing pairwise differences. The core difficulty is rigorously proving that no other distribution of numbers can produce a sum outside these bounds.
Proof Architecture
Lemma 1: For $n$ real numbers $a_1 \le \dots \le a_n$ with $a_n - a_1 = d$, the sum $s$ satisfies $s \ge (n-1)d$. Sketch: The sum of differences involving $a_1$ and $a_n$ is at least $(n-1)d$ because each extreme appears in $n-1$ pairs with positive differences.
Lemma 2: For the same numbers, $s \le \frac{n^2}{4} d$. Sketch: Split numbers into two clusters, one at $a_1$ and one at $a_n$, maximizing the number of pairs across clusters. The sum is $n_1 n_2 d \le n^2 d /4$, with $n_1 + n_2 = n$. The crux is showing no arrangement with intermediate points can exceed this.
Lemma 3: The extremal configurations for each bound are characterized by clustering at extremes. Sketch: For the lower bound, all numbers except one coincide at one extreme; for the upper bound, numbers split evenly at the two extremes.
The hardest direction is Lemma 2, ensuring that distributing numbers in the interior does not produce a larger sum than splitting into extremes.
Solution
Let $a_1 \le a_2 \le \dots \le a_n$ and denote $d = a_n - a_1$. The sum of all pairwise absolute differences is
$$s = \sum_{1 \le i < j \le n} (a_j - a_i).$$
Rewriting this, each $a_k$ appears with positive coefficient in the differences with all $a_j$ for $j>k$ and negative coefficient with all $a_i$ for $i<k$:
$$s = \sum_{k=1}^n [(k-1) a_k - (n-k) a_k] = \sum_{k=1}^n (2k - n -1) a_k.$$
For the lower bound, observe that $a_1$ and $a_n$ contribute $(a_n - a_1)$ to each pair involving one of them. There are $n-1$ pairs containing $a_n$ and $a_1$, so $s \ge (n-1)d$. Equality is attained when all intermediate numbers coincide with either $a_1$ or $a_n$, giving minimal additional differences.
For the upper bound, consider placing $n_1$ numbers at $a_1$ and $n_2$ numbers at $a_n$, with $n_1 + n_2 = n$. Then all differences between clusters equal $d$, giving sum $s = n_1 n_2 d$. The product $n_1 n_2$ is maximized for $n_1 = n_2 = n/2$ (or as close as possible for odd $n$), yielding $s \le n^2 d /4$. Any intermediate $a_k$ strictly between $a_1$ and $a_n$ contributes differences less than $d$ with at least one of the extremes, hence cannot increase $s$ beyond $n^2 d /4$.
Combining these arguments, we obtain the desired inequality
$$(n-1)d \le s \le \frac{n^2}{4} d.$$
This completes the proof.
∎
Verification of Key Steps
The key step for the lower bound is counting pairs containing the extremes. For $n=4$ with numbers $0, 0, 0, d$, the sum of differences is $d + d + d + d + d + d = 3d = (n-1)d$, confirming the bound. For the upper bound, test $n=4$ with numbers split as $0,0, d,d$, the sum of differences is $0+0+d+d+d+d = 4d = n^2 d /4$, verifying the maximal configuration. Introducing any interior number $x$ with $0 < x < d$ reduces some differences to less than $d$, producing sum strictly less than $4d$, confirming no configuration exceeds the bound.
Alternative Approaches
An alternative approach is to model the sum as a quadratic form in the ordered differences $b_i = a_{i+1} - a_i$, with $b_1 + \dots + b_{n-1} = d$, and $s$ linear in $b_i$ with coefficients $(n-i)i$. Maximizing $s$ reduces to distributing $d$ among $b_i$ with constraints, yielding that concentrating all $d$ in the middle difference is suboptimal, and the extremal distributions occur when $b_1 = d$, $b_2 = \dots = b_{n-1} = 0$, or symmetric at the end. This method generalizes systematically to unequal partitions, but the main approach is more intuitive and transparent, avoiding combinatorial bookkeeping of intermediate differences.