Subject: Diskretna matematika - 30.jun 2000 Date: 1. júl 2000 0:21 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= __________________________________________________________________________ http://neptun.w3.to | neptun@w3.to | telnet://atlantis.sk:7000