Η Ανισότητα Ανακατάταξης (Rearrangement Inequality)

Η Ανισότητα Ανακατάταξης (Rearrangement Inequality) αποδεικνύει ότι, για δύο μη φθίνουσες ακολουθίες, το άθροισμα των γινομένων είναι μέγιστο όταν ταιριάζουν “σε σειρά” και ελάχιστο όταν ταιριάζουν αντίστροφα.

Διατύπωση

Αν

$$x_1\le x_2\le \cdots \le x_{\mathrm{n}}$$

και

$$y_1 \leq y_2 \leq \cdots \leq y_n$$

τότε για οποιαδήποτε μετάθεση $\sigma$:

$$x_1{y}_1+x_2{y}_2+\cdots +x_n{y}_n\ge x_1{y}_{\sigma (1)}+x_2{y}_{\sigma (2)}+\cdots +x_n{y}_{\sigma (n)}\ge x_1{y}_n+x_2{y}_{n-1}+\cdots +x_n{y}_1\mathrm{.}$$

Με άλλα λόγια:

• Μέγιστο άθροισμα → όταν τα στοιχεία είναι τοποθετημένα στην ίδια σειρά.

• Ελάχιστο άθροισμα → όταν είναι τοποθετημένα σε αντίθετη σειρά.

Εφαρμογές

• Ανισότητα του Chebyshev: Από την ανακατάταξη προκύπτει

$$\frac{1}{n}\sum a_i{b}_i\ge (\frac{1}{n}\sum a_i)(\frac{1}{n}\sum b_i)$$

όταν οι ακολουθίες έχουν την ίδια διάταξη.

• AM–GM: Μπορεί να αποδειχθεί με ανακατάταξη όρων και τετραγώνων.

• Ανισότητα Nesbitt: Εφαρμόζεται ως ειδική περίπτωση.

Γεωμετρική ερμηνεία

Φανταστείτε έναν πίνακα $n\times n$ με τα γινόμενα όλων των $x_i y_j$. Το μέγιστο άθροισμα λαμβάνεται όταν επιλέγετε τα στοιχεία της κύριας διαγωνίου, το ελάχιστο όταν επιλέγετε την “αντίθετη” διαγώνιο.

Σκέψη για την απόδειξη

1. Απόδειξη με ανταλλαγή: Αν δεν είναι σωστά διατεταγμένα, μπορείς να ανταλλάξετε δύο όρους και να αυξήσεις το άθροισμα.

2. Επαγωγή: Δείξτε για $n=2$ και επεκτείνετε σε μεγαλύτερα $n$.

Γενικεύσεις

• Σε περισσότερες από δύο ακολουθίες.

• Σε ολοκληρωτικές εκδοχές (Riesz, Hardy–Littlewood).

• Σε γενικευμένες μορφές λογικής (T-norms).

Πηγές

• Wikipedia – Rearrangement Inequality
• Cut-the-Knot – Rearrangement Inequality
• Wolfram MathWorld – Rearrangement Inequality
• Hardy, Littlewood & Pólya, Inequalities, Cambridge University, Θεώρημα 368
• arXiv – Generalizations for many sequences