Monotónní podposloupnosti

Úloha číslo: 3792

Ukažte, že v každé dostatečně dlouhé číselné posloupnosti lze nalézt buď nerostoucí podposloupnost délky \(a+1\) nebo neklesající podposloupnost délky \(b+1\).

(Nalezněte nějaký odhad pro potřebnou délku posloupnosti.)

  • Řešení

    Pro danou posloupnost \((a_1)_{i=1}^n\) obarvíme hranu \((i,j)\), \(i<j\) grafu \(K_n\) modře pokud \(a_i<a_j\) a jinak červeně.

    Je-li \(n>R(a+1,b+1)\), potom prvky posloupnosti odpovídající vrcholům monochromatického úplného podgrafu tvoří hledanou monotónní podposloupnost.

  • Varianta

    Ukažte, že monotonní podposloupnost z předchozí varianty existuje v každé posloupnosti délky \(ab+1\).

Obtížnost: Obtížná úloha
Úloha řešená úvahou
Úloha na dokazování, ověřování
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze