USAMO 87/5 solution

16th USAMO 1987

Problem 5

a₁, a₂, ... , a_n is a sequence of 0s and 1s. T is the number of triples (a_i, a_j, a_k) with i < j < k which are not equal to (0, 1, 0) or (1, 0, 1). For 1 ≤ i ≤ n, f(i) is the number of j < i with a_j = a_i plus the number of j > i with a_j ≠ a_i. Show that T = f(1) (f(1) - 1)/2 + f(2) (f(2) - 1)/2 + ... + f(n) (f(n) - 1)/2. If n is odd, what is the smallest value of T?

Solution

For n odd, the smallest value of T is n(n-1)(n-3)/8 achieved by 01010... 010.

Suppose a particular a_i = 0. Let S_i be the set of a_j with j < i and a_j = a_i and a_j with j > i and a_j ≠ a_i. Suppose we take any two members of S_i and consider the triple formed with a_i itself. Surprisingly perhaps, they are all of the required form (a_i is bold):


... 0 ... 0 ... 0

... 0 ... 0 ... 1

... 0 ... 1 ... 1

Similarly, if a_i = 1:


... 1 ... 1 ... 1

... 1 ... 1 ... 0

... 1 ... 0 ... 0

Conversely, any triple of the required form can be considered (uniquely) to be an a_i with members of the triple before it equal to it and members of the triple after it unequal to it. Since f(m) ( f(m) - 1) is the number of ways of choosing two items from f(m), we have established that T = ∑ f(m) ( f(m) - 1).

We show that ∑ f(m) = n(n-1)/2 (and is hence independent of the details of the particular sequence a_i - it depends only on its length). In the case of a sequence of all 0s, we have f(1) = 0, f(2) = 1, ... , f(n) = n-1, so ∑ f(m) = n(n-1)/2. Now suppose we have a particular sequence and we change a_i from 0 to 1. Suppose there are a 0s before a_i, b 1s before a_i, c 0s after a_i and d 1s after a_i. Then the value of f(i) is changed from a + d to b + c, an increase of (b - a) + (c - d). The value of f(j) with j < i is decreased by 1 if f(j) is 0 and increased by 1 if f(j) is 0. So in total there is an increase of (a - b) for such j. Similarly, for j > i, the value of f(j) is decreased by 1 if f(j) is 0 and increased by 1 if f(j) is 1, a net increase of (d - c). Thus overall ∑ f(m) is increased by (b - a) + (c - d) + (a - b) + (d - c) = 0. But by a sequence of such changes we can get to any sequence a_i, so all sequences (of length n) have the same value for ∑ f(m).

Thus T is minimised when ∑ f(m)² is minimised. But since ∑ f(m) is fixed, that is achieved when the f(m) are as equal as possible. If n =2k+1, then ∑ f(m) = n(n-1)/2, so the average value of f(m) is exactly k, so we look for an arrangement with all f(m) = k. It is not hard to see that 01010...1010 works. So this gives T = ∑ k(k-1)/2 = n(n-1)(n-3)/8.

The question does not ask for it, but the even case is also straightforward. If n = 2k, then the best we can hope for is k values of k and k values of k-1, so that ∑ f(m) = k.k + k.(k-1) = k(2k-1) = n(n-1)/2. That is achieved by 0101...0101 (all the 0s have f(m) = k and all the 1s have f(m) = k-1). Hence T = k.k(k-1)/2 + (k-1).(k-1)(k-2)/2 = (k-1)(2k²-3k+2)/2 = (n-2)(n²-3n+4)/8.

16th USAMO 1987