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; kr<n)
  [(n-1)+k(r-1)]!
  --------------- =>to 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
      (0<r a kr<n) ... aspon myslim ze to tak bolo...

5. Dokazte ze ak A<>0 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