Podciągi monotoniczne/modyfikacja Twierdzenia Erdosa-Szekere

[adrianoo07]

Witam,

Znam twierdzenie Erdosa-Szekeresa, jednak interesuje mnie pewna jego modyfikacja. Mam dowolny ciąg (liczby mogą się powtarzać), i chcę wiedzieć jak mogę ograniczyć od dołu, długość pewnego jego podciągu niemalejącego bądź nierosnącego. Wiem że mogę przez \(\displaystyle{ \sqrt{n}}\), lecz ze względu na to że w tym ciągu mogą powtarzać się elementy, oraz interesują nas podciągi niemalejące bądź nierosnące, te ograniczenie będzie być może większe.

Z góry dziękuje za pomoc ; )-- 16 maja 2011, 08:34 --chociaż jak się tak zastanowiłem to nie ma znaczenia żadnego że ten ciąg jest dowolny ; ) w najgorszym przypadku dostaniemy ciąg o wszystkich różnych elementach i wyjdzie na twierdzenie Erdosa-Szekere ; )

Pozdrawiam