Chapter 7: Q7.21 (page 365)

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_{i j} a_{i j + 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

Expert verified

$\sum_{j = 1}^{n - 1} a_{i j} a_{i j + 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 [a_{l_{j}} a_{l_{j + 1}}] = \sum_{k} E [a_{l_{j}} a_{l_{j + 1}} ∣ I_{j} = k] P \{I_{j} = k\}$

Explanation

$= \frac{1}{n} \sum_{k} a_{k} \cdot E [a_{l_{j + 1}} ∣ I_{j} = k]$
$= \frac{1}{n} \sum_{k} a_{k} \cdot \sum_{i} a_{i} \cdot P \{I_{j + 1} = i ∣ I_{j} = k\}$

Explanation

$= \frac{1}{n \cdot (n - 1)} \sum_{k} a_{k} \sum_{i = k} a_{i}$
$= \frac{1}{n \cdot (n - 1)} \sum_{k} a_{k} (- a_{k})$

Explanation

Where the final equality followed from the assumption that $\sum_{i = 1}^{n} a_{i} = 0$ . Since the preceding shows that
$E [\sum_{j = 1}^{n - 1} a_{l_{j}} a_{l_{j + 1}}] < 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_{i j} a_{i j + 1} < 0$

Unlock Step-by-Step Solutions & Ace Your Exams!

Full Textbook Solutions
Get detailed explanations and key concepts
Unlimited Al creation
Al flashcards, explanations, exams and more...
Ads-free access
To over 500 millions flashcards
Money-back guarantee
We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

Recommended explanations on Math Textbooks

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Short Answer

Step by step solution

:Concept Introduction

Explanation

Explanation

Explanation

Explanation

Explanation

Final Answer

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Math Textbooks

Decision Maths

Applied Mathematics

Probability and Statistics

Pure Maths

Geometry

Mechanics Maths

Study anywhere. Anytime. Across all devices.