Nierówność przegrupowania

W matematyce mówi o tym nierówność przegrupowania

{\ Displaystyle x_ {n} y_ { 1}+\cdots +x_{1}y_{n}\równoważnik x_{\sigma (1)}y_{1}+\cdots +x_{\sigma (n)}y_{n}\równoważnik x_{1} y_{1}+\cdots +x_{n}y_{n}}

dla każdego wyboru liczb rzeczywistych

{\ Displaystyle x_ {1} \ równoważnik \ cdots \ równoważnik x_ {n} \ quad {\ tekst {i}} \ quad y_ {1} \ równoważnik \ cdots \równik y_{n}}

i każdą permutację

{\ Displaystyle x _ {\ sigma (1)} \ ldots, x _ {\ sigma (n)}}

z

{\ Displaystyle x_ {1}, \ ldots, x_ {n}.}

Jeśli liczby są różne, oznacza to, że

{\ Displaystyle x_ {1}<\ cdots <x_ {n} \ quad {\ tekst {i}} \ quad y_ {1}<\ cdots < y_{n},}

wtedy dolna granica jest osiągana tylko dla permutacji, która odwraca kolejność, to znaczy dla wszystkich ${\ Displaystyle i = 1, \ ldots, n,}$ $+ 1}$ a górna granica jest osiągana tylko dla tożsamości, to znaczy dla wszystkich ${\ Displaystyle i = 1, \ ldots, rz.}$ ${\ Displaystyle \ sigma (i) = i}$

Zauważ, że nierówność przegrupowania nie przyjmuje żadnych założeń dotyczących znaków liczb rzeczywistych.

Aplikacje

Za pomocą nierówności przegrupowania można udowodnić wiele ważnych nierówności, takich jak nierówność średnia arytmetyczna - średnia geometryczna , nierówność Cauchy'ego – Schwarza i nierówność sumy Czebyszewa .

$,$ że jeśli wtedy $}:=x_{i}{\text{dla wszystkich }}i}$ używając $y_$ ): ${\ Displaystyle x_ {1} x_ {n} + \ cdots + x_ {n} x_ {1} \; \ równoważnik \; x_ {1} x_ {\sigma (1)}+\cdots +x_{n}x_{\sigma (n)}\;\leq \;x_{1}^{2}+\cdots +x_{n}^{2}}$ obowiązuje dla każdej permutacji 1 ${\ Displaystyle 1, \ kropki, n.}$ $\ displaystyle \ sigma}$

Intuicja

Nierówność przegrupowania jest właściwie bardzo intuicyjna. Wyobraź sobie, że jest stos banknotów 10-dolarowych, stos banknotów 20-dolarowych i jeszcze jeden stos banknotów 100-dolarowych. Możesz wziąć 7 rachunków z wybranego stosu, a następnie stos znika. W drugiej rundzie możesz wziąć 5 banknotów z innego stosu, a stos znika. W ostatniej rundzie możesz wziąć 3 banknoty z ostatniego stosu. W jakiej kolejności chcesz wybierać stosy, aby zmaksymalizować swój zysk? Oczywiście najlepsze, co możesz zrobić, to zyskać ${\ Displaystyle 7 \ cdot 100 + 5 \ cdot 20 + 3 \ cdot 10}$ dolarów. Dokładnie to $< 5$ nierówność przegrupowania dla sekwencji $.}$ 5 < również zastosowanie algorytmu zachłannego .

Dowód

Dolna granica następuje po zastosowaniu górnej granicy do

{\ Displaystyle -x_ {n} \ równoważnik \ cdots \ równoważnik -x_ {1}.}

Dlatego wystarczy udowodnić górną granicę. Ponieważ istnieje tylko skończenie wiele permutacji, istnieje co najmniej jedna dla której

{\ Displaystyle x _ {\ sigma (1)} y_ {1} + \ cdots + x _ {\ sigma (n)} y_ {n}}

jest maksymalny. W przypadku kilku permutacji o tej własności niech σ oznacza permutację z największą liczbą punktów stałych .

Udowodnimy teraz przez sprzeczność , że σ musi być tożsamością (to koniec). Załóżmy, że σ nie jest tożsamością. Wtedy istnieje j w {1, ..., n - 1} takie, że σ ( j ) ≠ j oraz σ ( i ) = i dla wszystkich i w {1, ..., j - 1}. Stąd σ( j ) > j i istnieje k w { j + 1, ..., n } gdzie σ ( k ) = j . Teraz

{\ Displaystyle j <k \ Strzałka w prawo y_ {j} \ równoważnik y_ {k} \ qquad {\ tekst {i}} \ qquad j <\ sigma (j) \ Strzałka w prawo x_ {j} \ równoważnik x_ {\ sigma (j)}.\quad (1)}

Dlatego,

{\ Displaystyle 0 \ równoważnik \ lewo (x _ {\ sigma (j)} -x_ {j} \ prawej) \ lewo (y_ {k} -y_ {j} \ prawej). \ quad (2)}

