\section*{Problem 1}

(a) Each of \(\mathrm{x}_{1}, \ldots, \mathrm{x}_{\mathrm{n}}\) is \(-1,0\) or 1 . What is the minimal possible value of the sum of all \(\mathrm{x}_{\mathrm{i}} \mathrm{x}_{\mathrm{j}}\) with \(1<=\mathrm{i}<\mathrm{j}<=\mathrm{n}\) ? (b) Is the answer the same if the \(\mathrm{x}_{\mathrm{i}}\) are real numbers satisfying \(0<=\left|\mathrm{x}_{\mathrm{i}}\right|\) \(<=1\) for \(1<=\mathrm{i}<=\mathrm{n}\) ?


\section*{Solution}

(a) Answer: -[n/2].

Let \(\mathrm{A}=\left(\mathrm{x}_{1}+\ldots+\mathrm{x}_{\mathrm{n}}\right)^{2}, \mathrm{~B}=\mathrm{x}_{1}{ }^{2}+\ldots+\mathrm{x}_{\mathrm{n}}{ }^{2}\). Then we must minimize A - B. For \(\mathrm{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 \([\mathrm{n} / 2]\) x's to be \(+1,[\mathrm{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 \(\mathrm{A}=0\), since \(\mathrm{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 \(\mathrm{n}\) even, the same argument works. For \(\mathrm{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 \(\mathrm{x}_{\mathrm{n}}=\mathrm{x}\), then the sum is \(\mathrm{x}\left(\mathrm{x}_{1}+\ldots+\mathrm{x}_{\mathrm{n}-1}\right)+\) sum of terms \(\mathrm{x}_{\mathrm{i}} \mathrm{x}_{\mathrm{j}}\) with \(1<=\mathrm{i}, \mathrm{j}<\mathrm{n}\). But this is less than the sum for \(\mathrm{n}-1\), so \(\mathrm{x}\left(\mathrm{x}_{1}+\ldots+\mathrm{x}_{\mathrm{n}-1}\right)\) 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]\).

