IMO 2001 SL C1

Origin: COL | Category: Combinatorics

Problem

Let A = (a1, a2, . . . , a2001) be a sequence of positive integers. Let m be the number of 3-element subsequences (ai, aj, ak) with 1 \leqi < j < k \leq2001 such that aj = ai + 1 and ak = aj + 1. Considering all such sequences A, find the greatest value of m.

Solution

It is evident that arranging of A in increasing order does not diminish m. Thus we can assume that A is nondecreasing. Assume w.l.o.g. that a1 = 1, and let bi be the number of elements of A that are equal to i (1 \leqi \leqn = a2001). Then we have b1 + b2 + \cdot \cdot \cdot + bn = 2001 and m = b1b2b3 + b2b3b4 + \cdot \cdot \cdot + bn−2bn−1bn. (1) Now if bi, bj (i < j) are two largest b’s, we deduce from (1) and the AM– GM inequality that m \leqbibj(b1+\cdot \cdot \cdot+bi−1+bi+1+\cdot \cdot \cdot+bj−1+bj+1+bn) \leq
2001 3 = 6673 (b1b2b3 \leqb1bibj, etc.). The value 6673 is attained for b1 = b2 = b3 = 667 (i.e., a1 = \cdot \cdot \cdot = a667 = 1, a668 = \cdot \cdot \cdot = a1334 = 2, a1335 = \cdot \cdot \cdot = a2001 = 3). Hence the maximum of m is 6673.