IMO 2019 Shortlisted Problems

Define sets $B$ and $C$ by $$\begin{array}{rl}& B=\{(i,j)\left|1⩽i,j⩽n,\left|a_i-a_j\right|⩾1\right\},\\ & C=\{(i,j)\left|1⩽i,j⩽n,\left|a_i-a_j\right|<1\right\}.\end{array}$$ We have $$\begin{array}{rl}\sum _{(i,j)\in A}{a}_i{a}_j& =\frac{1}{2}\sum _{(i,j)\in B}{a}_i{a}_j\\ \sum _{(i,j)\in B}{a}_i{a}_j& =\sum _{1⩽i,j⩽n}{a}_i{a}_j-\sum _{(i,j)\notin B}{a}_i{a}_j=0-\sum _{(i,j)\in C}{a}_i{a}_j.\end{array}$$ So it suffices to show that if $A$ (and hence $B$) are nonempty, then $$\sum _{(i,j)\in C}{a}_i{a}_j>0.$$ Partition the indices into sets $P,Q,R$, and $S$ such that $$\begin{array}{ll}P=\left\{i\mid a_i⩽-1\right\}& R=\left\{i\mid 0<a_i<1\right\}\\ Q=\left\{i\mid -1<a_i⩽0\right\}& S=\left\{i\mid 1⩽a_i\right\}.\end{array}$$ Then $$\sum _{(i,j)\in C}{a}_i{a}_j⩾\sum _{i\in P\cup S}{a}_i^2+\sum _{i,j\in Q\cup R}{a}_i{a}_j=\sum _{i\in P\cup S}{a}_i^2+{\left(\sum _{i\in Q\cup R}{a}_i\right)}^2⩾0.$$ The first inequality holds because all of the positive terms in the RHS are also in the LHS, and all of the negative terms in the LHS are also in the RHS. The first inequality attains equality only if both sides have the same negative terms, which implies $\left|a_i-a_j\right|<1$ whenever $i,j\in Q\cup R$; the second inequality attains equality only if $P=S=\varnothing$. But then we would have $A=\varnothing$. So $A$ nonempty implies that the inequality holds strictly, as required.

---

Alternative solution.

Consider $P,Q,R,S$ as in Solution 1, set $$p=\sum _{i\in P}{a}_i,q=\sum _{i\in Q}{a}_i,r=\sum _{i\in R}{a}_i,s=\sum _{i\in S}{a}_i,$$ and let $$t_{+}=\sum _{(i,j)\in A,a_i{a}_j⩾0}{a}_i{a}_j,t_{-}=\sum _{(i,j)\in A,a_i{a}_j⩽0}{a}_i{a}_j.$$ We know that $p+q+r+s=0$, and we need to prove that $t_{+}+t_{-}<0$. Notice that $t_{+}⩽p^2/2+pq+rs+s^2/2$ (with equality only if $p=s=0$), and $t_{-}⩽pr+ps+qs$ (with equality only if there do not exist $i\in Q$ and $j\in R$ with $a_j-a_i>1$). Therefore, $$t_{+}+t_{-}⩽\frac{p^2+s^2}{2}+pq+rs+pr+ps+qs=\frac{(p+q+r+s{)}^2}{2}-\frac{(q+r{)}^2}{2}=-\frac{(q+r{)}^2}{2}⩽0$$ If $A$ is not empty and $p=s=0$, then there must exist $i\in Q,j\in R$ with $\left|a_i-a_j\right|>1$, and hence the earlier equality conditions cannot both occur.