IMO 2003/B2 solution

IMO 2003

Problem B2

Given n > 2 and reals x₁ <= x₂ <= ... <= x_n, show that (∑_i,j |x_i - x_j| )² ≤ (2/3) (n² - 1) ∑_i,j (x_i - x_j)². Show that we have equality iff the sequence is an arithmetic progression.

Solution

Thanks to Li Yi

Notice first that if we restrict the sums to i < j, then they are halved. The lhs sum is squared and the rhs sum is not, so the the desired inequality with sums restricted to i < j has (1/3) on the rhs instead of (2/3).

Consider the sum of all |x_i - x_j| with i < j. x₁ occurs in (n-1) terms with a negative sign. x₂ occurs in one term with a positive sign and (n-2) terms with a negative sign, and so on. So we get -(n-1)x₁ - (n-3)x₂ - (n-5)x₃ - ... + (n-1)x_n = ∑ (2i-1-n)x_i.

We can now apply Cauchy-Schwartz. The square of this sum is just ∑ x_i² ∑ (2i-1-n)².

Looking at the other side of the desired inequality, we see immediately that it is n ∑ x_i² - (∑ x_i)². We would like to get rid of the second term, but that is easy because if we add h to every x_i the sums in the desired inequality are unaffected (since they use only differences of x_i), so we can choose h so that ∑ x_i is zero. Thus we are home if we can show that ∑ (2i-1-n)² ≤ n(n² - 1)/3. That is easy: lhs = 4 ∑ i² - 4(n+1) ∑ i + n(n+1)² = (2/3)n(n+1)(2n+1) - 2n(n+1) + n(n+1)² = (1/3)n(n+1)(2(2n+1) - 6 + 3(n+1) ) = (1/3)n(n² - 1) = rhs. That establishes the required inequality.

We have equality iff we have equality at the Cauchy-Schwartz step and hence iff x_i is proportional to (2i-1-n). That implies that x_i+1 - x_i is constant. So equality implies that the sequence is an AP. But if the sequence is an AP with difference d (so x_i+1 = x_i + d) and we take x₁ = -(d/2)(n-1), then we get x_i = (d/2)(2i-1-n) and ∑ x_i = 0, so we have equality.

44th IMO 2003