nierówność o ciągach jednomonotonicznych

Zbiór wzorów, definicji i najczęściej poruszanych problemów z Podstaw matematyki
Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

nierówność o ciągach jednomonotonicznych

Post autor: Dumel »

O klasycznych nierównościach przydatnych na Olimpiadzie w kompendium sporo już jest, brakuje jednak informacji o pewnej szalenie elementarnej i dość przydatnej nierówności a mianowicie nierówności o ciągach jednomonotonicznych.

Dla liczb rzeczywistych \(\displaystyle{ a_1,a_2,...,a_n \ b_1,b_2,...,b_n}\) oznaczmy:
\(\displaystyle{ \left[\begin{array}{cccc}a_1&a_2&...&a_n\\b_1&b_2&...&b_n \end{array}\right]=a_1b_1+a_2b_2+\ldots+a_nb_n}\)

Twierdzenie:
dla dowolnych liczb rzeczywistych \(\displaystyle{ a_1 \ge a_2 \ge ... \ge a_n}\) oraz \(\displaystyle{ b_1 \ge b_2 \ge... \ge b_n}\) oraz dowolnej permutacji \(\displaystyle{ \sigma}\) ciągu \(\displaystyle{ (1,2,...,n)}\) zachodzi nierówność:
\(\displaystyle{ \left[\begin{array}{cccc}a_1&a_2&...&a_n\\b_1&b_2&...&b_n \end{array}\right] \ge \left[\begin{array}{cccc}a_1&a_2&...&a_n\\b_{\sigma(1)} & b_{\sigma(2)} &...& b_{\sigma(n)} \end{array}\right]}\)
Dowód:
dla \(\displaystyle{ a_1 \ge a_2}\) i \(\displaystyle{ b_1 \ge b_2}\) udowodnię nierówność
\(\displaystyle{ \left[\begin{array}{cc}a_1&a_2\\b_1&b_2 \end{array}\right] \ge \left[\begin{array}{cc}a_1&a_2\\b_2&b_1 \end{array}\right]}\)
jest ona równoważna nierówności:
\(\displaystyle{ 0 \le a_1b_1+a_2b_2-a_1b_2-a_2b_1=a_1(b_1-b_2)-a_2(b_1-b_2)=(a_1-a_2)(b_1-b_2)}\) oczywistej przez wzgląd na przyjęte założenia

Liczba inwersji w permutacji \(\displaystyle{ \tau_1=(b_{\sigma(1)}, b_{\sigma(2)},..., b_{\sigma(n)})}\) jest skończona. Jeśli liczba inwersji jest niezerowa, to istnieją indeksy \(\displaystyle{ i>j}\) spełniające \(\displaystyle{ b_{\sigma_{i}}<b_{\sigma_{j}}}\). Na mocy udowodnionej przed chwilą nierówności, składając \(\displaystyle{ \tau_1}\) z transpozycją \(\displaystyle{ (b_{\sigma_{i}},b_{\sigma_{j}})}\) otrzymamy nową permutację \(\displaystyle{ \tau_2=(b_{\sigma_2(1)}, b_{\sigma_2(2)},..., b_{\sigma_2(n)})}\) w której liczba inwersji jest mniejsza niż w \(\displaystyle{ \tau_1}\) oraz
\(\displaystyle{ \left[\begin{array}{cccc}a_1&a_2&...&a_n\\b_{\sigma_2(1)}&b_{\sigma_2(2)}&...&b_{\sigma_2(n)} \end{array}\right] \ge \left[\begin{array}{cccc}a_1&a_2&...&a_n\\b_{\sigma_1(1)} & b_{\sigma_1(2)} &...& b_{\sigma_1(n)} \end{array}\right]}\)
Powtarzając powyższe rozumowanie otrzymamy ciąg permutacji \(\displaystyle{ \tau_1,\tau_2,...,\tau_k}\) gdzie \(\displaystyle{ \tau_k=(b_1,b_2,...,b_n)}\) co kończy dowód.

Przykład zastosowania
przy pomocy powyższej nierówności udowodnimy
nierówność Nesbitt'a:
dla dowolnych liczb dodatnich \(\displaystyle{ a,b,c}\) zachodzi:
\(\displaystyle{ \frac{a}{b+c}+ \frac{b}{a+c}+ \frac{c}{a+b} \ge \frac{3}{2}}\)
Dowód:
ciągi \(\displaystyle{ (a,b,c)}\) oraz \(\displaystyle{ (\frac{1}{b+c}, \frac{1}{a+c}, \frac{1}{a+b})}\) są jednakowo uporządkowane, więc:
\(\displaystyle{ \left[\begin{array}{ccc}a&b&c\\ \frac{1}{b+c} & \frac{1}{a+c} & \frac{1}{a+b} \end{array}\right] \ge \left[\begin{array}{ccc}a&b&c\\ \frac{1}{a+c} & \frac{1}{a+b} & \frac{1}{b+c} \end{array}\right]}\)
oraz
\(\displaystyle{ \left[\begin{array}{ccc}a&b&c\\ \frac{1}{b+c} & \frac{1}{a+c} & \frac{1}{a+b} \end{array}\right] \ge \left[\begin{array}{ccc}a&b&c\\ \frac{1}{a+b} & \frac{1}{b+c} & \frac{1}{a+c} \end{array}\right]}\)
sumując te nierówności stronami otrzymamy:
\(\displaystyle{ 2(\frac{a}{b+c}+ \frac{b}{a+c}+ \frac{c}{a+b}) \ge \frac{a}{a+c} + \frac{b}{a+b} + \frac{c}{b+c}+ \frac{a}{a+b} + \frac{b}{b+c} + \frac{c}{a+c}=3}\) która jest równoważna dowodzonej nierówności.
ODPOWIEDZ