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$
7
  • 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
    Commented May 23, 2016 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$ Commented May 23, 2016 at 13:58
  • $\begingroup$ @steamyroot yes, its positive sorry. $\endgroup$
    – ItsImpulse
    Commented May 23, 2016 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
    Commented May 23, 2016 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
    Commented May 23, 2016 at 23:20

2 Answers 2

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .