Priklady zo skusok -> diskretna matematika 2, Eduard Toman, LS 2000 =================================================================== Dnes si Toman vymyslel toto: 1. uloha o manzelskych dvojiciach,mame ich usadit okolo okruhleho stola s 2n stolickami tak,aby ziadni manzelia nesedeli vedla seba a striedali sa muzi a zeny... (stolicky su ocislovane) 2. Hallova veta aj s dokazom 3. Nech m,n>2 a cisla R(m,n-1) a R(m-1,n) su parne.Potom plati: R(m,n) < R(m,n-1)+R(m-1,n) 4. Nech |A|=n a |B|=m. Potom: a) |A U B| = n + m ak A a B su disjunktne b) |A x B| = n . m c) |A ^ B| = n ^ m 5. Nech M je mnozina slov dlzky n v abecede A={a1,...ak} (k>=2). Kazde 2 slova mnoziny M sa lisia v aspon dvoch pismenach. Odhadnite zhora mohutnost mnoziny M. 6. Dokazte, ze |Z x <0,1)| = |R|, a potom aj |R|.|N| = |R|. P.S: Aj keby ste to mali dobre, je toho malo. Pridte nabuduce! (Toman) ------------------------------------------------------------------------------- oki, takze este nist nedoslo: tak to tu mate: pisomka: 1. konigova veta 2. ohranicet zhora mnozinu cisel ktore mozno vybrat z {1,...,2k+1} tak aby zjadne znix nebolo suctom dvox uz vybranyx (je to <=k+1) 3. nex su dane cele prirodzene cisla n,K a nezaporne cele cisla c1,..,ck. urcte pocet K-prvkovyx kombinacii s opakobanim z n prvkov, ktoryx sa pre kazde i z {1,...,n} poakuje prvok i-ty prvok najvjac ci-krat. ..iny grc: muoj wysledok (ET ho zozral, ale ja by som zan ruku do ohna nedal: n K k /n+K-1\ ---- k+1 /n\ ---- /n-K-SUM-l-1\ | ---- | | - \ (-1) * | | * \ | | | SUM= \ (cij+1) \ K / /___ \k/ /___ \ K-SUM-l / | /___ k = 1 l=SUM+1 j=1 co ine ako princip zapojenia a vypojenia :)) 4. A, B su konecne mneoziny |A|=|B| a exi stuju zobrazenja: f:A->B^k a g:B->A^k. treba dokazat ze ex. bij zobrazenja medzi A a B ktore su urcene f a g... (ET okolo toho dost kecal... ja som to moc nexcapal :)) 5. An - pocet Spernerovyx systemov n-prvkonej mnoziny, Tn = n nad |_ n/2 _|, dokazat ze: 2^Tn < An < 2^Tn nad Tn 6. Dokazat ze kazde prirodzene cislo sa da napisat ako sucet fibonacciho cisel, z ktoryx ani dve njesu "susedne". (induxia) Ustna: navyse Algoritmus... ruozni reprezentanti.. bla bla Zaklad: tvarit sa suverenne :))) c u when u get there ...tbc ________________________________________________________________________________ http://tbc.w3.to ------------------------------------------------------------------------------- 1. Ak su dane 4 rozne body v rovine , potom aspon jeden uhol ktory urcuju je vacsi ako pi/2 (dirichlet) 2. Dokazte ze mnozina vsetkych konecnych postupnosti vytvorenych z prvkov niektorej spocitatelnej mnoziny je spocitatelna mnozina. 3. Kolko je vsetkych permutacii, n>1 prvkov m1,m2,...,mn v ktorych pre ziadne i patriace do {1,2,...,n-1} nie je prvok m s indexom i+1 bezprostredne za prvkom m s indexom i. 4.Vyslovte a dokazte Ramseyovu vetu. ( tu o farbeni ) ( dokaz k nej neni v salabastroch ale staci dokazat tu R(m,n)<=R(n-1,m)+R(m,n-1) a to zarucuje existenciu n,m ) 5. Najdi proste zobrazenie z N na tretiu do N. 6. Dokazat tu blbost so Spencerovym systemom v n-prvkovej mnozine 2 na Tn < An < .... To je vsetko ... zatial je pocet vyhodenych a prejdenych v pomere 4:4 .... odisiel pocas pisomky na xvilu na hajzel ale moc sa mu von xodit nexcelo... pocas ustnej odisiel asi na pol hodinu... Zelam vela stastia ... Vlado ------------------------------------------------------------------------------- Maxim, 18:56:23 30. jun 2000 (piatok) Heya vsetci! Dnesna pestra Diskretka: 1.) Dokazte, ze nemozno najst viac nez 4 lubovolne sestciferne cisla zostavene z dvoch cifier tak, aby sa lubovolne dve lisili aspon na styroch miestach. Riesenie: Da sa vseliak, ja som riesil takto: Najdime si 4 sestciferne cisla, splnajuce dane podmienky. Dokazeme, ze uz ziadne dalsie splnajuce dane podmienky nemoze existovat. Uvedene cisla su napr.: X1=000000, X2=001111, X3=110011, X4=111100. Ze dalsie uz nemoze byt, doporucujem dokazovat priamo, teda sa ho pokusit skonstruovat a pritom ukazat, ze to nejde. 2.) Kolko je vsetkych permutacii z n prvkov m1,m2,...,mn v ktorych pre ziadne i lezi {1,2,...,n} nie je prvok na i-tom mieste a pritom prvky m1,m2 su vedla seba? 3.) Vyslovte a dokazte Spernerovu vetu. Dokazte aj pomocne tvrdenie. 4.) Dokazte, ze neplati nasledujuca veta: V kazdom strome, ktory ma najviac 1+k+...+k^(n-1) vrcholov a kazdy vrchol vetvenie najviac k, existuje vrchol dlzky vacsej ako n. 5.) Nech f:R->R ne rydzomonotonna funkcia. Potom mnozina vsetkych bodov je spocitatelna. Riesenie: Moje, za jeho spravnost nerucim. Medzi kazdymi dvoma bodmi nespojitosti sa nachadza aspon jedno racionalne cislo (za toto nedam do ohna nic! :>). Teda ku kazdemu bodu nespojitosti mozeme priradit jedno racionalne cislo, reprezentanta tohto bodu. Vieme, ze mnozina je spocitatelna prave vtedy, ak jej prvky mozeme zoradit do postupnosti. Musime zoradit mnozinu reprezenatantov bodov nespojitosti do postupnosti. Na dokaz, ze lubovolna mnozina {x; x lezi v Q} sa da zoradit do postupnosti, staci ak zoradime do postupnosti mnozinu Q. To uz dufam zvladne kazdy, keby nie tak poradim, ze kazde racionalne cislo sa da napisat ako p/q; p lezi v Z; q lezi v N. Urobime tabulku Z x N a v nej vyznacime postupnost (to je ten tradicny had, urcite ste to uz videli). 6.) Bola, ale za svet som nevedel precitat. Riesila sa ale Hallovou vetou. No a teraz nieco z teorie: 1.) Najskor som dostal dokazat matematickou indukciou Princip zapojenia a vypojenia vzhladom na pocet mnozin. 2.) Potom priklad. Zisti pocet prvocisiel mensich ako 36. Ja reku, ze ich aj vymenujem. A on, ze na to by ma bolo a povedal, ze mam uplatnit poznatky z mojho predchadzajuceho dokazu. Tak som teda uplatnil. 3.) Dostal som Eulerovu vetu, dost som sa trapil a teda... 4.) ... som vyfasoval este Cantorovu vetu aj so vsetkymi dosledkami. To som skopal a potom uz nasledoval iba zapis do indexu s trojeckou. vsetkym, ktorym sa to dnes (prip. v ine dni) nepodarilo drzim v auguste palce a tesim sa na skore stretnutie v tyzdni matematickej analyzy (10.-15.7.2000). S pozdravom Vas =Nepto= __________________________________________________________________________ ------------------------------------------------------------------------------- Dnes mozete prejst vsetci,vsetko uz bolo... 1. Hallova veta + algoritmus na najdenie toho systemu (este neviem co tam po nas chcel,no uz viem-cely algoritmus,ha) 2. Eulerova veta o particiach. 3. Cantorova, dokaz + vsetky dosledky 4. x prirodzene, x>0 , nech p(x) je pocet prvocisel neprevysujucich x. Urcte p(n)-p(Sqrt(n)) , n je prir. cislo vacsie ako 1 Urcte pocet prvocisel neprevysujucich 36. 5. Dok, ze pre umocnovanie mohutnosti plati (|A|^|B|)^|C|=|A|^(|B|.|C|) 6. E^n={(alfa_1,...,alfa_n),alfa_i je 0 alebo 1 pre secky prislusne i} alfa~=(alfa_1,...,alfa_n), beta~=(beta_1,....,beta_n); alfa~ krutene_mensie rovne beta~ <=> alfa_i mensie rovne beta_i ;i=1,n (toto su porovnatelne prvky-ostatne neporovnatelne) (E^n,=<) je ciastocne usporiadanie mnoziny E^n, urcte maximalny pocet neporovnatelnych prvkov. Teraz sa uz len caka a caka, a caka... Nic tazke,len to vediet :) ((: No tak sa majte a vela zdaru :)) mayo