Matematické Fórum

ameba · 10. 04. 2009 18:24

Hezké odpoledne, tak s tímhle si nevím rady. Zkoušela jsem si to rozepsat, vytvářet množinky a dívat se, jaké prvky mohou být nalevo a napravo od nich a hlavně jak dlouhé v nich mohou být podposloupnosti - domnívám se, že to je cesta, jen to ne a ne dotáhnout:

Ukažte, že libovolná posloupnost 1001 reálných čísel obsahuje (ostře) ros-
toucí, (ostře) klesající nebo konstantní podposloupnost délky 11. Ukažte
také naopak, že existuje posloupnost 1000 číısel, která ani jednu z uve-
dených podposloupností neobsahuje.

Kondr · 12. 04. 2009 18:42

Každému číslu a_i vposloupnosti přiřaďme trojici (l_i,c_i,h_i) kde l_i je délka nejdelší ostře klesající posloupnosti končící prvkem a_i, c_i délka nejdelší konstantní posloupnosti končící prvkem a_i a h_i délka nejdelší ostře rostoucí posloupnosti končící prvkem a_i. Pokud by žádné číslo h_i,l_i ani c_i nikdy nepřesáhlo 10, mohlo by být různých trojic (l_i,c_i,h_i) pouze 10*10*10. Pro posloupnost délky 1001 by se musela nějaká zopakovat. Snadno ukážeme, že se taková trojice opakovat nemůže, proto musí některé c_i,h_i nebo l_i překročit desítku, což jsme chtěli ukázat.

Druhá část je snadná: stačí nalézt jednu takovou posloupnost, pro kterou se každá trojice vyskytne právě jednou.

Matematické Fórum

#1 10. 04. 2009 18:24

Posloupnost 1001 čísel obsahuje rostoucí podposloupnost délky 11?

#2 12. 04. 2009 18:42

Re: Posloupnost 1001 čísel obsahuje rostoucí podposloupnost délky 11?

Zápatí