Minimal value of $\sum_{1\leq i<j\leq 2014}a_ia_j$ where $a_i=\pm1$

Let $a_i \in \{-1,1\}$ for all $i=1,2,3,...,2014$ and $$M=\sum^{}_{1\leq i<j\leq 2014}a_{i}a_{j}.$$ Find the least possible positive value of $M$.

Came across this question in a Math Olympiad and I'm not sure how to even start, the answer given is 51.

Solution 1:

Hint: $\displaystyle \left(\sum_{i=1}^{2014}a_i\right)^2=\sum_{i=1}^{2014}a_i\sum_{j=1}^{2014}a_j = \sum_{i=1}^{2014}a_i^2+2\sum_{1\leq i<j\leq 2014}a_i a_j.$

Solution 2:

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\, #2 \,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $$ \mbox{Since}\quad \sum_{1\ <\ i\ <\ j\ <\ 2014}a_{i}a_{j} = \half\bracks{\pars{\sum_{i = 1}^{2014}a_{i}}^{2} - 2014}\quad\mbox{with}\quad a_{i} = \pm 1 $$

the problem is reduced to find the minimum value of $\ds{\pars{\sum_{i = 1}^{2014}a_{i}}^{2}}$ such that

$$ \pars{\sum_{i = 1}^{2014}a_{i}}^{2} > 2014\quad\imp\quad \verts{\sum_{i = 1}^{2014}a_{i}} > \root{2014} \approx 44.8876 $$

Let $n_{+}$ the number of $a_{i}$'s that have the values $+1$. Then,

\begin{align} \sum_{i = 1}^{2014}a_{i} & = n_{+}\times 1 + \pars{2014 - n_{+}}\times\pars{-1} = 2\pars{n_{+} - 1007} \quad\mbox{which is a $\color{#f00}{even}$ number} \end{align}

So, we are forced to choose $\ds{\verts{\sum_{i = 1}^{2014}a_{i}} = \color{#f00}{46}}$ because $\ds{\color{#00f}{45}}$ is an $\color{#00f}{odd}$ number. Then

$$ \half\pars{46^{2} - 2014} = \color{#f00}{51} $$