Matematické Fórum

Andrejka3

Ahoj.
Mám problém s druhou částí příkladu:
1) Nechť a, b jsou prosté posloupnosti délky n. Dokaž, že existuje rostoucí posloupnost indexů délky $\left\lceil\sqrt[4]{n}\right\rceil$ taková, že určuje monotónní podposloupnost a a monotónní podposloupnost b.
2) Dokaž, že je to nejlepší odhad.

Dokázat 2) jsem chtěla sestrojením protipříkladu pro každé n. Akorát to se mi nedaří. Máte nějaký nápad?
Stačilo by pro každé $n^4$ sestrojit dvě posloupnosti takové, že pro každou rostoucí posloupnost $n+1$ podposloupnost a jimi určená není monotónní nebo podposloupnost b není monotónní.

laszky · 13. 09. 2018 19:42

↑ Andrejka3:

Ahoj, mozna by slo pouzit nejakou analogii protiprikladu, uvedeneho na wiki u Erdosovy-Szekeresovy vety.

Andrejka3 · 13. 09. 2018 20:16

↑ laszky:
Ahoj.
Zkoušela jsem vzít $(i,a)$ posloupnost reprezentovatnou v $(\mathbb{R}^2,\leq_2)$ ,
kde $(x,y)\leq_2(z,t)\iff x\leq z\:\wedge\: y\leq t$
jako na tom protipříkladu, takže tři 'nezávislé' řetězce délky 3.
A teď bych asi potřebovala to zařídit tak, aby žádný (anti)řetězec délky $\left\lceil \sqrt[4]{9}\right\rceil+1=3$ nebyl zobrazen na řetězec nebo antiřetězec posloupnosti b (kterou chci takhle právě sestrojit).

Třeba jsem si nakreslila tohle na papír a zkusila jsem třemi barvami obarvit prvky patřící do stejného řetězce v b. Ale takhle to nejde, vždycky nějaký antiřetětec se mi zobrazil na antiřetězec. Buď to dělám špatně, nebo tudy cesta nevede.

check_drummer · 13. 09. 2018 21:44

↑ Andrejka3:
Ahoj, a jak prosím dokážeš bod 1? Děkuji. (Jen tak na první poheld mě napadá vybrat monotónní posloupnost z a a pro tyto indexy omezit b a z ní vybrat dále monotónní posloupnost z b, ale nevím, zda lze dosáhnout monotónní posloupnosti délky sqrt(n) - ale určitě jsem o tomto problému už někde četl. :-))

check_drummer · 13. 09. 2018 22:13

↑ Andrejka3:
Ahoj ještě jednou. Jde asi o to, že by mohlo být možné pro každou a sestrojit vhodnou b, pro které získáme monotónní podposloupnosti z a,b o co nejmenší délce. Tj. může být vhodné postupovat tak, že k a se pokouším nalézt co "nejhorší" b. Problém je v tom, že dostatečně dlouhých podposloupností v a může být hodně (zejména je problém, že se mohou překrývat) a já musím zajistit volbou b, aby byly všechny pomocí vhodné volby b co nejvíce "eliminovány".

Andrejka3 · 13. 09. 2018 22:19

↑ check_drummer:
Ahoj. Přesně jak píšeš.

Využívá se věty: Pro n prvkovou uspořádanou množinu (poset) platí $\alpha\cdot\omega\geq n$ ,
kde alfa je antiřetězec s nejvíce prvky (šířka) a omega je řetězec s nejvíce prvky (délka).

Aplikuje s tak, že když reprezentuješ posloupnost jako poset $\{(i,a); 0<i \leq n\}\subset \mathbb{R}^2$ s uspořádáním jako v ↑ Andrejka3:, tak řetětec v téhle poset je totéž, co neklesající ppsl, antiřetězec totéž, co klesající.

Proč to vyjde ta odmocnina: kdyby šířka i délka byla menší než horní část z té odmocniny, pak když je vynásobíš, vyjde číslo menší než n.

check_drummer · 15. 09. 2018 02:25

