Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

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

Andrejka3
Moderátor
Příspěvky: 1992
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

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í.


What does a drowning number theorist say?
'log log log log ...'

Offline

  • (téma jako vyřešené označil(a) Andrejka3)

#2 13. 09. 2018 19:42

laszky
Příspěvky: 1399
Škola: MFF UK, FJFI CVUT
Reputace:   112 
 

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

↑ Andrejka3:

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

Offline

 

#3 13. 09. 2018 20:16

Andrejka3
Moderátor
Příspěvky: 1992
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

↑ 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.


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#4 13. 09. 2018 21:44

check_drummer
Příspěvky: 2682
Reputace:   73 
 

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

↑ 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. :-))


Jak se nazývá množina shodných disjunktních krychlí?
Ragú

Offline

 

#5 13. 09. 2018 22:13

check_drummer
Příspěvky: 2682
Reputace:   73 
 

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

↑ 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".


Jak se nazývá množina shodných disjunktních krychlí?
Ragú

Offline

 

#6 13. 09. 2018 22:19

Andrejka3
Moderátor
Příspěvky: 1992
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

↑ 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.


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#7 15. 09. 2018 02:25

check_drummer
Příspěvky: 2682
Reputace:   73 
 

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

↑ 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.


Jak se nazývá množina shodných disjunktních krychlí?
Ragú

Offline

 

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

Andrejka3
Moderátor
Příspěvky: 1992
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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

↑ check_drummer:
Zkusím to nakreslit pro případ n=16,  jak jsem to pochopila:
//forum.matematika.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!


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#9 16. 09. 2018 00:04

check_drummer
Příspěvky: 2682
Reputace:   73 
 

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

↑ 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.


Jak se nazývá množina shodných disjunktních krychlí?
Ragú

Offline

 

#10 16. 09. 2018 01:01

Andrejka3
Moderátor
Příspěvky: 1992
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

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


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#11 18. 09. 2018 00:35

check_drummer
Příspěvky: 2682
Reputace:   73 
 

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

Pěkné :-)


Jak se nazývá množina shodných disjunktních krychlí?
Ragú

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson