Návrat na detail prednášky / Stiahnuť prednášku / Univerzita Komenského / Fakulta matematiky, fyziky a informatiky / Diskrétna matematika 2
Pár príkladov zo skúšky (subject.doc)
Subject: Diskretna
Date: 29. jún 2000 13:37
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
Date: 24. máj 2000 9:54
Povodna sprava:
Datum a cas: 23-MAY-2000 22:05
---------- Forwarded message ----------
Date: Thu, 18 May 2000 00:02:32 +0200
Date: Wed, 17 May 2000 14:21:24 +0200 (CEST)
Subject: Diskretna 17.5.2000
Dnes sme boli na diskretnej traja a ujo Edo nemal
velmi dobru naladu :-(
Pisomna cast:
1., Eulerova veta pre particie.
To ako comu sa rovna (1-x)*(1-x^2)*(1-x^3)*...
2., Dokazte, ze ak kazdy prvok sa vyskytuje prave v r mnozinach,
r>=1, tak potom existuje system roznych reprezentantov pre mnoziny
{S_1,..,S_n}
3., NEch x_1, x_2, ... x_n su realne cisla |x_i|>1. Dokazte, ze
v lubovolnom intervale dlzky 2 mame NIE viac ako n nad (n div 2)
suctov tvaru
n
--
\ e x ; e = +-1
/ k k k
--
k=1
Toto som nejak previedol na ulohu, ze kazde x_i je vacsie ako 2
a_k je bud 0 alebo 1. Potom sa zostroja mnoziny, kde x_i patri, ak
je pri nom 1, inac (ak je pri nom 0 nepatri). Dokazeme, ze dve
mnoziny, ktore su vlastnou podmnozinou, musia mat rozdiel suctov
viac ako 2. Pustime Spernerovu vetu a sme stastni... Edo to zozral.
4., Uloha o manzelskych dvojiciach. Kolkymi sposobmi mozme usadit
za okruhly stol n manzelskych dvojic tak, aby aby ziaden manzelsky
par nesedel vedla seba muzi so zenami sedeli na striedacku.
5., Dokazte, ze ak m,n su vacsie ako 2 a cisla R(m-1,n-1) su parne.
Potom R(m,n)<R(m-1,n)+R(m,n-1).
... tu chcel aj tu vetu z paperov, ktorabola pred touto
6., Nutna a postacujuca podmienka, aby mnozina bola spocitatelna.
Ustna:
1., Eulerova veta pre pocet cisel nesudelitelnych s cislom n.
2., Hallova veta
...toto som ani nezatal, tak sme si s nim dohodli rande na inokedy.
Do lietania
Brano
PS. Na zaver bonus:
Edo dava velmi rad vety z papierov ... a hlavne tie, ktore neprednasal.
----- End forwarded message -----
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).
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...
Subject: DM 21.6.2000
Date: 21. jún 2000 14:22
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 :)))
Subject: DM 30.5.2000
Date: 30. máj 2000 14:57
Takze zdrawim : priklady:
1. Nech A_n je pocet Spernerovych systemov v n-prvkovej mnozine.
Potom plati:
(2^T_n)
2^T_n < A_n < ( nad )
( T_n )
2. Nech M=(S_1,S_2, ... , S_m) je system konecnych neprazdnych
mnozin. Pozadujeme aby kazda mnozina mala viacej ako jedneho
reprezentanta (r>1) pozadujeme roznost reprezentantov. Vyslovte
a dokazte nutnu a postacujucu podmienku existencie roznych
reprezentantov.
3. Dokazte 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)!
4. F_0=0 F_(n+2)=F_(n+1) +F_n (klasicka fibonnaciovka)
F_1=1
dokazte ze plati F_n=1/5^(1/2)[ ...] ten nerekurzivny vzorcek
5. Odvodte vzorec pre vypocet A'(r)
6. Vyslovte a dokazte Ramseyovu vetu.
Subject: Skuska DM 26.5.
Date: 26. máj 2000 10:05
Ahojte, takze tu su niektore (vsetky) z dnesnych prikladov na skuske z DM,
vidno, ze staci mat precitane skripta a prepocitane priklady z papierov:
1.Nech x1,..,xn su realne cisla |xi|>1. Dokazte, ze v lubovolnom intervale
dlzky 2 mame nie viac ako ( n ) suctov tvaru
n ( |_ n/2 _| )
---
\ E . x ,kde E = + 1
/__ k k k -
k=1
2.Kazda postupnost n^2+1 roznych prirodzenych cisel obsahuje alebo rastucu
alebo klesajucu podpostupnost n+1 prvkov.
3.Uvedte a zdovodnite algoritmus pre najdenie systemu roznych reprezentantov.
4.Dokazte, ze prienik rozkladov (particii) cisla n na navzajom rozne scitance
je rovny prieniku rozkladov cisla n na neparne scitance, t.j. kazdy scitanec je
neparne cislo. (Uvazujeme neusporiadane particie)
5.Uloha o nepriatelskych dvojiciach. Kolkymi sposobmi mozeme posadit za okruhly
stol n nepriatelskych dvojic tak, aby ziadna dvojica nepriatelov nesedela
vedla seba ? (stolicky su ocislovane)
6.Zostavte a dokazte Cantorovu vetu. Zdovodnite jej dosledky.
13.5.1999:
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.
---------------------------------------------------------------------
20.5.1999:
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|
----------------------------------------------------------------------------
25.5.1999
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
----------------------------------------------------------------------------
27.5.1999:
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:
-Ramseyova veta
-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.
2) Particie (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
----------------------------------------------------------------------------
10.6.1999:
PISOMNA:
1.) Nech An je pocet Sepernerovych systemov v n-prvkovej mnozine. Potom plati
2^(Tn) < An < C(2^(Tn),Tn) kde Tn=C(n, n div 2)
-jeto v tych prikladoch co rozdal.
2.) o hareme
Nech M={S1,S2,...,Sm} je system konecnych neprazdnych mnozin. Pozadujeme
aby kazda mnozina mala aspon jedneho reprezentanta (r>1), nadalej viac
pozadujeme aby reprezentanti boli rozni. Vyslovte nutnu a postacujucu
podmienku aby existoval system (r>1) roznych reprezentantov. Dokazte.
3.) Mnozina A ma n-prvkov, najdite pocet usporiadanych dvojic (X,Y),
X c A; Y c A; X n Y = 0, pomocou principu zapojenia a vypojenia.
4.) Nech S je mnozina navzajom disjunktnych intervalov (nie jednobodovych)
na priamke R. Dokazte za S je spocitatelna.
5.) Vyslovte a dokazte nutnu a postacujucu podmienku na to aby mnozina
bola spocitatelna.
6.) Dokazte ze plati: (|A|^|B|)^|C| = |A|^(|B|*|C|)
USTNA:
1.)
2k+1 listockov ocislovanych od 1..2k+1. Aky najvacsi pocet listkov mozme
vybrat tak aby ziadne vybrate cislo nerovnalo suctu dvoch vybranych cisel?
[[k+1 a bolo treba aj dokazat]]
2.) Konigova veta + dokaz
-----------------------------------------------------------------------
15.6.1999:
1) Nech G je bipartitny graf r-teho radu. Dokazte, ze existuje komletne
parenie. (tz.: Bipartitny graf <=> dva typy vrcholov napr. cervene a modre a
hrany existuju iba medzi cervanymi a modrymi nie medzi cervenymi a cervenymi
resp. modrymi a modrymi; r-teho radu znamena, ze z kazdeho vrchola vychadze
prave r hran. Priklad bipartitneho grafu radu 3 je K3,3 (t.j.:ten co nie je
rovinny))
2) Kolkymi sposobmi mozeme usadit n nepriatelskych dvojic v kine (t.z. do
radu), tak aby ziadna nepriatelska dvojica nesedela vedla seba.
3) Ukazat, ze plati: |Z x <0,1)|=R a ze |N||R|=|R|
4) Dokazat, ze K17 (t.z.: kompletny graf so 17 vrcholmi) zafarbeny troma
farbami obsahuje jednofarebny trojuholnik.
5) Nech mame dane realne cisla x1,x2,..,xn , take ze |xi|>1. Treba ukazat,
ze lubovolny interval dlzky 2 obsahuje maximalne
(n nad [n/2]) roznych suctov suma(i=1..n) ai*xi pricom ai je z {-1,1}
6) Dirichletov princip, dosledky, Konigova lema. Dokazat.
USTNA CAST:
Na ustnej sa ma spytal na nejake detaily z pisomky (proti nicomu vyrazne
neprotestoval a tak si myslim, ze by som mohol mat vsetko dobre (nie len ze
som pekny, sikovmy a mudry, ale aj skromny)). Asi sam mu zapacilo moje
riesenie 2 prikladu, ze sa ma spytal:
1) Nepriatelske dvojice za okruhlym stolom. (to iste ako 2, ale za okruhlym
stolom)
2) Manzelske pary za okruhlym stolom. (t.z.: Kolkymi sposobmi mozme za
okruhlim stolom usporiadat n manzelskych dvojic tak aby sa striedali muz,
zena, muz ..., a aby ziaden manzelsky par nesedel vedla seba)
3) Cantorova veta a dosledky.
----------------------------------------------------------------------------
3.6.1999
1. Dokazte, ze pocet rozkladov cisla n na navzajom rozne scitance je rovny
poctu rozkladov cisla n na neparne scitance, t.j. kazdy scitanec je neparne
cislo (uvazujeme neusporiadane particie).
2. Dokazte, ze ak m, n su cisla vacsie ako 2 a cisla R(m-1,n) a R(m,n-1) su
parne. Potom R(m,n)<R(m-1,n)+R(m,n-1)
3. Kolkymi sposobmi mozeme posadit za okruhly stol n manzelskych dvojic tak,
aby ziadna nesedela vedla seba a muzi sa striedali zo zenami.
4. Nech A, B su konecne mnoziny. |A|=n, |B|=m
a) ak B a B su disjunktne, potom |AuB|=n+m
b) |AxB|=m.n
c) |A^B|=n^m
5. Uvedte a zdovodnite algoritmus pre najdenie systemu roznych reprezentantov.
6. Ukazte, ze ak kazda mnozina ma r prvkov, r>=1 a kazdy prvok sa vyskytuje
prave v r mnozinach, tak potom existuje system roznych reprezentantov pre
mnoziny {S1, S2, ...., Sm}
USTNA:
1) Spernerova veta
3)
Nech E ={a ,a , a | a patri{0;1} pre i patriace 1,2,...,n}
n 1 2 n i ( <--- to su dolne indexy)
oznacme a~ (a ,a ,a ,...a ) (pre informatikov - n-bitovy vektor)
1 2 3 n
hovorime, ze a~ je mensie alebo rovne ako b~, ak
a je mensie alebo rovne ako b pre i patriace 1,2....n
i i
E s operaciou =< tvori ciastocne usporiadanu mnozinu
n
Najdite maximalny pocet n-bitovych vektorov,(podmnozin E ), ktore nie su
n
usporiadane.
--------------------------------------------------------------------------------
22.6.1999:
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.
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.
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
---------------------------------------------------------------------------
24.6.1999:
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.
---------------------------------------------------------------------------
UNKNOWN:
1) pocet permutacii n prvkov, pri ktorych a(i+1) nenasleduje bezprostredne za
a(i) pre i z {1,..,n-1}
2) k cisel v riadku: dokazte, ze sucet niektorych za_sebou_iducich je delit k
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.)
4) Nutna a postac. podmienka pre existenciu systemu VIACERYCH (aspon 2)
reprezentantov mnozin.
5) Zobrazenie f:N^3 -> N , bijektivne (najst)
6) Vyslovit a dokazat Konigovu vetu.
Prednášky sú zverejnené v súlade s ustanovením § 33 ods. 1 písm. c) zákona č. 618/2003 v znení neskorších prepisov a teda výhradne na informačné účely. Prosíme Vás aby ste všetky porušenia autorských práv bezodkladne ohlásili administrátorovi. Podmienky používania
