# 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.

• Try some small cases first, rather than the case with $2014$. What does that tell you? Provide your effort in the small case in your question. – heropup May 23 '16 at 13:54
• This only depends on the number of $1$'s and $-1$'s in the sequence - you could phrase it in one variable. – Milo Brandt May 23 '16 at 13:58
• @steamyroot yes, its positive sorry. – ItsImpulse May 23 '16 at 14:09
• It's been quite a few years since I was a mathlete, but there doesn't seem to be enough of a constraint on j for this question to be non-trivial. Just make a2014 = -1, all the others equal to 1, and choose j for each i such that they all even out except for one, and your answer is 1. What am I missing in the problem statement? – DCShannon May 23 '16 at 22:55
• @DCShannon The notation is short for a sum over all values of i and j, so you can't choose j. Another way of writing it would be $\displaystyle \sum_{i=1}^{1024}\sum_{j=i+1}^{1024} a_i a_j$ – phihag May 23 '16 at 23:20

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.$

• So that will give $M=\sum^{}_{1\leq i<j\leq 2014}a_{i}a_{j}=\frac{1}{2} [(\sum^{2014}_{i=1}a_{i})^{2}-2014]$ since $a_i$ can only be 1 or -1 the term just becomes 2014. But how do i deal with the other term? – ItsImpulse May 23 '16 at 14:06
• Think about what value $\sum a_i$ can take, given the limited possibilities of $a_i$. – hardmath May 23 '16 at 14:07
• @SteamyRoot's comment above is relevant here: I can easily enough come up with a sequence such that $\sum_i a_i=0$ and get $M=-1007$. So some additional constraint is needed to get 51 as the result. – Semiclassical May 23 '16 at 14:09
• Since $a_i$ is either 1 or -1, the difference between choosing one as 1 or -1 would be 2. So it has to be an even number and getting $0.5(46^2-2014)=51$ ah thank you! – ItsImpulse May 23 '16 at 14:15
• @ItsImpulse : what is $46$ ? I don't get it – reuns May 25 '16 at 3:43

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