Russian problems Problem 56 (a) Each of x 1 , ... , x n is -1, 0 or 1. What is the minimal possible value of the sum of all x i x j with 1 <= i < j <= n? (b) Is the answer the same if the x i are real numbers satisfying 0 <= |x i | <= 1 for 1 <= i <= n? Solution (a)
: -[n/2]. Let A = (x 1 + ... + x n ) 2 , B = x 1 2 + ... + x n 2 . Then we must minimize A - B. For n even, we separately minimize A and maximize B by taking half the x's to be +1 and half to be -1. For n odd we can take [n/2] x's to be +1, [n/2] to be -1, and one to be 0. That minimizes A and gives B one less than its maximum. That is the best we can do if we fix A = 0, since A = 0 requires an even number of x's to be non-zero and hence at least one to be zero. If we do not minimize A, then since its value must be an integer, its value will be at least 1. In that case, even if B is maximized we will not get a lower total. (b) : -[n/2]. For n even, the same argument works. For n odd we can clearly get -[n/2], so it remains to prove that we cannot get a smaller sum. Suppose otherwise, so that x i is a minimal sum with sum less than -[n/2]. Let x n = x, then the sum is x(x 1 + ... + x n-1 ) + sum of terms x i x j with 1 <= i, j < n. But this is less than the sum for n-1, so x(x 1 + ... + x n-1 ) must be negative, and since it is minimal we must have |x| = 1. But the same argument shows that all the terms have modulus 1. We now have a contradiction since we know that the minimum in this case is -[n/2]. Russian 51-60 (C) John Scholes jscholes@kalva.demon.co.uk 24 Sep 1998