Pokaż, że ciąg zawiera podciąg (zasada szufladkowa?)

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
YyyYYyyyY
Użytkownik
Użytkownik
Posty: 86
Rejestracja: 19 lis 2011, o 20:59
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 43 razy

Pokaż, że ciąg zawiera podciąg (zasada szufladkowa?)

Post autor: YyyYYyyyY »

Niech \(\displaystyle{ (a_1, a_2, ..., a_{n^2+1})}\) będzie ciągiem rożnych liczb rzeczywistych. Pokaż, że ten ciąg zawiera podciąg długości \(\displaystyle{ n+1}\), który jest monotoniczny. Podaj przykład ciągu długości \(\displaystyle{ n^2}\), którego wszystkie podciągi monotoniczne są długości co najwyżej \(\displaystyle{ n}\).
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Pokaż, że ciąg zawiera podciąg (zasada szufladkowa?)

Post autor: Dasio11 »

Ogólniej: każdy ciąg o długości \(\displaystyle{ pq+1}\) ma podciąg niemalejący o długości \(\displaystyle{ p+1}\) lub podciąg nierosnący o długości \(\displaystyle{ q+1.}\)

Dowód: każdemu \(\displaystyle{ n \in \{1, 2, 3, \ldots, pq+1 \}}\) przyporządkujemy parę \(\displaystyle{ (i_n, d_n),}\) gdzie \(\displaystyle{ i_n}\) jest długością najdłuższego podciągu niemalejącego o początku w \(\displaystyle{ a_n,}\) a \(\displaystyle{ d_n}\) jest długością najdłuższego nierosnącego podciągu o początku w \(\displaystyle{ a_n.}\) Jeśli \(\displaystyle{ n < m}\) i \(\displaystyle{ a_n \le a_m,}\) to \(\displaystyle{ i_n \ge i_m+1,}\) a jeśli \(\displaystyle{ n<m}\) i \(\displaystyle{ a_n \ge a_m,}\) to \(\displaystyle{ d_n \ge d_m + 1.}\) Przyporządkowanie jest więc różnowartościowe. Gdyby dla każdego \(\displaystyle{ n}\) było \(\displaystyle{ i_n \le p}\) oraz \(\displaystyle{ d_n \le q,}\) to wyrazów ciągu mogłoby być co najwyżej \(\displaystyle{ pq.}\)

Przykładem ciągu długości \(\displaystyle{ n^2,}\) którego każdy monotoniczny podciąg ma długość co najwyżej \(\displaystyle{ n,}\) jest

\(\displaystyle{ a_n= \big( n, n+1, n+2, \ldots, 2n-2, 2n-1, \\ n-1, n, n+1, \ldots, 2n-3, 2n-2, \\ n-2, n-1, n, \ldots, 2n-4, 2n-3, \\ n-3, n-2, n-1 \ldots, 2n-5, 2n-4,\\ \vdots, \\ 3, 4, 5, \ldots, n+2, \\ 2, 3, 4, \ldots, n+1, \\ 1, 2, 3, \ldots, n \big).}\)
ODPOWIEDZ