Question

Let $a_1,\dots ,a_n$, not all equal to 0 , be such that $\sum _{i=1}^n{a}_i=0$. Show that there is a permutation $i_1,\dots ,i_n$such that $\sum _{j=1}^n{a}_{ij}{a}_{ij+1}<0$.
Hint: Use the probabilistic method. (It is interesting that there need not be a permutation whose sum of products of successive pairs is positive. For instance, if $n=3$, $a_1=a_2=-1$, and $a_3=2$, there is no such permutation.)

Short answer

$\sum _{j=1}^{n-1}{a}_{ij}{a}_{ij+1}<0$

Step-by-step solution

:Concept Introduction

The question asks to show that there is a permutation $i_1,\dots ,i_n$such that $\sum _{j=1}^n{a}_{i,}{a}_{i,+1}<0$where $a_1,\dots ,a_n$are not all equal to $0$and $\sum _{i=1}^n{a}_i=0$.

Explanation

The question asks to show that there is a permutation $i_1,\dots ,i_n$such that $\sum _{j=1}^n{a}_{i,j}{a}_{i,+1}<0$where $a_1,\dots ,a_n$are not all equal to $0$and $\sum _{i=1}^n{a}_i=0$

Explanation

Let $I_1,\dots ,I_n$be a random permutation that is equally likely to be any of the $n$ ! Permutations Then:
$E\left[a_{l_j}{a}_{l_{j+1}}\right]=\sum _{k}E\left[a_{l_j}{a}_{l_{j+1}}\mid I_j=k\right]P\left\{I_j=k\right\}$

Explanation

$=\frac{1}{n}\sum _k{a}_k·E\left[a_{l_{j+1}}\mid I_j=k\right]$
$=\frac{1}{n}\sum _k{a}_k·\sum _i{a}_i·P\left\{I_{j+1}=i\mid I_j=k\right\}$

Explanation

$=\frac{1}{n·(n-1)}\sum _k{a}_k\sum _{i=k}{a}_i$
$=\frac{1}{n·(n-1)}\sum _k{a}_k\left(-a_k\right)$

Explanation

Where the final equality followed from the assumption that $\sum _{i=1}^n{a}_i=0$. Since the preceding shows that
$E\left[\sum _{j=1}^{n-1}{a}_{l_j}{a}_{l_{j+1}}\right]<0$

Final Answer

Therefore, one can conclude that there must be some permutation $i_1,\dots ,i_n$for which
$$$\sum _{j=1}^{n-1}{a}_{ij}{a}_{ij+1}<0$