Základní informace

Cvičení je (rozvrhově) určeno pro přednášku doc. Fialy, která se koná v pátek v 9:00.

Pokud cítíte problém s postupy z diskrétní matematice, navštivte předmět Matematické dovednosti. Pokud se vám nedaří s některými příklady pohnout, napište a zastavte se. Běžně bývám k dostižení, ale je dobré pokud o vás vím pár dní dopředu. Ideálním kontaktem na mě je email 1@2354knopkammffczcuni.

Pravidla udělení zápočtu

Je třeba splnit obě následující podmínky pro získání zápočtu:
  • alespoň polovinu bodů z písemek - bude 5 malých písemek (každá za 5 bodů) a jedna větší závěrečná (za 25 bodů), průběžné výseldky,
  • alespoň polovinu bodů z domácích úkolů - úkoly dostanete na cvičeních, celkově bude možno získat 50 bodů, průběžné výsledky.

Bonusové domácí úkol

zadání více méně LA, ale ze začátku je možné procvičít relace.

Domácí úkoly

První sada

odevzdávejte do pondělí 13.10. 15:40
  1. [1 bod] Napište rovnici, na které indukční krok bude platit, ale základní krok platit nebude. Tedy nebude existivat žádné $n$ pro které by rovnice platila.
  2. [2 body - příklad 7 ze cvičení] Dokažte, že každé přirozené číslo $n\in\N$ lze zapsat ve tvaru: $$n = \sum_{j = 1}^k F_{i_j}.$$ Tedy jako součet vybrané podposloupnosti Fibonacciho čísel. Kupříkladu číslo $42$ je možné zapsat jako následující součet $42 = 34 + 8$, tedy $k = 2, i_1 = 6$ a $i_2 = 9$, protože $F_6 = 8$ a $F_9 = 34$.
  3. [2 body - příklad 1d za cvičení] Dokažte, že pro každé přirozené čislo $n\in\N$ platí: $\sum_{i = 1}^n i^2 = \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6}.$

Druhá sada

odevzdávejte do pondělí 20.10. 15:40
  1. [2 body] Nalezněte relaci (nebo dokažte, že taková neexistuje), která:
    1. Je slabě antisymetrická i symetrická zároveň.
    2. Je slabě antisymetrická a není symetrická.
    3. Není slabě antisymetrická a je symetrická.
    4. Není slabě antisymetrická ani není symetrická.
  2. [2 body] Kolik je relací? (nezapomeňte napsat zdůvodnění)
    1. Symetrických
    2. Slabě anti-symetrických
  3. [1 bod] Dokažte, že $F_{4n}$ je dělitelné třemi pro každé $n\in\N$. Kde $F_i$ značí $i$-té Fibocciho číslo a $F_1 = F_2 = 1$.

Třetí sada

odevzdávejte do pondělí 27.10. 15:40
  1. [3 body] Definujme si rekurzivně mocninu relace $R$ na množině $X$ následovně: $R^n = R \circ R^{n-1}$ pro $n \gt 1$ a $R^1 = R$.
    1. Ukažte, že pokud množina $X$ je konečná, tak potom existují $m,n\in\N$ různá, pro která platí $R^n = R^m$.
    2. Nalezněte relaci, pro kterou platí $m \ge n$ a zároveň $m \neq n+1$.
    3. Je tvrzení z prvního bodu platné i pro nekonečnou množinu $X$?
  2. [2 body] Kolik existuje pořadí písmen $A,B,D,E,I,K,M,N,R,Ů,Z$ takových, že po vynechání některých písmen nevznikne ani jedno ze slov ARZEN, DRAK, DŮM, DŮRAZ.

Čtvrtá sada

