Subject: DM 14.1.99 Zdraaavstvujte! Neviem ci uz niekto poslal diskretnu matiku z 14.1.99 (moj mail server died), ale ako sa hovori, "Ako sa do hory vola, matka mudrosti", idem na to: 1. Dokazte, ze pocet kombinacii s opakovanim k-tej triedy z n prvkov je rovny n+k-1 nad k, zostrojte bijekciu medzi komb. s opak. k-tej triedy z n prvkov a k tej triedy bez opakovania z n+k-1 prvkov. 2. n! > (n/e) Matematickou indukciou (to je zadanie, nie moj postup) 3. n Suma ((-1)^k-1)/k (n) = 1 + 1/2 + ... + 1/n k=1 (k) 4. |A| = n; X je podmnozina A, Y je podmnozina A; Najdite pocet dvojic (X, Y) takych, ze plati |(X-Y) zjednotenie (Y-X)| = 1 (pre zaujimavost je to symetricka diferencia, ze?) 5. Vyslovte a dokazte C-B vetu. (otazky typu: "Ako su definovane mnoziny C a B su tu nemiestne a nedoporucujem klast ich na skuske ;) 6. Najdite najv. koeficient (a+b+c)^10 ; (a+b+c+d)^14 -------------------------------------------------------------------- Takze co bolo dnes na diskeretnej matematike ked uz mame taky pekny datum. 1. Nech A je mnozina |A|=n a X<=A a Y<=A najdite pocet usporiadnenych dvojic (X,Y) takych ze plati A prienik B = 0 2. Dokazte ( n )n n!<= 2 (---) ( 2 ) 3. Zostrojte zobrazenie z <0,1> na (0,1) 4. a) Kolkymi sposobmi mozeme rozdelit n rovnakych predmetov medzi k ludi b) to iste ale kazdy musi dostat r (specialne r=1) 5. Dokazte ze ak A<>0 tak neexistuje zobrazenie f:A->0 6. Nech k patri N a B je taka mnozina ze |B|=n potom pocet kombinacii bez opakovania k-tych tried prvkov mnoziny B je rovny 1 k-1 ( n ) --- |-| (n-j) = ( ) k! j=0 ( k ) |-| symbolyzuje tieco ako sumu ale nasobenie ( pi ?? ) Celkom lahke. A teraz co som dostal na 3-hodinovu ustnu odpoved. 1. Bijekciu medzi komibaciami s opakovanim k-tej triedy z n roznych prvkov a kombinaciami bez opakovania k-tej triedy z n+k-1 roznych prvkov. 2. n - Francuzov m - Anglicanov a zvysok si domyslite 3. T(n) - pocet postupnosti z 0 a 1 dlzky n takych ze ziadne dve 1 nestoja vedla seba. Dokazat: T(n)=T(n-1)+T(n-2) vyjadrit T(n) pomocou kombinacnych cisiel -------------------------------------------------------------------- dna 14.1.99 boli tieto priklady: 1. dokaz, ze pocet komb. s opak k-tej triedy z n prvkov je / n+k-1\ [ ] \ k / plus zostroj bijekciu medzi komb. s opak. k-tej triedy z n prvkov a komb. bez opak. k-tej triedy z n+k-1 prvkov. 2. dokaz matem.induk.: n!>(n/e)^n 3. dokaz, ze : n --- \ / n \ / (-1)^k /k [ ] = 1+1/2+1/3+ ... +1/n --- \ k / k=0 alebo nieco take 4. A je mnozina a plati [A]=n nech X,Y su podmnoziny A. Kolko je uspor. dvojic (X,Y) takych, ze plati: [ (X-Y) v (Y-X) ] = 1 v=zjednotenie 5. vyslov a dokaz C-B vetu (to nie je rozdiel mnozin C,B to je Cantor-Bernsteinova veta, dobre?) a tiez tu lemu k tomu 6. aky bude najvacsi koef. vo vyrazoch: a) (a+b+c)^10 b) (a+b+c+d)^14 ----------------------------------------------------------------------- Dnes som stravil asi 6 hodin v dobre chladenej XI (akv.) u pana docenta Rozhodol sa ze dnes da premierove priklady - to znamena ze az na jeden take este asi neboli Tu su: 1. n 1 1 (2n-1)! suma=--------.----------- = ------------ k=1 (k-1)!k! ((n-k)!)^2 (n!(n-1)!)^2 2. (dost lahky nepamatam si zadanie) n tice z 1 a 0 kde nemozu byt dve 1 vedla seba. Napis vzorec pre T(n)= pocet n-tic plus dokaz ze T(n+1)=T(n)+T(n-1) 3. Nieco o tranzitivnom uzavere 4. (n/k)^k < (n nad k) < (3*n/k)^k 5. nieco okolo permutacii a ich urcovanie pomocou cyklov 6. Klasika pre romantikov: Mame n Anglicanov a m Francuzov. Kolkymi sposobmi ich mozeme postavit do radu ked pri sebe musia stat aspon dvaja krajania. ----------------------------------------------------------------------- Cafte !! Vcera 7.1. boli na skuske z diskretnej matiky tieto priklady: 1. Dokazte, ze ak B{} tak ani mnozina zobrazeni z A do B nie je {}. {} - je prazna mnozina. 2. Dokazte: ---- / n \ 4*\ | | = n (n/2)+1 n*Pi / | 4k | = 2 + 2 *cos ---- ---- \ / 4 k 3. Dokazte tu lemu, co sa pouziva pri dokaze Cantor-Bernsteinovej vety. Ta s tymi mnozinami A1,A2,B1,B2. 4. Najdite minimalnu hodnotu suctu: s ----- / ni \ \ | | pricom n = n1 + n2 + .........+ ns / | k | ----- \ / i=1 5. Zistite, ci je kvantifikovany vyrok tautologia pre lubovolne vyr. formy a,b.... presne znenie si uz nepamatam.... Najdete to v tych prikladoch, co nam dal Toman.... 6. Nech A je podmn. B(n,l) a B mnozina vsetkych vektorov z B(n,k) porovnatelnych aspon s jednym vektorom v A. Dokazte, ze |A| |B| B(n,i) obsahuje tie vektory z {0,1}^n, --- <= --- ktore obsahuju prave i jednotiek; /n\ /n\ ak a=(a_1,...,a_n), b=(b_1,...,b_n), \l/ \k/ tak a<=b, ak a_i<=b_i, pre vsetky i; a,b su porovnatelne, ak a<=b alebo b<=a Inac skuska bola hrozne od veci..... Pisomka od 9:00 do 11:00 (asi). Skoro cely cas bol mimo.... Potom zacal opravovat pisomky . Na "ustnej" si nas postupne volal dnu, a dal ratat tie veci, co sme na pisomke nevedeli.... (Dal ratat aspon dva - stvrty a siesty).. Vcelku radim na pisomke napisat co najviac...(mnozstvo, nemusi byt vsetko spravne), nech to vyzera, ze toho mate vela.... On sa na riesenia skoro ani nepozeral.... Treba vediet ratat priklady z tych 6-tich papierov.(Hlavne sumy komb. cisel); Uspesnost: 7/15 (mohla by byt aj lepsia) To najlepsie na koniec: Odchadzali sme zo skusky nieco po pol piatej. (Vela z nas tam teda bolo 7 hodin) --------------------------------------------------------------------------- ------ Subject: Dm 6.2.!!!! Neviem, ci to je ono, ale dns na skuske Tominovi trcali dajake papiere s datumom 6.2.1998 a nejakymi prikladmi; co som zachytil (nebolo to moc citatelne: m 1. Dokaz: (n+m) = suma (n+k-1) ( m ) = k=0 ( k ) 2. Zadanie nebolo citatelne, ale nieco: ( 2^(1/2)+ 3^(1/4) )^100 ; tajny tip, urci cleny s racionalnymi koeficientami. (Ten vztah v ludskej reci - odmocnina z 2 + stvrta odmocnina z 3 a to cele na 100). Inac dnes mal dobru naladu uplne trapne priklady, spravili aj taki, co neboli ani raz na prednaske a nevedeli vobec teoriu (napr. Vasicek, Vrbovsky) Najtazsi bol asi: mate n rovnakych predmetov rozdelit medzi k ludi, ked kazdy ma dostat minimalne r predmetov. Kolko je sposobov? (r>0; krto je riesenie. (k-1)! (n-kr)! Potom spec. pripad r=0 a r=1, dokaz, ze neexistuje najdi zobrazenie: A->B, ak A<>{} a B={}, potom dokaz, ze kombinacii bez opakovania je n nad k, a najdi proste zobrazenie <0;1> -> (0;1). zatial cauko, uzivajte si pripravu, ja uz mam volno... Vr. ------ Subject: dm 28/1 Nazdar spoluziaci !!! Dnes boli na pisomke z diskretnej tieto priklady: 1. Nech A je mnozina. |A|=n. X <= A a Y <= A. Najdite pocet usporiadanych dvojic (X,Y) takych ze plati |(X-Y) U (Y-X)|=1 2. Dokazte ze plati n!<=2(n/2)^n 3. Zostrojte sproste zobrazenie <0,1> na (0,1) 4. a) kolkymi sposobmi mozme rozdelit n rovnakych predmetov medzi k ludi ? b) to iste ale pozadujeme aby kazda osoba dostala minimalne r predmetov (00 tak neexistuje zobrazenie f:A->0 6. Nech K<=N a nech B je taka mnozina ze |B|=n. Potom pocet kombinacii bez opakovania k-tej triedy z prvkov mnoziny B je rovny ... (ten ...sialeny vzorec je v poznamkach pri vete o kombinaciach bez opakovania). Potom na ustnej som dostal tieto temy: 1. rovnost zobrazeni (vsetko okolo toho) 2. priklad: Kolkymi sposobmi mozme do matice m x n zapisat cisla 1 a -1 tak, aby sucin cisel bol v kazdom riadku i stlpci +1 ??? (vysledok je 2^((n-1)(m-1)) ). Kua, chuapi, mam to za 3 !!! Ale som rad ze je to(man) za mnou... CAUTE !!! Peter P.S.: Sorry vsetci co to uz mate spravene, ze vas s tymto otravujem, ale este je plno ludi co to este nemaju a tak si mozte vy*rat oko!!! :-)))))) ------ Subject: Diskretna matika. 1. Urcte pocet kombinacii s opakovanim a najdite bijekciu medzi kombinaciami s opakovanim z n prvkov a kombinaciami bez opakovania z n+k-1 prvkov. 2. dokazte MI ( n )n n!>( --- ) ( e ) 3.dokazte sumu - 6. priklad z tych 8 sum co boli na jednom tom papieri, ktore nam dal Toman. 4.Nech A je neprazdna,|A|=n, nech X,Y su podmn. A, nech X prienik Y=prazdna mnozina, kolko je vsetkych usp.dvojic (X,Y) ? {3 na n} 5.Cantor-Bernsteinova veta a ta lema k nej. 6.aky bude najvacsi koeficient vo vyraze a.) 10 (a+b+c) b.) 14 (a+b+c+d) Vela stastia ! Brano. ------ Subject: Re: Diskr.mat. 14.1. Toman Drahy priatelia, na tejto skuske sa zrejme Toman rozhodol, ze ma ustve - skusal ma takmer 5 hodin. Priklady, ktore som mal na ustnej casti (nieco je podobne ako na pisomnej) 1. Dokazte, ze 4*suma n nad 4k = 2^n + 2^(n/2)+1 * cos(n*pi)/4 2. Mame n Anglicanov a m Francuzov. Kolkymi sposobmi ich mozme rozostavit, aky nebol ziaden Anglican ani ziaden Francuz osamoteny - tj. stoji vedla neho este jeden sukmenovec. 3. Tranzitivny a reflexivno-tranzitinvy uzaver relacie, dokazy 4. Dokaz, ze ak B nie je prazdna mnozina, potom ani mnozina zobrazeni z A do B nie je prazdna 5. Ak je A neprazdna mnozina a B prazdna, tak neexistuje zobrazenie z A do B 6. Aky je pocet kombinacii s opakovanim k-tej triedy z n prvkov 7. Najdi bijekciu medzi kombinaciami s op. k-tej triedy z n prvkov a kombinaciami bez op. k-tej triedy z n+k-1 prvkov. A to bolo vsetko. Doctor ------ Subject: Diskr.mat. 8.1.98 ustna cast Posielam vam teraz pre zmenu, co som dostal od pana Tomana v ustnej casti skusky: Dokaz: n --- \ / (-1)^k (1/(k+1)) (n nad k) = (1/(n+1)) (da sa dokazat priamo) --- k=0 n --- \ / ((-1)^(k-1))/k (n nad k) = 1+1/2+...+1/n (na toto treba indukciu) --- k=1 No a potom dava nejake doplnujuce veci k pisomke, napr. na pisomke sme dokazovali, ze prazdne zobrazenie je zobrazenie, a on mi dal este navyse dokazat, ze je bijektivne (celkom primitivny dokaz :) A potom nasleduju rydzo teoreticke otazky: Definuj kombinacie s opakovanim (cez zobrazenia, samozrejme). Definuj rozklad mnoziny. V akom su vztahu rozklad mnoziny a relacia ekvivalencie, vyslov zakladne vety a dokaz (tie vety - ide o dve vety: o rozklade indukovanom relaciou a o relacii indukovanej rozkladom). No a potom nasleduje uz iba zapis do indexu (pripadne nie)... Zdravim Emil ------ Subject: Diskr.mat. 8.1.98 Toman Tieto priklady boli na pisomke z diskretnej matiky 8.1.98 s Doc. Tomanom: 1. Dokazte, ze plati 0!=1 2. Zostrojte proste zobrazenie mnoziny A na mnozinu B, ked A={(x,y) patri do RxR, x^2+y^2<=1},B=<-1,1>x<-1,1> 3. Dokazte, ze plati (n nad k)=(n-2 nad k-2)+2*(n-3 nad k-2)+...+ +(n-k+1)(k-2 nad k-2) 4. Nech k,n1,...,nk patria do N+; n1+...+nk=n Nech |A|=n,|B|=k a B={b1,...,bk} Dokazte: Ak Pn1,...,nk je pocet tych surjekcii A na B, ze plati |f^-1({bj})|=nj, j=1,...,k, tak Pn1,...,nk = n!/(n1!.n2!. ... .nk!) 5. Zistite, ci nasledujuci kvantifikovany vyrok je tautologia pre lubovolne vyrokove formy a(x), b(x): Existuje x[a(x)=>b(x)]=>[Pre vsetky x a(x)=>Existuje x b(x)] 6. Dokazte, ze pocet kombinacii s opakovanim k-tej triedy z n roznych prvkov je (n+k-1 nad k). Vela stastia Zdravim Emil ------ Subject: Diskretna zimny s. 96/97 (Toman) Na zaciatok hadam staci, co sa pytal priatel Toman vlani na skuske (pisomka) 1) Dokazte, ze plati k --- \ / n \ / m \ = / m + n \ / \ r / \ k - r / = \ k / --- r=0 2) Najdite maximalnu hodnotu suctu s --- \ / n \ pri podmienkach / \ ki / 0 <= k1 < k2 < ... < ks <= n --- 1 <= s <= n + 1 i=1 3) Dokazte, ze karteziansky sucin troch mnozin A = { E }, B = { E }, C = { { E } } nie je asociativny. [ E je prazdna mnozina ] 4) Nech X je mnozina, Fi je niektory rozklad mnoziny X, T je relacia ekvivalencie na X. Nech Fi(T) je rozklad indukovany relaciou T a T(Fi) relacia ekvivalencie indukovana rozkladom Fi. Dokazte, ze Fi = Fi(T(Fi)) a T = T(Fi(T)) ! 5) Zostrojte proste zobrazenie mnoziny A na mnozinu B, ked A = { (x, y) parti R^2, x^2 + y^2 <= 1 } a B = <-1, 1> x <-1, 1>. 6) Nech f: X -> X. Potom a) f je surjekcia <=> existuje take g: X -> X, ze f @ g = Ix (identita) b) f je injekcia <=> existuje take g: X -> X, ze g @ f = Ix P.S. Vcelku sa Ti oplati vytvorit si na taketo spravicky vlastny priecinok Humor