Q7.21 - A First Course in Probability

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.)

Step-by-Step Solution

Answer

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

Step 1 :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$.

Step 2 : 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$

Step 3 : 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\}$

Step 4: 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\}$

Step 5: 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)$

Step 6: 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$

Step 7: 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$