szukanie zaawansowane
 [ Posty: 10 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 29 lis 2017, o 19:25 
Użytkownik
Avatar użytkownika

Posty: 26
Lokalizacja: Warszawa
Cześć,

Szukam dowodu na twierdzenie o ciągach jednomonotonicznych dla więcej niż dwóch ciągów, gdzie każdy element każdego z ciągów ma ten sam znak. Najlepiej, żeby był w miarę niedługi, bo może się przydać do napisania na konkursach. Napiszę może to twierdzenie w wersji dla dwóch ciągów, ale wiem, że działa analogicznie w przypadku większej ilości.

Dla dwóch niemalejących ciągów a_{i} i b_{i} zachodzi nierówność:

\sum_{i=1}^{n} a_{i}b_{n+i-1}  \le  \sum_{i=1}^{n} a_{i} b_{\sigma(i)} \le  \sum_{i=1}^{n} a_{i}  b_{i}, gdzie \sigma(i) to dowolna liczba od 1 do n, która nie została jeszcze użyta w tej sumie (mam nadzieję, że jest to zrozumiałe).

Pozdrawiam
Góra
Mężczyzna Offline
PostNapisane: 29 lis 2017, o 20:49 
Moderator

Posty: 1979
Lokalizacja: Trzebiatów
Wezmy pod uwagę ciągi \left( -6, -7, - 8\right) , \left( -2, -3, -4\right) , \left( 4, 3, 2\right). Wszystkie są jednomonotoniczne, skąd z tw. dla 3 ciągów mielibyśmy, że maksymalna wartość wynosi 48 + 63 + 64. Z drugiej strony wystarczy zauważyć, że większą wartość otrzymamy dla \left( -8, -7, -6 \right) , \left( -4, -3, -2\right), \left( 4, 3, 2\right), które są pewnym mixem, ale dają większą wartość sumy.
Wnioskowałbym, że są potrzebne dodatkowe założenia, na pewno co do znaku. Zakładając, że wszystkie wyrazy w każdym ciągu są dodatnie dość łatwo udowodnić uogólnione twierdzenie na podstawie przypadku n = 2.
Góra
Mężczyzna Offline
PostNapisane: 29 lis 2017, o 21:05 
Użytkownik
Avatar użytkownika

Posty: 26
Lokalizacja: Warszawa
Zahion, założeniem jest, że każdy z ciągów jest niemalejący, o czym napisałem, ale chyba niewystarczająco to podkreśliłem.

Tak więc, dla dwóch ciągów założeniem jest:
a_{1} \le  a_{2} \le ... \le  a_{n}
b_{1} \le  b_{2} \le ... \le  b_{n}.

I może wypadałoby, żebym dokładniej sformułował twierdzenie dla, powiedzmy, trzech ciągów, aby bardziej klarownym było, co właściwie trzeba udowodnić.

Założenie:
a_{1} \le  a_{2} \le ... \le  a_{n}
b_{1} \le  b_{2} \le ... \le  b_{n}
c_{1} \le  c_{2} \le ... \le  c_{n}

Teza:
\sum_{i=1}^{n} a_{i}  b_{i}  c_{i} \ge  \sum_{i=1}^{n} a_{\sigma (i)}  b_{\tau (i)}  c_{\phi (i)}, gdzie \sigma (i) to dowolna permutacja zbioru \left\{ 1,2,...n \right\}, \tau (i) to dowolna permutacja zbioru \left\{ 1,2,...n \right\} i \phi(i) to dowolna permutacja zbioru \left\{ 1,2,...n \right\} dla i = 1, 2, ..., n.

EDIT: Znalazłem dowód dla dwóch ciągów, który znałem, ale uznałem, że to za dużo pisania na forum.
Góra
Mężczyzna Offline
PostNapisane: 29 lis 2017, o 21:13 
Moderator

Posty: 1979
Lokalizacja: Trzebiatów
Może inaczej, literkowo zobrazuje co mam na myśli.
Niech a_{1} = -5 , a_{2} = 1 dalej b_{1} = -5 , b_{2} = 1 i c_{1} = 1 , c_{2} = 2. Twoje założenia są spełnione, prawda ?
Nasza suma wtedy to 25 + 2 = 27.
Z drugiej strony jeżeli rozpatrzymy inną permutację ciągu c_{n} to otrzymamy większą wartość, wbrew temu co chcielibyśmy uzyskać : \left( -5 , 1\right), \left( -5, 1\right), \left( 2, 1\right) to otrzymamy wartość 50 + 1 = 51.
Góra
Mężczyzna Offline
PostNapisane: 29 lis 2017, o 22:04 
Użytkownik
Avatar użytkownika

Posty: 26
Lokalizacja: Warszawa
Faktycznie, zdaje się, że to twierdzenie sprawdza się jedynie wtedy, gdy wszystkie elementy każdego z ciągów mają ten sam znak. Niech więc to będzie naszym dodatkowym założeniem.
Góra
Mężczyzna Offline
PostNapisane: 29 lis 2017, o 22:08 
Moderator

Posty: 1979
Lokalizacja: Trzebiatów
Udało mi się coś znalezc.
Wyszukaj pod hasłem : Generalized Reverse Rearrangement, Daniel S. Liu pdf.
Niestety dowód aż tak krótki nie będzie, znośny - jak najbardziej.
Góra
Mężczyzna Offline
PostNapisane: 29 lis 2017, o 22:24 
Użytkownik
Avatar użytkownika

Posty: 26
Lokalizacja: Warszawa
Bardzo podobne, ale mówi o iloczynie dwóch ciągów, a nie o ich sumie. To znaczy, dowód na sumę pewnie byłby podobny, ale w dokumencie zawarty jest tylko dowód dla dwóch ciągów, a taki już znam.
Góra
Mężczyzna Offline
PostNapisane: 29 lis 2017, o 22:55 
Moderator

Posty: 1979
Lokalizacja: Trzebiatów
Na początku jest dowód dla dwóch ciągów, na dole jest uogólnienie na n, o ile mówimy o tym samym dokumencie.
Góra
Mężczyzna Offline
PostNapisane: 29 lis 2017, o 23:16 
Użytkownik
Avatar użytkownika

Posty: 26
Lokalizacja: Warszawa
Okej, zdaje się, że sam wpadłem na pomysł dowodu. Jest on rekurencyjny, ale może postaram się przedstawić go dla trzech ciągów. Zakłada on jednak, że wszystkie elementy ciągów są większe równe 0.

1.a_{1}  \le  a_{2}  \le ... \le  a_{n}
2.b_{1}  \le  b_{2}  \le ... \le  b_{n}
3.c_{1}  \le  c_{2}  \le ... \le  c_{n}

Z 2 i 3 wynika, że b_{1} c _{1}  \le  b_{2}  c_{2}  \le ...  \le  b_{n} c _{n}. Możemy każdą z par z postaci b_{i}  \cdot  c_{i} nazwać x_{i}. Wtedy x_{1}  \le  x_{2}  \le ... \le  x_{n}.

Teraz mamy dwa ciągi monotoniczne: a_{1}  \le  a_{2}  \le ... \le  a_{n} i x_{1}  \le  x_{2}  \le ... \le  x_{n}. Na nich korzystamy z twierdzenia o dwóch ciągach.

Analogicznie dla większej ilości ciągów.
Góra
Mężczyzna Offline
PostNapisane: 29 lis 2017, o 23:38 
Moderator

Posty: 1979
Lokalizacja: Trzebiatów
To jest pierwsza rzecz, która rzeczywiście przychodzi do głowy, ale :
Wtedy dowodzisz, że \sum_{i=1}^{n} a_{i}b_{i}c_{i}  \ge  \sum_{i=1}^{n} \left( a_{i}b_{i}\right)c_{l(i)}, gdzie l, k : \left\{ 1, 2, ..., n \right\}  \rightarrow \left\{ 1, 2, ... , n \right\} ( innymi słowy co np. z a_{1}b_{2}c_{3}, tak jak w nierówności \sum_{i=1}^{n} a_{i} b_{i} c_{i} \ge \sum_{i=1}^{n} a_{\sigma (i)} b_{\tau (i)} c_{\phi (i)} ). Wcześniej pojawia się kolejne pytanie ( które intuicyjnie jest proste do rozwiązania ). Dla dowolnej sumy stworzonej z permutacji k, l postaci\sum_{}^{} a_{l(i)}b_{k(i)} możemy poustawiać wyrazy naszego nowego ciągu y_{i} = a_{l(i)}b_{k(i)} jednomonotonicznie względem c_{i}. Pytanie brzmi - dlaczego ta wartość ma być mniejsza od tej, którą otrzymamy w Twoim wypadku. Te kwestie wyglądają na wymagające uzasadnienia.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 10 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 tw. o trzech ciągach  anitap23  0
 Dowód granicy pierwiastka n-tego stopnia z dowolnego ciągu.  Gregoreo  9
 Granice ciągów z twierdzenia o trzech ciągach  Orki  6
 Granica ciagu - dowod twierdzenia - zadanie 2  Igno  2
 Znalezc granice korzystając z twierdzenia o trzech ciągach  ghostko  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl