Inequality from UW challenge of the week [Solution]

The problem was here.

In brief

$x_i$ are $n$ real numbers such that

$$\sum _{k=1}^{n} x_i = 0$$

$$\sum_{k=1}^{n} x_i^2 = 1$$

Show that for some $i,j$,

$$x_i x_j \le -\frac{1}{n}$$

Solution

---

The official solution is quite neat.

wlog, assume $x_1 \le x_2 \le \dots \le x_n$.

Now

$$0 \le \sum_{k=1}^n (x_k - x_1)(x_n - x_k) = -nx_1x_n - 1$$

(The equality is just gotten from expanding out and using the given identities).

The inequality now follows immediately.