Let $a_1, a_2,...,a_{2018}$ be a sequence of numbers such that all its elements are elements of a set $\{-1,1\}$. Sum $$S=\sum \limits_{1 \leq i < j \leq 2018} a_i a_j$$can be negative and can also be positive. Find the minimal value of this sum
Problem
Source: Regional Olympiad - Federation of Bosnia and Herzegovina 2018
Tags: Sum, Sequence, algebra
06.12.2018 19:37
Because the sum is symetric in every variable $a_i$ suppose $a_1=...=a_k=-1\wedge a_{k+1}=...=a_n=1$ where $k\in\lbrace 0,1,...,n\rbrace$ Then the sum is equal to ${k\choose 2}\cdot (-1)^2+{n-k\choose 2}\cdot 1^2+k(n-k)\cdot (-1)\cdot 1=\frac{3k^2-4nk+n^2-n}{2}$. Now treat it as a quadratic function in $k$. The minimum is attained iff $k$ is equal to $\lfloor 2n/3\rfloor$ if $2n/3-\lfloor 2n/3\rfloor\in[0;\frac{1}{2}]$ and equal to $\lfloor 2n/3\rfloor+1$ otherwise
06.12.2018 20:55
The same as above, simply observe that, the given sum is $\sum_{1\leq i<j\leq n}a_ia_j = \sum_{(i,j):a_i\neq a_j}(-1)+\sum_{(i,j):a_i=a_j}(1)$. Now, let $k=\{\ell:a_\ell=-1\}$. This sum is nothing but, $\binom{k}{2}+\binom{n-k}{2}-k(n-k)$, which is the quadratic above, and can be solved easily. An interesting fact is that, this problem becomes highly non-trivial, is we consider a weighted sum, say, $\sum_{1\leq i <j\leq n}g_{ij}a_ia_j$, where, $g_{ij}$'s are weights (a typical instance is where $g_{ij}$'s are samples from a Gaussian distribution).
07.12.2018 05:46
$S=\sum \limits_{1 \leq i < j \leq 2018} a_i a_j = \frac{1}{2} ((\sum_{i=1}^{2018} a_{i})^{2} - \sum_{i=1}^{2018} a_{i}^{2} ) = \frac{1}{2} ((\sum_{i=1}^{2018} a_{i})^{2} - 2018 ) = \frac{1}{2} ((\sum_{i=1}^{2018} a_{i})^{2}) - 1009 \geq -1009$ The inequality holds at 1009 of them are $1$ and the others are $-1$.
07.12.2018 23:17
I made a little mistake: it should look like ${k\choose 2}\cdot (-1)^2+{n-k\choose 2}\cdot 1^2+k(n-k)\cdot (-1)\cdot 1=\frac{4k^2-4nk+n^2-n}{2}=\frac{(n-2k)^2-n}{2}\ge - \frac{n}{2}$ So for $2|n$ the minimum is attained when $k=n/2$ and then $S=- \frac{n}{2}$ For $2|n+1$ the minimum is attained when $|n-2k|=1$ and equals to $- \frac{n-1}{2}$
28.10.2020 16:42
You can interpret this as Complete graph $K_{2018}$ as following: Color $K_{2018}$ with $2$ colors(black and white) and find the maximum number of black vertices connected to white vertices, since this is same as number of pairs with two different signs and more we have these pairs sum is getting smaller and smaller. Now let the number of black vertices be $a$ and number of white vertices be $b$. As every vertex is connected we have that number of black vertices connected to number of white vertices is $ab$ and we search for this maximum but since $a+b=2018$ by AM-GM we have that $1009\geq \sqrt{ab}$ or maximum of $ab=1009^2$ and this is achieved when $a=b=1009$. So to achieve minimum of $S$ we have $1009$ number of $1$ and $1009$ number of $-1$. Calculating this gives us that the desired minimum is $-1009$