All-Soviet-Union Mathematical Olympiad

Solution:

a. Answer: $-\left[ n / 2 \right]$.

Let $A = (x_{1} + \ldots + x_{n})^{2}$, $B = x_{1}^{2} + \ldots + 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. Answer: $- [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} + \ldots + x_{n-1})$ plus the sum of terms $x_{i}x_{j}$ with $1 \leq i, j < n$. But this is less than the sum for $n-1$, so $x(x_{1} + \ldots + 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]$.