Matematické Fórum

Ahoj, řeším tyto příklady, ale nejsem s to je dotáhnout do konce:

1. Najděte posloupnost funkcí f1 ... fn: N -> N taková, že pro všechna n náležící N platí: fi+1 == O(fi) & fi != O(fi+1). (i a i+1 jsou samozřejmě indexy.)

– Napadla mne horní celá část z funkce ((f/i)*n), kde i = 1...n. Může tak být?

2. Najděte rostoucí funkce f, g: N -> N takové, že f != O(g) & g != O(f).

– Napadly mne horní celé části z funkcí (sin n + n) a (cos n + n) definované na N, ale nejsem si jist, že je to stoprocentně správně. (I když podle WolframAlpha to tak docela i vypadá.)

3. Mějme n-prvkovou množinu X. Dokažte, že počet částečně uspořádaných podmnožin N je roven 2^Θ(n^2), tj. že existuje nějaké c, d náležící do kladných reálných čísel takové, že 2^(c*n^2) <= počet částečných uspořádání <= 2^(d*n^2).

– Tak tady jsem nepřišel sám na nic kloudného. Co jsem tak bloumal po netu, tak jsem zjistil, že dolní odhad počtu uspořádání je 2^((n^2)/4) – tzn. vytvoříme si z množiny n prvků dva antiřetězce délky (n/2) a pro každou dvojici z těchto množin (těch je (n^2)/4) se rozhodujeme, zda bude mezi nimi relace uspořádání či nikoliv – proto onen odhad. (Jestli jsem jeho význam dobře pochopil.) – Nemáte někdo nápad, jak by se dal ten počet ČUM na n prvcích odhadnout shora? Na to se taky dá někde sehnat formule, jenže ta je moc přesná a její odvození vůbec nechápu. (A navíc se mi nechce pouze opisovat...) Stačí mi jen náznak, jak by se to dalo odhadnout.