Let $x_{1}, \ldots, x_{n}$ be real numbers taking values $0, +1$ or -1. What is the minimum of

$$
\sum_{1 \leq i<j \leq n} x_{i} x_{j} ?
$$
The sum $\sum_{1 \leq i<j \leq n} x_{i} x_{j}$ closely resembles what appears when expanding $\left(\sum x_{i}\right)^{2}$. However, there are two issues: each term $x_{i} x_{j}$ is counted twice, and the terms $x_{i}^{2}$ appear:

$$
\left(\sum_{i=1}^{n} x_{i}\right)^{2}=2 \sum_{1 \leq i<j \leq n} x_{i} x_{j}+\sum_{i=1}^{n} x_{i}^{2}
$$

The term $\left(\sum_{i=1}^{n} x_{i}\right)^{2}$ is positive since it is a square, and each $x_{i}^{2}$ is less than 1, so the term $\sum_{i=1}^{n} x_{i}^{2}$ is less than $n$.

$$
\sum_{1 \leq i<j \leq n} x_{i} x_{j}=\frac{1}{2}\left(\left(\sum_{i=1}^{n} x_{i}\right)^{2}-\sum_{i=1}^{n} x_{i}^{2}\right) \geq \frac{-n}{2}
$$

If $n$ is even, this minimum is achieved when half of the $x_{i}$ are +1 and the other half are -1. For $n$ odd, $\sum_{i<j} x_{i} x_{j} \leq \frac{-n}{2}$ and this sum is an integer, so it is at least $\frac{-n+1}{2}$, and this minimum is achieved with $x_{1}=0$ and the rest of the $x_{i}$ split between +1 and -1.