Subject: DM 24. 6. 1999 Caute! 1. A = alef0 Vypocitajte: (2^A + A^A)*A 2. Nech X je konecna mnozina, potom plati: a) ak f: X -> X je injektivne, tak f je "na" b) ak f: X -> X je "na", tak je injektivne. 3. Ukazte, ze kazda mnozina ma r prvkov, r >= 1 a kazdy prvok sa nachadza prave v r mnozinach, potom existuje system roznych reprezentantov pre mnoziny S1, S2, ..., Sm 4. Vyslovte a dokazte Eulerovu vetu o particiach. 5. Kazda postupnost n^2+1 roznych prir. c. obsahuje alebo rastucu, alebo klesajucu podpostupnost o n+1 prvkoch. 6. Vyslovte a dokazte nevyhnutnu a postacujucu podmienku na to, aby bola mnozina M spocitatelna. good luck. Zdravim Dnesne menu od pana T. (vsetko domace specialitky): 1. E^n = { (alfa1, ..., alfan) | alfai patri {0,1}; i=1, ..., n} alfa1 [alfa jedna], alfan nieje meno dalsieho mimozemstana, ale [alfa n] alfa~ [vid, citaj, pis: alfa s vlnovkou] alfa~ = (alfa1, ..., alfai) beta~ = (beta1, ..., betai) alfa~ =<' beta~ <=> alfai =< betai ; i=1, ..., n ^^^ - to je 'rovna sa alebo vacsie krutene' Dokazte, ze (E^n, =<') je ciastocne usporiadana mnozina. (riesne na prednaske, Spernerova veta) 2. Nech M je mnozina slov o dlzke n a A = {a1, ..., ak} je abeceda. Slova v mnozine M sa lisia aspon v 2 pismenach. Najdite horny odhad mohutnosti mnoziny M. (Dirichlet) 3. Nech E(m,n,r) je sposob rozdelenia m roznych guliciek do n roznych krabiciek, pri ktorych je prave r krabiciek prazdnych. Nech F(m,n,r) je blabla, pri ktorych je aspon r krabiciek prazdnych. (riesene na prednaske, princip zapojenia & vypojenia) 4. A teraz mozte aj rezat... Islo o nieco s grafom K5 a dotoho sefkuchar zamiesal trojuholniky s par plechovkami farby. (Vcelku nestravitelne.) 5. Realne cislo x sa nazyva algebraicke, ak existuju take cele cisla a0, a1, ..., an , ze pre kazde x plati a0 + a1 x + ... + an x^n = 0. Dokazte, ze mnoz. A algebraickych cisel je spocitatelna. (riesene na prednaske) 6. alef 0 [alef nula] si oznacim ako ocarujucialefnula teda ako A A A A a) 2 + 2 = 2 A A A b) A + A = 2 Dolezite upozornenie: opatovne objednanie menu je mozne az v auguste (31.8). Nezabudnite sa zapisat do poradovnika... ;> Vystrcil som ukazovak smerom k oblohe. Ocervenal. Povedal som: "Nach Haus`, nach Haus`..." Subj: DM - okruhle stoly Caute Boli tu akesi otazky na okruhle stoly, tak ponukam moju interpretaciu. Mimochodom v minulom mail-e som nedopatrenim uverejnil zly vysledok prikladu s okruhlym stolom a manzelmi, za co sa velmi ospravedlnujem. "Spravny" vysledok je: 4n suma(k=0..n) (-1)^k (n nad k) (2n-k-1 nad k-1) (k-1)! [(n-k)!]^2 OKRUHLY STOL NEPRIATELIA suma(k=0..n) (-1)^k (n nad k) 2^(k+1) n (2n-k-1)! suma(k=0..n) (-1)^k Sk <-- inkluzia exkluzia Sk=(n nad k) 2^(k-1) 4n (2n-k-1)! Sk je pocet takych rozsadeni, ze aspon k nepritelskych dvojic sedi vedla seba. (n nad k) <-- vybratie k dvojic ktore budu sediet vedla seba 4n <-- prvu dvojicu mozem posadit za prazdny okruhly stol 4n sposobmi, tym ale urobim nieco ako roztrhnutie stola (t.z. k zvysnym miestam sa spravam ako keby som usadzal za rovny stol) 2^(k-1) <-- k jednemu nepriatelovi mozem posadit druheho bud vlavo alebo vpravo, kedze ostalo k-1 dvojic ... (2n-k-1)! <-zvysok permutujem vsetkych je dokopy 2n, k som si vybral plus jeden bonusovy za prvu nepritelsku dvojicu (ten pri 4n) OKRUHLY STOL MANZELIA 4n suma(k=0..n) (-1)^k (n nad k) (2n-k-1 nad k-1) (k-1)! [(n-k)!]^2 V tomto priklade vam nemozem povedat Tomanov postup, ale iba odvovodnenie, ktore som mu vypotil ja. Nekritizoval ho sice, ale netvaril sa, ze by to bolo nejak extra dobre (ale vysledok je podla Tomana dobry) takze: Zas inkluzia-exkluzia ako minule Sk je pocet takych rozsadeni, ze aspon k manzelskyc dvojic sedi vedla seba. 2[(n-k)!]^2 <-- pocet usadenia n-k dvojic vedla okolo stola aby sedeli mzmz... (n nad k) <-- vybratie k dvojic ktore budu sediet vedla seba 2n <-- pocet sposobov usadenia prvej dvojice (2n-k-1 nad k-1)*(k-1)! <-- z 2n-k-1 volnych miest vyberiem k-1 na ktore usadim zvysne vybrate manzelske dvojice, ale musim ich este usporiadat (toto je podla mna blbost (!!!) ale inak si to neviem vysvetlit) Subj: DISKRETNA Ahojte. Bol som na skuske s Lomom, takze pisomku vam pisat nejdem. Na ustnej som dostal 4 otazky: 1) Ci poznam Jana Kovacika 2) Patricie (usp. aj neusp.) -> vid salabasre 3) Eulerova veta (1-x)*(1-x^2)*(1-x^3)* ... 4) Ak X je konecna mnozina, tak: a) f: X->X je zobrazenie 1-1, tak f je zobrazenie na b) f: X->X je zobrazenie na, tak f je zobrazenie 1-1 Subj: diskretna 27.5. Pisomku sme mali zaujimavu: 1. Najdite pocet vsetkych j-variacii s opakovanim z k prvkov, ked sme pouzili vsetky prvky z k (ries: zap-vyp) 2. Dokaz, ze v n^2+1 prvkovej postupnosti, existuje monotonna podpostupnost dlzky n+1. (niekde uz bolo riesenie) 3. Pocet E(m,n,r) a F(m,n,r) ---> Tomanove salabastre 4. Nech F je mnozina vsetkych konecnych postupnosti (tak dako to bolo zadane). Dokaz |F|=|N| 5. Dokaz Spernerovu vetu a vetu co sa pri tom pouziva ---> Salabastre. 6. Dokaz ze ak ma mnozina n prvkov, tak je konecna podla dedekinda a opacne (tusim ze opacne to nejde teda len ->). Ustna: Daval klasiky, ja som mal Ramseyho vetu a dokaz ze ked sa v K5 neda najst jednofarebny trojuholnik, tak je prave 5 hran zafarbenych jednou farbou.(Najprv treba dokazat pomocne tvrdenie.). Inac bola aj hyperkocka, a dokazy zo Tomanovych salabastrov . Preslo tusim 6 alebo 7 ludi, takze asi 50%. Povacsine dava rovnake znamky ako mal clovek v zime. Subj: Diskretna Date: Tue, 25 May 1999 14:21:56 MET Pisomka 1; Pocet permutacii o n prvkoch takych mnoziny(m1,m2,m3,...,mn) ze ziadne mi m(i+1) nejdu za sebou 2; Dokazte ze v kazdom rade k cisel existuje za sebou niekolko prvkou takych ze ich sucet je delitelny k 3; 2^Tn < An < 2^tn nad Tn 4; Halova veta aby existoval[Ao r roznych reprezentantov pre kazdu mnozinu 5; N^3 -> N 6; Konigova veta Ustna 1; Cantorova veta 2; Problem Holic;Holic externych kontrolor 3; Nutna a postacujuca podmienka konecnosti mnoziny Subj: diskretna(20.5.99) Tu su priklady: 1) pocet permutacii n prvkov, pri ktorych a(i+1) nenasleduje bezprostredne za a(i) pre i z {1,..,n-1} riesenie: Suma[k=0..n-1] (-1)^k * ((n-1) nad k) * (n-k)! myslienka: A(i) je mnozina permutacii, pri ktorych a(i+1) je hned za a(i) |A(i)| = (n-1)! |A(i) prienik A(j)| = (n-2)! (pre i!=j) (pozor: 2 pripady : - a1a2a3 - a1a2, a3a4) atd... 2) k cisel v riadku: dokazte, ze sucet niektorych za_sebou_iducich je delit k myslienka: nech S(i) je sucet prvych i cisel a) ak niektore S(i) je delit. k => hotovo b) ak nie => vsetky zvysky su z {1,..,k-1} -> DIRICHLET -> existuju i!=j take, ze S(i) mod k = S(j) mod k , ked odcitame S(j) od S(i) (j>i) dostavame za sebou iduce cisla , kt. nam vyhovuju 3) dokaz: 2^Tn < An < ((2^Tn) nad Tn) An - pocet Spernerovych systemov (vsetky systemy mnozin pre ktore plati - su podmn. povodnej mn. A, pozor: NEMUSIA DAVAT V ZJEDNOTENI A, ziadne 2 do seba nezapadaju (jedna nie je podmn. druhej)) Tn = (n nad (n mod 2)) |A| = n (mohutnost povodnej mn.) (bez riesenia - nenasiel som ziadne elegantne) 4) Nutna a postac. podmienka pre existenciu systemu VIACERYCH (aspon 2) reprezentantov mnozin. riesenie: pre vsetky k , pre vsetky i(1), .., i(k): |A(i(1)) prienik .. prienik A(i(k))| >= 2k - dokaz podobne ako Hall. veta, ale 3 pripady: |...| >= 2k+2 |...| = 2k+1 |...| = 2k 5) Zobrazenie f:N^3 -> N , bijektivne (najst) (riesenie je klasicke (vid f:Q -> N, bij.)) 6) Vyslovit a dokazat Konigovu vetu. Subj: Diskreditacia 20.5. 1. Dokazte (n+r-1)! n (n+r-3)! n*(n-1) (n+r-5)! n!*(n-1)! -------- - --- * -------- + ------- * -------- - ... = --------- r! 1 (r-2)! 1*2 (r-4)! r!*(n-r)! 2. Vyslovte a dokazte Eulerovu vetu 3. Vyslovte a dokazte Ramseyovu vetu 4. ( |A|^|B| )^|C| = |A|^ |B|*|C| 5. Ak mnozina A je podmnozinou N a je zhora neohranicena, tak |A|=|N| 6. |{1,2}^N| = |{1,2,3}^N| Mate toho malo. Pridite nabuduce. Subj: Diskretna 13.5.1999 -- 6. priklad Zdravim, tu je riesenie 6. prikladu s particiami ... Potrebujeme ukazat rovnost mohutnosti, takze ukazeme dve inkluzie. 1. pre kazdu particiu cisla n na max. m scitancov najdeme particiu cisla n+C(m+1,2) na presne m roznych scitancov. Vsimnime si, ze 1+2+3+...+m = C(m+1,2) Majme particiu n = a1 + a2 + ... + ak, k<=m. Nezalezi na poradi, takze 1 <= a1 <= a2 <=... <= ak a zaroven 1 < 2 < ... < m-k < m-k+1 < m-k+2 < ... < m scitame 1 < 2 < ... < m-k < a1+m-k+1 < a2+m-k+2 < ... < ak+m Toto je ale particia cisla n+C(m+1,2) na m navzajom roznych scitancov. 2. Majme particiu cisla n+C(m+1,2) na presne m roznych scitancov ... n+C(m+1) = a1 + a2 + ... + am nech bi = ai - i (teraz tie cisla odcitame), tak n = b1 + b2 + ... + bm Zjavne ai>=i => bi = ai-i>=0. Ak bi = 0, tak ta particia skratka nie je. Teda b1, b2, ..., bm su scitance particie cisla n. Pre particiu n sme nasli prislusnu particiu n+C(m+1,2) a naopak, takze pocty particii sa rovnaju. Subj: Diskretka 13.5.1999 Mate chut na nieco chladene ? Nech sa paci... 1. Kolkymi sposobmi mozeme posadit za okruhly stol s 2n stolickami (stolicky su ocislovane) n nepriatelskych dvojic tak, ze ziadna nepriatelska nebude vedla seba 2. Mame 2k+1 listkov, ocislovanych prirodzenymi cislami 1,2,...,2k+1 Aky najvacsi pocet listkov mozno vybrat tak, aby sa ziadne vybrane cislo nerovnalo suctu dvoch vybranych cisel. 3. Vyslovte a dokazte Konigovu vetu 4. Vyslovte a dokazte Cantorovu vetu 5. Dokazte, ze zjednotenie a karteziansky sucin dvoch spocitatelnych mnozin je spocitatelna mnozina. 6. Pocet particii cisla n o najviac m scitancoch je rovny poctu particii cisla / m+1 \ n + [ ] \ 2 / na m vzajomne roznych scitancov. Sa majte Vec: Diskretna, 11.6. 1. Dokaz, ze plati (n+r-1)! n (n+r-3)! n(n-1) (n+r-5)! n!(n-1)! -------- - -*-------- + ------*-------- - . . . = -------- r! 1 (r-2)! 1*2 (r-4)! r!(n-r)! 2. Nech A,B su dve konecne mnoziny, k>=1 prirodzene c. Medzi A a B je ustanoveny mnohoznacny vztah, ze kazdemu prvku mnoziny A zodpoveda prave k prvkov mn. B a naopak kazdemu prvku mn. B zodpoveda prave k prvkov mn. A. Dokaz, ze medzi A a B existuje bijekcia (kazdemu prvku je potom priradeny prvok v sulade s mnohoznacnym vztahom). 3. Dokaz odhad poctu Spernerovych systemov: 2^T < An < (2^T nad T) ; T=(n nad [n/2]) ; An je pocet Sper. sys. 4. Dokaz, ze v dvojfarebnom Kn, n>=10 existuje aspon (1/2)n^2-(19/2)n+61 jednofarebnych 3-uholnikov. 5. Nech A,B su konecne mnoziny, |A|=n, |B|=m. Dokaz: a) ak A a B su disjunktne, tak |AvB|=n+m b) |AxB|=n*m c) |A^B]=n^m 6. Nech f je zobrazenie z NxN do N take, ze pre m,n z N plati f(m,0)=n, f(n,m+1)=f(n,m)+1. Dokaz f(m,n)=m+n. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Na teorke daval klasiky - A(r), grafy, Ramseye, Halla, postupnosti, nepriatelov... Ak mal niekto 4 priklady viac-menej dobre, dostal este jeden a ak to mal 100%-tne, po vacsine isiel za 2 do bace. Mat priklad z pisomky dobre znamenalo tam mat pekne vyzerajucu omacku a spravny zaver, podrobnosti ho vobec nezaujimali. Gooth luck! Himmel --------------------------------------------------------------------------- Datum a cas: 6-JUN-1997 13:24 Vec: Diskretna...(6.6.97) Zdravim vas! Tu su priklady z diskretnej zo 6.6.97 1. S je mnozina disjunktnych intervalov (nie jednoprvkovych) na R. Dikazte, ze S je spocitatelna. 2. Pocet rozsadeni n nepriatelskych dvojic okolo okruhleho stola 3. Mnozina A je podmnozinou N a je zhora neohranicena, potom |A|=|N|. 4. Dokazte, ze system mnozin {S1,...,Sm} ma m roznych reprezentantov, ak kazda z mnozin ma prave r prvkov , a kazdy prvok sa nachadza prave v r mnozinach. 5. Dokazte, ze v dvoj-farebnom K24 existuje aspon jeden jedno-farebny K4. 6. En={ (x1,...,xn); xi je z {0,1} }, x=(x1,...,xn), y=(y1,...,yn), x<=y <=> xi<=yi. Dokazte, ze (En,<=) je ciastocne usporiadana a aky je maximalny pocet navzajom neporovnatelnych prvkov? Drzim palce, Boro. --------------------------------------------------------------------------- Datum a cas: 20-JUN-1997 14:06 Vec: diskretna 20.6. Priklady si nepamatam, ale to nie je podstatne. Bolo to terno, bud to bolo za tri alebo padak. Ine znamky myslim ani neboli. Mal som 5 prikladov z pisomnej. Na ustnej mi dal jeden. Ten som spravil. Potom mi dal este jeden, ktory som za pana boha nevedel vyratat a chcel ma poslat do prdele. Tak som sa ho spytal, ci mi moze povedat, kolko prikladov mam dobre z pisomnej (vtedy som to este nevedel) tak s odporom ale predsa si ich pozrel a prisiel na to, ze ich mam 5 dobre. !!! on si tie priklady asi ani vobec nepozrel, lebo ich az vtedy zacal hladat a opravovat !!! Drzim palce ostatnym, ktori to este stale nemaju. erce --------------------------------------------------------------------------- Datum a cas: 14-MAY-1997 14:39 Vec: Diskretna 14.5 1, Mame n*n+1 prvkovu postupnost roznych prirodzenych cisel. Ukazte, ze existuje monotonna podpostupnost dlzky n+1. 2, Mame dane j, k a c1, c2, az ck. Kolko je vsetkych kombinacii s opakovanim j prvkov z k, ze pre vsetky i je i ty prvok opakovany najviac ci krat. 3, Priklad s hyperkockou. Prelozene: A je mnozina n prvkovych binarnych vektorov s k jednotkami a B je obsahuje vsetky take vektori, ktore dostaneme s niektoreho vektoru z A pridanim jednotiek, tak aby jednotiek bolo l. Treba ukazat: |A|/(n nad k) <= |B|/(n nad l) Napr. ked n = 3, k = 2, l = 1, A = {(0, 0, 1), (1, 0, 0)} tak B = {(1, 0, 1), (1, 1, 0), (0, 1, 1)} 4, Konigova veta (to s tou maticou jednotiek a nul) 5, Ak R(m, n-1) = 2p; R(m-1, n) = 2q; teda su parne, potom plati: R(m, n) < R(m, n-1) + R(m-1,n) 6, Mnozina Q zjednotene s <0, 1> je spocitatelna. Dokazte. ---- Vsetci az na jedneho presli. Z prikladov na skuske dalej: Pocet rozsadeni manzelskych parov, Spernerova veta, Ramseyove cisla, Hallovo kriterium, 2k+1 papierkov kolko mozme vybrat tak aby ked vyberieme a,b,c tak a+b sa nerovna c, dokazat inkluziu exkluziu, odvodit eulerovu funkciu, odvodit A'(r). --------------------------------------------------------------------------- Date: Wed, 20 May 1998 12:10:31 MET Subject: Diskretna matika 20.5. 1. kolko je moznych rozsadeni n nepriatelskych dvojic okolo okruhleho stula s ocislovanymi stolickami... 2. mame postupnost n*n+1 roznych pri. cisel. dokazte, ze existuje rydzo monotonna podpostupnost dlzky n+1. 3. ostra nerovnost pri ramseovych cislach, ak tie dve su parne......... 4. Hallova veta.... 5. alef0 * alef0 = alef0 6. pocet partici cisla n na najviac m scitancov sa rovna poctu partici cisla m+n na m scitancov....... f... off --------------------------------------------------------------------------- Date: Thu, 11 Jun 1998 14:12:15 MET Subject: dm z 11.6.(99-1) 1. Dokazte, ze plati tato ohavna (na prve pohlady) suma, ci co: (n+r-1)! - n(n+r-3)! + n(n-1)(n+r-5)! - .... = n!(n-1)! --------- --------- -------------- -------- r! 1 (r-2)! 1.2. (r-4)! r!(n-r)! Predelte to (n-1)! a napravo dostanete kombinacne cislo n nad r. nalavo vam vyde najeke komb.cislo a komb.cislo s opak. To jest ... mame dokazat, ze tie komb. bez opakovania sa rovnaju komb. s opakovanim s nejakou specifickou podmienkou (zapojenie-vypojenie). Ta podmienka je - od vsetkych komb. s opak. odpocitam tie, ktore maju jeden prvok aspon dvakret vo vybere, dva prvky vo vybere aspon dvakrat a .... k prvkov vo vybere aspon dvakrat (Sk) 2. Nech An je pocet Spernerovych systemov pre mnozinu z n-prvkov. Dokazte, ze plati ... Tn / Tn \ Tn 2 < An < | 2 | (2 nad Tn) \ / \ Tn / kde Tn je / n \ | n/2 | \ / Prva nerovnost je zrejma. Majme B1,B2,...,Bm (m = Tn) mnozin, ktore tvoria Spernerov system. Z nich mozeme vytvorit dalsie tak, ze zoberiem jej lubovolne podmnoziny (z mnozin B1,..,Bm) . A to je presne 2^Tn 3. Student riesi ulohy v priebehu roka. Kazdy den riesi (neznamena, ze vyriesi) aspon jednu ulohu. Aby nebol pretazeny, v kazdom tyzdni vyriesi najviac 12 uloh. Dokazte, ze existuje niekolko po sebe iducich dni, pocas ktorych student vyriesi 20 uloh. (nemusi existovat, ak je to takto zadane, kontra priklad nech si citatel nakde sam). (na skuske dal..sformulujte, aby to malo riesenie...) (stacilo ... kazdy den VYRIESI aspon ...) 4. N N Dokazte, ze mnoziny {0,1} a {0,1,2} maju rovnaku mohutnost (budto tak ako v zimnom semestri - najst bijekciu viz Tomanove prednasky) (alebo takto N N 2<=3 -> 2 <=3 N N N 3 <= N = 2 cim je tvrdenie dokazane . . . ) 5. Nech A,B su konecne mnoziny, |A|=n, |B|=m a) ak A,B su disjunktne, tak |AvB|=n+m b) |AxB|=n.m | B | m c) |A | = n (dokaz na prednaske) 6.Nech X je konecna mnozina. Potom plati : a) ak f:X --> X je injekcia, tak f je bijekcia b) ak f:X --> X je surjekcia, tak f je aj injekcia (teda bijekcia) (nema vyznam rozsirovat sa o tom...) riesenia su jedne z mnohych, pricom clovek nikdy nevie, ako to vlastne je... takze vela zdaru v dalsej praci a do dalsich rokov len to najlepsie ad referendum matus --------------------------------------------------------------------------- Date: Tue, 16 Jun 1998 13:17:21 MET Subject: Diskretna 16.6 Cafte 7infovia! takze: 1. pisomku sme mali peknu: 1. pocet permutacii n prvkov takych ze a_(i+1) nenasleduje bezprostredne za a_i. (i<=n-1) > toto sa robilo na cvikach, inac = n! - Suma(i=1 az n-1) (-1)^(i+1).(n-1 nad i).(n-i)! 2. je danych k prvkov v riadku, dokazte ze existuje medzi nimi postupnost po sebe iducich prvkov takych, ze ich sucet je delitelny k > urobime sucty a_1, a_1+a_2, ... dostaneme k suctov. Bud existuje delitelny k (Si mod k=0) alebo vsetkych k ma zvysky z {1..k-1}. Dirichletov princip - existuju dva rovnake zvysky. Ak tie sucty odcitame... 3. Dokazte pomocou indukcie pre n ze mohutnost komplementu zjednotenia n mnozin sa rovna suma(k=0 az n) (-1)^k.Sk > v skriptach 4. Nutna a post podm. existencie _viacerych_ reprezentantov. (tento priklad je v tych lajstrach s prikladmi medzi pr. roznych d.) >Podm: aby lub. zjednotenie k mnozin malo aspon 2k prvkov. podobne ako dvokaz hallovej vety, ale 3 pripady: ak vsetky >= 2k+2, ak vsetky >=2k+1, ak vsetky >=2k 5. Bijekcia N^3 -> N 6. Dokaz konigovej vety 2. ustna: 1. Dokazat eulerovu vetu o particiach 2. DEfinicia grafu 3. zaver: bolo to neskutocne lahke. Niekto mal stastie... 4. Credits: Majovi za 1.2,1.4 Robovi za 1.5 Cafte. Nech mate take stastie ako ja!!!