Problem

Source: Dutch NMO 2016 p2

Tags: algebra, Sequence, Sum, Product, minimum



For an integer $n \ge 1$ we consider sequences of $2n$ 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, 0\cdot 1, 0\cdot -1, 1\cdot 1, 1\cdot -1, 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 \ge 1$ the smallest sum product value that such a sequence of $2n$ numbers could have. Attention: you are required to prove that a smaller sum product value is impossible.