odevzdávejte do pondělí 3.11. 15:40
  1. [1 bod] Rozhodněte, zda pro relace $X$ a $Y$ na množině $K$ platí, že jsou-li $X$ i $Y$ ekvivalence, potom i $X\circ Y$ je ekvivalence.
  2. [2 body] Rozhodněte, zda následující relace na $\N$ jsou ekvivalence a pokud ano, určete třídy ekvivalence )popište je):
    1. $xR_p y$ právě když $p|(x-y)$, pro $p\in\N$ prvočíslo (pevné),
    2. $xRy$ právě když $\exists z\in\N$ takové, že $z|y$ a zároveň $z|x$. Co by se stalo, pokud navíc požadujeme $z \lt 1$?
  3. [2 body] Kolika způsoby je možné umístit $6$ červených, $6$ zelených a $6$ modrých kamenů na šachovnici $5\times 5$ tak, že některý řádek nebo sloupec je celý pokryt kameny stejmé barvy? Na každé políčko mohu umístit jeden nebo žádný kámen.

Pátá sada

odevzdávejte do pondělí 10.11. 15:40
  1. [3 body] Dokažte vztah $$š(n) = n! - nš(n-1) - \binom{n}{2}š(n-2) - \cdots - \binom{n}{n-1}š(1) - 1,$$ kde $š$ je funkce šatnářky.
  2. [2 body] Dokažte rekurentní vztah $š(n) = (n − 1)[š(n − 1) + š(n − 2)].$

Šestá sada

odevzdávejte do pondělí 24.11. 15:40
  1. [3 body] Kolik existuje $3$-ciferných čísel tvořených číslicemi z množiny $\{1,3,5,7,9\}$ bez/s opakování(m)? Jaký je součet těchto čísel?
  2. [2 body] Kolika způsoby lze postavit do řady 5 vodníků a 7 čarodějnic, že żádní dva vodníci nestojí vedle sebe? Kolik je możností, kdybychom je za stejných podmínek měli stavět do kruhu?

Sedmá sada

odevzdávejte do pondělí 01.12. 15:40
  1. [2 body] Buďte $A$ a $B$ náhodné jevy s pravděpodobnostmi $P(A) = 1/3, P(B) = 1/4$ a $P(A\cap B) = 1/10)$. Označme $\overline{X}$ doplňkový jev k jevu $X.$ Určete $P(A|B), P(B|A), P(\overline{A}|B), P(A|\overline{B}).$
  2. [3 body] Mějme kostky tvaru krychle. Řekneme, že kostka $K$ je \emph{lepší} než kostka $L$, pokud při hodu těmito kostkami padne na kostce $K$ větší číslo než na kostce $L$ s pravděpodobností alespoň $1/2.$ Zkonstruujte (nikoli nutně fyzicky) trojici kostek $A,B,C$, pro které bude platit, že $A$ je lepší než $B$, $B$ je lepší než $C$ a $C$ je lepší než $A$. Zamyslete se nad tím, kterou očekávanou relační vlatnost tímto potlačujeme.

Osmá sada

odevzdávejte do pondělí 08.12. 15:40
  1. [3 body] Dokažte, že v každém souvislém grafu $G$ existují dva vrcholy $u, v$ takové, že $G\setminus \{u\}$ (graf bez vrcholu $u$ a všech hran s ním incidentních), $G\setminus \{v\}$ $G\setminus \{u,v\}$ jsou souvislé grafy.
  2. [2 body] Najděte souvislý graf na 3 vrcholech takový, že kažká mocnina jeho matice sousednosti obsahuje alespoň jednu nulu. Nalezněte takový graf pro všechna $n\ge3.$

Devátá sada

odevzdávejte do pondělí 15.12. 15:40
  1. [5 bodů] Kouzelník a asistentka
    Kouzelník provádí následující kouzlo. Má běžný karetní balíček obsahující $52$ karet (tedy $13$ od každé barvy). Náhodný divák z publika si náhodně vybere 5 karet a předá je kouzelníkově asistence. Asistentka poté kouzelníkovi ukáže 4 z těchto karet, kouzelník pak následně pomocí svých magických schopností řekne, která karta je ta pátá (tu si nechala asistentka).
    Ukažte, že v tomto triku není nic magického.