Nerovnost přeskupení - Rearrangement inequality

v matematika, přeskupení nerovnost^[1] tvrdí, že

{ displaystyle x_ {n} y_ {1} + cdots + x_ {1} y_ {n} leq x _ { sigma (1)} y_ {1} + cdots + x _ { sigma (n)} y_ {n} leq x_ {1} y_ {1} + cdots + x_ {n} y_ {n}}

pro každou volbu reálná čísla

{ displaystyle x_ {1} leq cdots leq x_ {n} quad { text {a}} quad y_ {1} leq cdots leq y_ {n}}

a každý permutace

{ displaystyle x _ { sigma (1)}, tečky, x _ { sigma (n)}}

z X₁, . . ., X_n.

Pokud jsou čísla různá, znamená to

{ displaystyle x_ {1} < cdots

pak je dolní hranice dosažena pouze pro permutaci, která obrátí pořadí, tj. σ (i) = n − i + 1 pro všechny i = 1, ..., n, a horní hranice je dosažena pouze pro identitu, tj. σ (i) = i pro všechny i = 1, ..., n.

Všimněte si, že nerovnost přeskupení nedává žádné předpoklady o znameních reálných čísel.

Aplikace

Mnoho důležitých nerovností lze dokázat přeskupením nerovností, například aritmetický průměr - nerovnost geometrického průměru, Cauchy – Schwarzova nerovnost, a Čebyševova nerovnost součtu.

Důkaz

Dolní mez následuje použitím horní meze na

{ displaystyle -x_ {n} leq cdots leq -x_ {1}.}

Proto stačí prokázat horní hranici. Protože existuje jen definitivně mnoho permutací, existuje alespoň jedna pro kterou

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

je maximální. V případě, že s touto vlastností existuje několik permutací, označme σ jednu s nejvyšším počtem pevné body.

Teď budeme prokázat rozporem, že σ musí být identita (pak jsme hotovi). Předpokládejme, že σ je ne identita. Pak existuje a j v 1, ...,n - 1} takové, že σ (j) ≠ j a σ (i) = i pro všechny i v 1, ...,j - 1} Proto σ (j) > j a existuje a k v {j + 1, ..., n} s σ (j) = k. Nyní

{ displaystyle j

Proto,

{ displaystyle 0 leq (x _ { sigma (j)} - x_ {j}) (y_ {k} -y_ {j}). quad (2)}

Rozšíření tohoto produktu a přeskupení dává

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

tedy obměna

{ displaystyle tau (i): = { begin {cases} i & { text {for}} i in {1, ldots, j }, sigma (j) & { text { for}} i = k, sigma (i) & { text {for}} i in {j + 1, ldots, n } setminus {k }, end {cases} }}

který vzniká z σ výměnou hodnot σ (j) a σ (k), má ve srovnání s σ alespoň jeden další pevný bod, konkrétně v j, a také dosahuje maxima. To je v rozporu s volbou σ.

Li

{ displaystyle x_ {1} < cdots

pak máme přísné nerovnosti na (1), (2) a (3), proto maximum lze dosáhnout pouze identitou, jakákoli jiná permutace σ nemůže být optimální.

Důkaz indukcí

Nejprve si to všimněte

{ displaystyle x_ {1}> x_ {2} quad { text {a}} quad y_ {1}> y_ {2}}

naznačuje

{ displaystyle (x_ {1} -x_ {2}) (y_ {1} -y_ {2})> 0 quad { text {nebo}} quad x_ {1} y_ {1} + x_ {2 } y_ {2}> x_ {2} y_ {1} + x_ {1} y_ {2},}

proto je výsledek pravdivý, pokud n = 2. Předpokládejme, že to platí na hodnosti n-1a nechte

{ displaystyle x_ {1}> cdots> x_ {n}, quad { text {a}} quad y_ {1}> cdots> y_ {n}}

.

Vyberte permutaci σ, pro kterou uspořádání vede k maximálnímu výsledku.

Pokud σ (n) se lišily od n, řekněme σ (n) = k, existovalo by j < n takové, že σ (j) = n. Ale

{ displaystyle x_ {k}> x_ {n} quad { text {a}} quad y_ {j}> y_ {n}, quad { text {proto}} quad x_ {n} y_ { n} + x_ {k} y_ {j}> x_ {k} y_ {n} + x_ {n} y_ {j}}

tím, co bylo právě prokázáno. Z toho by vyplývalo, že permutace τ se shoduje s σ, kromě j a n, kde τ (j) = k a τ (n) = n, dává lepší výsledek. To je v rozporu s volbou σ. Proto σ (n) = n, a z indukční hypotézy, σ (i) = i pro každého i < n.

Stejný důkaz platí, pokud nahradíme přísné nerovnosti nerovnostmi.

Zobecnění

Zevšeobecnění nerovnosti přesmyku říká, že pro všechny reálná čísla ${ displaystyle x_ {1} leq cdots leq x_ {n}}$ a jakýkoli výběr funkcí ${ displaystyle f_ {i}: [x_ {1}, x_ {n}] rightarrow mathbb {R}, i = 1,2, ..., n}$ takhle