
2. For an integer $n \geqslant 1$ we consider sequences of $2 n$ numbers, each equal to $0,-1$ or 1 . The sum product value of such a sequence is calculated by first multiplying each pair of numbers from the sequence, and then adding all the results together.

For example, if we take $n=2$ and the sequence $0,1,1,-1$, then we find the products $0 \cdot 1, \quad 0 \cdot 1$, $0 \cdot-1, \quad 1 \cdot 1, \quad 1 \cdot-1, \quad 1 \cdot-1$. Adding these six results gives the sum product value of this sequence: $0+0+0+1+(-1)+(-1)=-1$. The sum product value of this sequence is therefore smaller than the sum product value of the sequence $0,0,0,0$, which equals 0 .

Determine for each integer $n \geqslant 1$ the smallest sum product value that such a sequence of $2 n$ numbers could have.

Attention: you are required to prove that a smaller sum product value is impossible.


2. Suppose that our sequence has $x$ ones, $y$ minus ones (and hence $2 n-x-y$ zeroes). We calculate the sum product value of the sequence (as an expression in $x$ and $y$ ).

In the sum product value, six different types of terms occur: $1 \cdot 1,1 \cdot-1,-1 \cdot-1,1 \cdot 0,-1 \cdot 0$, and $0 \cdot 0$. Only the first three types contribute since the other types are equal to 0 .

The number of terms of the type $1 \cdot 1=1$ equals the number of ways to select two out of $x$ ones. This can be done in $\frac{x(x-1)}{2}$ ways: there are $x$ options for the first 1 , and then $x-1$ options for the second 1. Since the order in which we select the two ones does not matter, we effectively count each possible pair twice.

Similarly, the number of terms of the type $-1 \cdot-1=1$ is equal to $\frac{y(y-1)}{2}$.

The number of terms of the type $1 \cdot-1=-1$ is equal to $x y$, since there are $x$ options for choosing a 1 and, independently, there are $y$ options for choosing a -1 .

In total, we obtain a sum product value of

$$
S=\frac{x(x-1)}{2} \cdot 1+\frac{y(y-1)}{2} \cdot 1+x y \cdot-1=\frac{x^{2}-2 x y+y^{2}-x-y}{2}=\frac{(x-y)^{2}-(x+y)}{2} .
$$

Since $(x-y)^{2} \geqslant 0$ (squares are non-negative) and $-(x+y) \geqslant-2 n$ (there are only $2 n$ numbers in the sequence), we see that $S \geqslant \frac{0-2 n}{2}=-n$. So the sum product value cannot be smaller than $-n$. If we now choose $x=y=n$, then $(x-y)^{2}=0$ and $-x-y=-2 n$, which imply a sum product value of exactly $\frac{0-2 n}{2}=-n$. Therefore, the smallest possible sum product value is $-n$.
