Omarrangemang ojämlikhet

I matematik anger omarrangemanget ojämlikhet det

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}

för varje val av reella tal

x_{1}\leq \cdots \leq x_{n}\quad {\text{ och }}\quad y_{1}\leq \ cdots \leq y_{n}

och varje permutation

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

av

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

Om siffrorna är olika, vilket betyder att

x_{1}<\cdots <x_{n}\quad {\text{ och }}\quad y_{1}<\cdots < y_{n},

då uppnås den nedre gränsen endast för permutationen som vänder ordningen, det vill säga $\sigma (i)=n-i+1$ för alla $i=1,\ldots ,n,$ och den övre gränsen uppnås endast för identiteten, det vill säga $\sigma (i)=i$ för alla $i=1,\ldots ,n.$

Observera att omarrangeringsojämlikheten inte gör några antaganden om de reella talens tecken.

Ansökningar

Många viktiga ojämlikheter kan bevisas genom omarrangemang av ojämlikhet, såsom det aritmetiska medelvärdet – geometrisk medelolikhet , Cauchy -Schwarz-ojämlikheten och Chebyshevs summaolikhet .

En speciell konsekvens är att om $x_{1}\leq \cdots \leq x_{n}$ så (genom att använda $y_{i }:=x_{i}{\text{ för alla }}i$ ): ${\displaystyle x_{1}x_{n}+\cdots +x_{n}x_{1}\;\leq \;x_{1}x_{\sigma (1)}+ \cdots +x_{n}x_{\sigma (n)}\;\leq \;x_{1}^{2}+\cdots +x_{n}^{2}} gäller för varje permutation$ σ { $displaystyle \sigma }$ av $1,\ldots ,n.$

Intuition

Omarrangeringsojämlikheten är faktiskt väldigt intuitiv. Föreställ dig att det finns en hög med $10-sedlar, en hög med $20-sedlar och ytterligare en hög med $100-sedlar. Du får ta 7 sedlar från en valfri hög och sedan försvinner högen. I den andra omgången får du ta 5 sedlar från en annan hög och högen försvinner. I den sista omgången får du ta 3 sedlar från den sista högen. I vilken ordning vill du välja högarna för att maximera din vinst? Självklart är det bästa du kan göra att få $7\cdot 100+5\cdot 20+3\cdot 10$ dollar. Detta är exakt vad omarrangeringsolikhet säger för sekvenserna $10<20<100$ och $3<5<7.$ Det är också en tillämpning av en girig algoritm .

Bevis

Den nedre gränsen följer genom att tillämpa den övre gränsen på

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

Därför räcker det att bevisa den övre gränsen. Eftersom det bara finns ändligt många permutationer, finns det åtminstone en för vilken

x_{\sigma (1)}y_{1}+\cdots +x_{\sigma (n)}y_{n}

är maximal. Om det finns flera permutationer med denna egenskap, låt σ beteckna en med det högsta antalet fixpunkter .

Vi ska nu motsägelsevis bevisa att σ måste vara identiteten (då är vi klara). Antag att σ inte är identiteten. Då finns det ett j i {1, ..., n − 1} så att σ( j ) ≠ j och σ( i ) = i för alla i i {1, ..., j − 1}. Därav σ( j ) > j och det finns ett k i { j + 1, ..., n } med σ( k ) = j . Nu

j<k\Rightarrow y_{j}\leq y_{k}\qquad {\text{and}}\qquad j<\sigma (j)\Rightarrow x_{j}\leq x_{\ sigma (j)}.\quad (1)

Därför,

0\leq \left(x_{\sigma (j)}-x_{j}\right)\left(y_{k}-y_{j}\right).\quad (2)

Att utöka denna produkt och arrangera om ger

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

därav permutationen

\tau (i):={\begin{cases}i&{\text{för }}i\in \{1,\ldots ,j\},\\\sigma (j)&{\text{för }}i=k,\\\sigma (i)&{\text{för }}i\in \{j+1,\ldots ,n\}\setminus \{k\},\end{cases}}

som uppstår från σ genom att byta ut värdena σ( j ) och σ( k ), har åtminstone en ytterligare fixpunkt jämfört med σ, nämligen vid j , och uppnår även maximum. Detta motsäger valet av σ.

Om

x_{1}<\cdots <x_{n}\quad {\text{ och }}\quad y_{1}<\cdots < y_{n},

då har vi strikta ojämlikheter vid (1), (2) och (3), därav kan maximum endast uppnås av identiteten, vilken annan permutation σ som helst kan inte vara optimal.

Bevis genom induktion

Observera först det

x_{1}>x_{2}\quad {\text{ och }}\quad y_{1}>y_{2}

innebär

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

därför är resultatet sant om n = 2. Antag att det är sant vid rang n-1 , och låt

x_{1}>\cdots >x_{n},\quad {\text{ och }}\quad y_{1}>\cdots >y_{n}.

Välj en permutation σ för vilken arrangemanget ger ett maximalt resultat.

Om σ( n ) skilde sig från n , säg σ( n ) = k , skulle det finnas j < n så att σ( j ) = n . Men

x_{k}>x_{n}\quad {\text{ och}}\quad y_{j}>y_{n},\quad {\text{därav}}\quad x_{n}y_{n}+x_{k}y_{j}>x_{k}y_{ n}+x_{n}y_{j}

av det som just har bevisats. Följaktligen skulle det följa att permutationen τ som sammanfaller med σ, förutom vid j och n , där τ( j ) = k och τ( n ) = n , ger ett bättre resultat. Detta motsäger valet av σ. Därför σ( n ) = n , och från induktionshypotesen , σ( i ) = i för varje i < n .

Samma bevis gäller om man ersätter strikta ojämlikheter med icke strikta.

Generaliseringar

En enkel generalisering tar hänsyn till fler sekvenser. Antag att vi har ordnade sekvenser av positiva reella tal

x_{n}\geq \cdots \geq x_{1}\geq x_{1}\ge text{and}}\quad y_{n}\geq \cdots \geq y_{1}\geq 0\quad {\text{and}}\quad z_{n}\geq \cdots \geq z_{1}\ geq 0

och en permutation

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

av

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

och en annan permutation

y_{\tau (1)},\dots ,y_{\tau ( n)}

av

y_{1},\dots ,y_{n}

. Då håller det

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

Observera att till skillnad från den vanliga omarrangeringsojämlikheten kräver detta uttalande att siffrorna är icke-negativa. Ett liknande uttalande gäller för alla antal sekvenser med alla tal icke-negativa.

En annan generalisering av omarrangeringsolikheten säger att för alla reella tal $x_{1}\leq \cdots \leq x_{n}$ $f_{i}:[x_{1},x_{n}]\högerpil \mathbb {R} ,i=1,2,\ldots , n$ alla val av funktioner så att derivatorna $f'_{i}$ uppfyller: