Rendezési egyenlőtlenség

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

$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}$

minden

$x_{1}\leq \cdots \leq x_{n}\quad {\text{és}}\quad y_{1}\leq \cdots \leq 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_{n}y_{1}+\cdots +x_{1}y_{n}<x_{\sigma (1)}y_{1}+\cdots +x_{\sigma (n)}y_{n}<x_{1}y_{1}+\cdots +x_{n}y_{n}$

Felhasználások

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

A rendezési egyenlőtlenség bizonyítható indirekt módon: n=2-re: (a₂-a₁)(b₂-b₁)$\geq$0. 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 a_i és b_i van párosítva. Ekkor van legalább egy olyan a_i – b_j és a_k – b_l 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ó.

Fordítás

• 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. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Források

• AOPSWiki