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*}$

Page

Toolbox

Search

2006 Romanian NMO Problems/Grade 8/Problem 2

Problem

Solution

See also