↑ Andrejka3:
Ahoj, nevím jestli to v tuto hodinu dává smysl:

Označím jako blok délky n rostoucí posloupnost délky n. Řeknu, že blok x je větší než blok y, pokud jsou věechny prvky z x větší než všechny prvky z y. Podobně definuju menší bloky.

(Pro jednoduchost ignoruju celé části.)
Posloupnost a sestrojím tak, že ji rozdělím na sqrt(n) bloků o délkách sqrt(n), kde každý následující blok je menší než blok předchozí.

Posloupnost b bude so trochu složitější - také ji rozdělím na sqrt(n) částí Ci o velikostech sqrt(n) - a každou část Ci sestrojím tak, jak jsem sestrojil posloupnost a (tj. rozdělím ji na sqrt(sqrt(n)) bloků o délce sqrt(sqrt(n)), atd.

Nyní je nutné vhodně zvolit velikost prvků v jednotlivých Ci, abych zajistil vhodné vztahy mezi prvky v různých Ci - relativní pořadí prvků v každé Ci však musí zůstat zachováno, tj. musím tyto prvky v jedné Ci všechny zvětšovat nebo změnšovat o stejnou hodnotu, abych nezměnil vztahy mezi prvky v rámci jedné Ci:
Částí Ci je sqrt(n) a já posloupnost těchto částí Ci (tj. posloupnost C1,C2,C3,..) rozdělím na sqrt(sqrt(n)) skupin o sqrt(sqrt(n)) prvcích a aplikuju na ně stejný postup jako na a - lze si to představit tak, že části Ci chápu jako jeden prvek a volím vzájemné velikosti těchto Ci.

Pak už by to snad mohlo zafungovat.

Andrejka3

↑ check_drummer:
Zkusím to nakreslit pro případ n=16, jak jsem to pochopila:
//forum.matweb.cz/upload3/img/2018-09/10262_monotpsl2.png
Tohle by mohlo fungovat, že?

Pro libovolné $n^4$ stačí upravit počet těch teček v blocích, a pro čísla mezi jen něco ubrat.
Díky!

check_drummer · 16. 09. 2018 00:04

↑ Andrejka3:
Ahoj, přesně tak jsem to myslel. Jen vzájemné umístění modrých a červených teček lze volit libovolně, tedy např. všechny modré body mohou mít větší hodnotu než všechny červené body. Ale takto z toho vznikl pěkný geometrický obrazec, třeba na ozdobení ubrusu. :-) Zvlášť kdyby se symetricky doplnila i ta prázdná pole, třeba se zaměněnými barvami. :-) No ale to už odbočuju.

Andrejka3 · 16. 09. 2018 01:01

↑ check_drummer:
Ubrus:
//forum.matweb.cz/upload3/img/2018-09/52467_ubrus.png

check_drummer · 18. 09. 2018 00:35

Pěkné :-)

Matematické Fórum

#1 12. 09. 2018 20:03 — Editoval Andrejka3 (13. 09. 2018 10:53)

Délka monotónních podposloupností, diskrétní

#2 13. 09. 2018 19:42

Re: Délka monotónních podposloupností, diskrétní

#3 13. 09. 2018 20:16

Re: Délka monotónních podposloupností, diskrétní

#4 13. 09. 2018 21:44

Re: Délka monotónních podposloupností, diskrétní

#5 13. 09. 2018 22:13

Re: Délka monotónních podposloupností, diskrétní

#6 13. 09. 2018 22:19

Re: Délka monotónních podposloupností, diskrétní

#7 15. 09. 2018 02:25

Re: Délka monotónních podposloupností, diskrétní

#8 15. 09. 2018 12:21 — Editoval Andrejka3 (15. 09. 2018 13:38)

Re: Délka monotónních podposloupností, diskrétní

#9 16. 09. 2018 00:04

Re: Délka monotónních podposloupností, diskrétní

#10 16. 09. 2018 01:01

Re: Délka monotónních podposloupností, diskrétní

#11 18. 09. 2018 00:35

Re: Délka monotónních podposloupností, diskrétní

Zápatí