IMO 1982 SL 11

Problem

B5 (CAN 3) (a) Find the rearrangement {a1, . . . , an} of {1, 2, . . ., n} that maximizes a1a2 + a2a3 + \cdot \cdot \cdot + ana1 = Q. (b) Find the rearrangement that minimizes Q.

Solution

(a) Suppose {a1, a2, . . . , an} is the arrangement that yields the maxi- mal value Qmax of Q. Note that the value of Q for the rearrange- ment {a1, . . . , ai−1, aj, aj−1, . . . , ai, aj+1, . . . , an} equals Qmax −(ai − aj)(ai−1−aj+1), where 1 < i < j < n. Hence (ai−aj)(ai−1−aj+1) \geq0 for all 1 < i < j < n.

We may suppose w.l.o.g. that a1 = 1. Let ai = 2. If 2 < i < n, then (a2 −ai)(a1 −ai+1) < 0, which is impossible. Therefore i is either 2 or n; let w.l.o.g. an = 2. Further, if aj = 3 for 2 < j < n, then (a1 −aj+1)(a2 −aj) < 0, which is impossi- ble; therefore a2 = 3. Continuing this argument we obtain that A = {1, 3, 5, . . ., 2[(n −1)/2] + 1, 2[n/2], . . ., 4, 2}. (b) A similar argument leads to the minimizing rearrangement {1, n, 2, n −1, . . . , [n/2] + 1}.