IMO2003 problem B2

[eepiccolo]

Here is the fifth problem from the 44th International Mathematical Olympiad. The other five are posted also. I don't know the answers, but I'll be working on them when I get the chance.

B2. Given n > 2 and reals x_1 <= x_2 <= ... <= x_n, show that (Σ_i,j |x_i - x_j| )^2 <= (2/3) (n^2 - 1) Σ_i,j (x_i - x_j)^2. Show that we have equality iff the sequence is an arithmetic progression.

[eepiccolo]

Well, here is a solution to part of the problem that NickGlover sent me several days ago.

Originally Posted by NickGlover

I only proved the second part of problem B2

First, we inductively prove formulas for the summations.

sum(i,j) |x_i - x_j| = (n-1)*n*(n+1)*a/3, where a is difference between two consecutive elements in the progression.

Proof by induction:

Base case, n = 3.

Let x_2 = x_1 + a and x_3 = x_1 + 2a.

The summation is

|x_1 - x_2| + |x_1 - x_3| + |x_2 - x_1| + |x_2 - x_3| + |x_3 - x_1| + |x_3 - x_2| = a + 2a + a + a + 2a + a = 8a

(3-1)*3*(3+1)*a/3 = 8a, so the formula is true for the base case.

Now we will prove: if sum(i,j) |x_i - x_j| = (n-1)*n*(n+1)*a/3 for n elements, then sum(i,j) |x_i - x_j| = n*(n+1)*(n+2)*a/3 for n+1 elements.

If we start with n elements with the summation being (n-1)*n*(n+1)*a/3, we can add an (n+1)th element on the end and calculate the new sum.

The new sum will have to add in
|x_n+1 - x_1| + |x_n+1 - x_2| + ... + |x_n+1 - x_n-1| + |x_n+1 - x_n|
AND
|x_1 - x_n+1| + |x_2 - x_n+1| + ... + |x_n-1 - x_n+1| + |x_n - x_n+1|

These sums are the same sum, so we are really just adding in two times one of them. This sum will be (reversing the order of the terms)

2(a + 2a + ... + (n-1)a + na)
= 2a(1 + 2 + ... + (n-1) + n))
= 2a*n(n+1)/2
= n(n+1)*a.

Now we add this to (n-1)*n*(n+1)*a/3 to get

(n-1)*n*(n+1)*a/3 + n(n+1)*a
= ((n-1)*n*(n+1)*a + 3n(n+1)*a)/3
= (n(n+1)(n-1 + 3))*a/3
= n(n+1)(n+2)*a/3

This does correspond to the formula for the summation for n+1.

Therefore we have proven that sum(i,j) |x_i - x_j| = (n-1)*n*(n+1)*a/3

Next, we prove:

sum(i,j)(x_i - x_j)^2 = (n-1)*(n^2)*(n+1)*a^2/6

Base case, n = 3.

The summation is similar to above except squaring the terms, so we get a^2 + 4a^2 + a^2 + a^2 + 4a^2 + a^2 = 12a^2

(3-1)*(3^2)*(3+1)*a^2/6 = 2*9*4*a^2/6 = 12a^2, so the formula works for the base case.

Now we will prove: if sum(i,j)(x_i - x_j)^2 = (n-1)*(n^2)*(n+1)*a^2/6 for n elements, then sum(i,j)(x_i - x_j)^2 = n*(n+1)^2*(n+2)*a^2/6 for n+1 elements.

If we start with n elements with the summation being (n-1)*(n^2)*(n+1)*a^2/6, we can add an (n+1)th element on the end and calculate the new sum.

The new sum will have to add in
(x_n+1 - x_1)^2 + (x_n+1 - x_2)^2 + ... + (x_n+1 - x_n-1)^2 + (x_n+1 - x_n)^2
AND
(x_1 - x_n+1)^2 + (x_2 - x_n+1)^2 + ... + (x_n-1 - x_n+1)^2 + (x_n - x_n+1)^2

These sums are the same sum, so we are really just adding in two times one of them. This sum will be (reversing the order of the terms)

2(a^2 + 4a^2 + ... + ((n-1)^2)*(a^2) + (n^2)*(a^2))
= 2a^2(1 + 4 + ... + (n-1)^2 + n^2))
= 2a^2*n*(n+1)*(2n+1)/6
= n*(n+1)*(2n+1)*a^2/3.

Now we add this to (n-1)*(n^2)*(n+1)*a^2/6 to get

(n-1)*(n^2)*(n+1)*a^2/6 + n*(n+1)*(2n+1)*a^2/3
= ((n-1)*(n^2)*(n+1) + 2n*(n+1)*(2n+1))*a^2/6
= n*(n+1)*(n(n-1) + 2*(2n+1))*a^2/6
= n*(n+1)*(n^2-n + 4n+2)*a^2/6
= n*(n+1)*(n^2+3n+2)*a^2/6
= n*(n+1)*(n+1)*(n+2)*a^2/6
= n*(n+1)^2*(n+2)*a^2/6

This does correspond to the formula for the summation for n+1.

Therefore we have proven that sum(i,j)(x_i - x_j)^2 = (n-1)*(n^2)*(n+1)*a^2/6

Now we simply substitute these results into the main equation, (sum(i,j) |x_i - x_j| )^2 = (2/3)*(n^2 - 1)*sum(i,j)(x_i - x_j)^2 to get

((n-1)*n*(n+1)*a/3)^2 = (2/3)*(n^2 - 1)*(n-1)*(n^2)*(n+1)*a^2/6
((n-1)^2)*(n^2)*((n+1)^2)*a^2/9 = (2/3)*(n-1)*(n+1)*(n-1)*(n^2)*(n+1)*a^2/6
((n-1)^2)*(n^2)*((n+1)^2)/3 = 2*((n-1)^2)*(n^2)*((n+1)^2)/6
((n-1)^2)*(n^2)*((n+1)^2)/3 = ((n-1)^2)*(n^2)*((n+1)^2)/3

Therefore, with an arithmetic progression, both sides of the equation are equal.

[NickGlover]

Oh, I did realize that my proof didn't properly handle the "iff". Instead I only proved

Given n > 2 and reals x_1 <= x_2 <= ... <= x_n, if the sequence is an arithmetic progression, show that (sum(i,j) |x_i - x_j| )^2 = (2/3)*(n^2 - 1)*sum(i,j)(x_i - x_j)^2.

I worked it at a while trying to figure out how to prove the first question and the second part of the second question, but I was not successful.