IMO 1991 SL 27

Origin: POL

Problem

Determine the maximum value of the sum  i<j xixj(xi + xj) over all n-tuples (x1, . . . , xn), satisfying xi \geq0 and n i=1 xi = 1.

Solution

Write F(x1, . . . , xn) =  i<j xixj(xi+xj). Choose an n-tuple (x1, . . . , xn), n i=1 xi = 1, xi \geq0 with at least three nonzero components, and assume w.l.o.g. that x1 \geq\cdot \cdot \cdot \geqxk−1 \geqxk \geqxk+1 = \cdot \cdot \cdot = xn = 0. We claim that replacing xk−1, xk with xk−1 + xk, 0 the value of F increases. Write for brevity xk−1 = a, xk = b. Then F(. . . , a + b, 0, 0, . . .) −F(. . . , a, b, 0, . . .)

k−2  i=1 xi(a + b)(xi + a + b) − k−2  i=1 [xia(xi + a) + xib(xi + b)] −ab(a + b)

= ab

k−2  i=1 xi −a −b

= ab(2 −3(a + b)) > 0, because xk−1 + xk \leq2 3(x1 + xk−1 + xk−2) \leq2 3. Repeating this procedure we can reduce the number of nonzero xi’s to two, increasing the value of F in each step. It remains to maximize F over n-tuples (x1, x2, 0, . . . , 0) with x1, x2 \geq0, x1 + x2 = 1: in this case F equals x1x2 and attains its maximum value 1 4 when x1 = x2 = 1 2, x3 = . . . , xn = 0.