# Minimize $\displaystyle\sum_{1 \le i < j \le 95} a_i a_j$.

Each of the numbers $$a_1,$$ $$a_2,$$ $$\dots,$$ $$a_{95}$$ is $$\pm 1.$$ Find the smallest possible positive value of $$\sum_{1 \le i < j \le 95} a_i a_j.$$

My guess is that the answer should be $$1$$, but I'm not sure if this can happen, and I'm also not sure how you can prove it. I would greatly appreciate any help!!

Thanks!!

• That looks a lot like cross terms in $(a_1+a_2+\cdots a_{95})^2 Feb 24, 2022 at 16:42 • Indeed,$\sum_{1 \le i < j \le 95} a_i a_j = \frac12\big( \sum_{1\le k\le 95} a_k \big)^2 - \frac12\sum_{1\le k\le 95} a_k^2$makes the problem much more transparent. Feb 24, 2022 at 16:47 • The order of the$a_i$doesn't matter since you have all possible pairwise products of them. So a possible approach is: (1) Say$k$terms are equal to$+1$and$95-k$terms are equal to$-1$; what's the sum, as a function of$k$? (2) Find the integer$k$for which this is smallest but still positive. Feb 24, 2022 at 17:08 • Hint: this equals to$\binom{95}2-2t(95-t)$where$t$is the number of$1\$s Feb 24, 2022 at 17:09
• Thanks for the help everyone!! I really appreciate it! Feb 24, 2022 at 17:12