Rozbudowa tego produktu i przearanżowanie daje

{\ Displaystyle x _ {\ sigma (j)} y_ {j} + x_ {j} y_ {k}\leq x_{j}y_{j}+x_{\sigma (j)}y_{k}\,,\quad (3)}

stąd permutacja

{\ Displaystyle \ tau (i): = {\ rozpocząć {przypadki} i & {\ tekst {dla}} i \ w \ {1, \ ldots, j \}, \\\ sigma (j) i {\ tekst { for }}i=k,\\\sigma (i)&{\text{for }}i\in \{j+1,\ldots ,n\}\setminus \{k\},\end{przypadki} }}

która wynika z σ przez zamianę wartości σ( j ) i σ( k ), ma co najmniej jeden dodatkowy punkt stały w stosunku do σ, mianowicie w j , i również osiąga maksimum. Jest to sprzeczne z wyborem σ.

Jeśli

{\ Displaystyle x_ {1}<\ cdots <x_ {n} \ quad {\ tekst {i}} \ quad y_ {1}<\ cdots < y_{n},}

wtedy mamy ścisłe nierówności w (1), (2) i (3), stąd maksimum można osiągnąć tylko przez tożsamość, każda inna permutacja σ nie może być optymalna.

Dowód przez indukcję

Zauważ najpierw to

{\ Displaystyle x_ {1}> x_ {2} \ quad {\ tekst {i}} \ quad y_ {1}> y_ {2}}

implikuje

{\ Displaystyle \ lewo (x_ {1} -x_ {2 }\right)\left(y_{1}-y_{2}\right)>0\quad {\text{lub }}\quad x_{1}y_{1}+x_{2}y_{2}> x_{2}y_{1}+x_{1}y_{2},}

stąd wynik jest prawdziwy, jeśli n = 2. Załóżmy, że jest prawdziwy na randze n-1 i niech

{\ Displaystyle x_ {1}> \ cdots > x_ {n}, \ quad {\ tekst {i}} \ quad y_ {1}> \ cdots > y_ {n}.}

Wybierz permutację σ, dla której układ daje maksymalny wynik.

Gdyby σ( n ) były różne od n , powiedzmy σ ( n ) = k , istniałoby j < n takie , że σ ( j ) = n . Ale

{\ Displaystyle x_ {k}> x_ {n} \ quad {\ tekst { i}}\quad y_{j}>y_{n},\quad {\text{stąd}}\quad x_{n}y_{n}+x_{k}y_{j}>x_{k}y_{ n}+x_{n}y_{j}}

przez to, co właśnie zostało udowodnione. W konsekwencji wynikałoby z tego, że permutacja τ pokrywająca się z σ, z wyjątkiem j i n , gdzie τ( j ) = k i τ( n ) = n , daje lepszy wynik. Jest to sprzeczne z wyborem σ. Stąd σ( n ) = n , az hipotezy indukcyjnej σ ( i ) = i dla każdego i < n .

Ten sam dowód zachodzi, jeśli zastąpimy ścisłe nierówności nierównościami nieścisłymi.

Uogólnienia

Proste uogólnienie uwzględnia więcej sekwencji. Załóżmy, że mamy uporządkowane ciągi dodatnich liczb rzeczywistych

{\ Displaystyle x_ {n} \ geq \ cdots \ geq x_ {1} \ geq 0 \ quad {\ tekst{i}}\quad y_{n}\geq \cdots \geq y_{1}\geq 0\quad {\text{i}}\quad z_{n}\geq \cdots \geq z_{1}\ geq 0}

i permutacja

{\ Displaystyle x _ {\ sigma (1)} \ kropki, x _ {\ sigma (n)}}

\ displaystyle x_ {1}, \ kropki, x_ {n}}

1 i inna permutacja

{\ Displaystyle y_ {\ tau (1)}, \ kropki, y_ {\ tau ( n)}}

z

{\ Displaystyle y_ {1}, \ kropki, y_ {n}}

. Wtedy trzyma

{\ Displaystyle x_ {n} y_ {n} z_ {n} + \ ldots + x_ {1} y_ {1} z_ {1} \ geq x_ {\ sigma (n)} y_ {\ tau (n)} z_ {n}+\ldots +x_{\sigma (1)}y_{\tau (1)}z_{1}.}

Zauważ, że w przeciwieństwie do powszechnej nierówności przegrupowania, to stwierdzenie wymaga, aby liczby były nieujemne. Podobne stwierdzenie jest prawdziwe dla dowolnej liczby sekwencji, w których wszystkie liczby są nieujemne.

${\ Displaystyle f_ {i}: [x_ {1}, x_ {n}] \ rightarrow \ mathbb {R}, i = 1,2, \ ldots, N}$ $wszystkich$ nierówności przegrupowania stwierdza, że liczb funkcji takie, że pochodne spełniają: ${\ displaystyle f'_ {i}}$