16
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – heropup May 23 '16 at 13:54
  • 1
    $\begingroup$ This only depends on the number of $1$'s and $-1$'s in the sequence - you could phrase it in one variable. $\endgroup$ – Milo Brandt May 23 '16 at 13:58
  • $\begingroup$ @steamyroot yes, its positive sorry. $\endgroup$ – ItsImpulse May 23 '16 at 14:09
  • $\begingroup$ 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? $\endgroup$ – DCShannon May 23 '16 at 22:55
  • $\begingroup$ @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$ $\endgroup$ – phihag May 23 '16 at 23:20
25
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – ItsImpulse May 23 '16 at 14:06
  • $\begingroup$ Think about what value $\sum a_i$ can take, given the limited possibilities of $a_i$. $\endgroup$ – hardmath May 23 '16 at 14:07
  • $\begingroup$ @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. $\endgroup$ – Semiclassical May 23 '16 at 14:09
  • 2
    $\begingroup$ 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! $\endgroup$ – ItsImpulse May 23 '16 at 14:15
  • $\begingroup$ @ItsImpulse : what is $46$ ? I don't get it $\endgroup$ – reuns May 25 '16 at 3:43
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.