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!!


  • 1
    $\begingroup$ That looks a lot like cross terms in $(a_1+a_2+\cdots a_{95})^2 $\endgroup$ Feb 24, 2022 at 16:42
  • 3
    $\begingroup$ 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. $\endgroup$ Feb 24, 2022 at 16:47
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 24, 2022 at 17:08
  • 2
    $\begingroup$ Hint: this equals to $\binom{95}2-2t(95-t)$ where $t$ is the number of $1$s $\endgroup$
    – JetfiRex
    Feb 24, 2022 at 17:09
  • $\begingroup$ Thanks for the help everyone!! I really appreciate it! $\endgroup$ Feb 24, 2022 at 17:12


You must log in to answer this question.

Browse other questions tagged .