current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 15 down vote favorite
3

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.

share|cite|improve this question
5  
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 11 hours ago
1  
This only depends on the number of $1$'s and $-1$'s in the sequence - you could phrase it in one variable. – Milo Brandt 11 hours ago
8  
Is something missing in the question? Using Semiclassical's answer I know where $51$ comes from, but it's easy to get a negative value for $M$? I assume the "least possible positive value" is meant? – SteamyRoot 11 hours ago
    
@steamyroot yes, its positive sorry. – ItsImpulse 10 hours ago
    
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 2 hours ago
up vote 19 down vote accepted

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

share|cite|improve this answer
    
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 10 hours ago
    
Think about what value $\sum a_i$ can take, given the limited possibilities of $a_i$. – hardmath 10 hours ago
    
@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 10 hours ago
1  
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 10 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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