2006 Romanian NMO Problems/Grade 8/Problem 2

Problem

Let $n$ be a positive integer. Prove that there exists an integer $k$, $k\geq 2$, and numbers $a_i \in \{ -1, 1 \}$, such that

$n = \sum_{1\leq i < j \leq k } a_ia_j$.

Solution

Suppose that there exists such an integer $k$ and numbers $a_i \in \{ -1, 1 \}$, $i\in \{1,\ldots,k\}$ such that $n = \sum_{1\leq i < j \leq k } a_ia_j$. Let \begin{align*}X &= \#\{i\in [k] \;:\; a_{i}=-1\} \\ Y &= \#\{i\in [k] \;:\; a_{i}=1\}\end{align*} then \[n=\sum_{1\leq i < j \leq k } a_ia_j = \binom{X}{2}+\binom{Y}{2}-XY = \frac{(X-Y)^{2}-(X+Y)}{2}.\] We see that if $X$ and $Y$ are increased by $1$, then $n$ is decreased by $1$. This motivates the following construction: Let $m$ be large enough such that $\binom{m}{2} > n$, let $Y = \binom{m}{2} - n$ and $X = Y+m$, let $k = X+Y$, and let $a_{1},\ldots,a_{X} = -1$ and $a_{X+1},\ldots,a_{X+Y} = 1$. Then \begin{align*}\sum_{1\leq i < j \leq k } a_ia_j &= \binom{X}{2}+\binom{Y}{2}-XY\\ &= \frac{(X-Y)^{2}-(X+Y)}{2} \\ &= \frac{m^{2}-\left(m+\binom{m}{2} - n+\binom{m}{2} - n\right)}{2} \\ &= n.\end{align*}

See also