Rendezési egyenlőtlenség

A Wikipédiából, a szabad enciklopédiából

A rendezési egyenlőtlenség (más néven rendezési tétel) azt mondja ki, miszerint

x_ny_1 + \cdots + x_1y_n
\le x_{\sigma (1)}y_1 + \cdots + x_{\sigma (n)}y_n
\le x_1y_1 + \cdots + x_ny_n

minden

x_1\le\cdots\le x_n\quad\text{és}\quad y_1\le\cdots\le y_n

esetén, minden

x_{\sigma(1)},\dots,x_{\sigma(n)}\,

permutációra.

Amennyiben a feltételek x-re és y-ra szigorúak, azon esetben az egyenlőtlenség:

x_ny_1 + \cdots + x_1y_n
< x_{\sigma (1)}y_1 + \cdots + x_{\sigma (n)}y_n
< x_1y_1 + \cdots + x_ny_n

Felhasználások[szerkesztés | forrásszöveg szerkesztése]

Számos egyenlőtlenség bizonyítható a rendezési tétel felhasználásával, például a Számtani és mértani közép közötti egyenlőtlenség, Cauchy–Bunyakovszkij–Schwarz-egyenlőtlenség és a Csebisev-összegegyenlőtlenség.

Bizonyítás[szerkesztés | forrásszöveg szerkesztése]

A rendezési egyenlőtlenség bizonyítható indirekt módon: n=2-re: (a2-a1)(b2-b1)\ge0. Kibontás és átrendezés után éppen a kívánt egyenlőtlenség jön ki. Ezután tegyük fel, hogy a legnagyobb értéket nem akkor veszi fel az összeg, amikor minden i-re ai és bi van párosítva. Ekkor van legalább egy olyan ai - bj és ak - bl párosítás, ahol i<j és k>l. Ekkor azonban az n=2-re használt módszerrel látható, hogy az érték nem csökken, amennyiben az i - l és k - j párokat vesszük, amely azonban ellentmond annak, miszerint van nagyobb . A minimális tag is hasonló módon bizonyítható.

Források[szerkesztés | forrásszöveg szerkesztése]

  • Ez a szócikk részben vagy egészben a Rearrangement inequality című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel.
  • AOPSWiki