Zkouška Pangrác 27. 1. 2026

1. (a) [2 body] Definujte, kombinační číslo $\binom{n}{k}$ (včetně potřebných předpokladů ohledně čísel $n$ a $k$)

   (b) [8 bodů] Ukažte, že pro celá čísla $k$, $m$, $n$ splňující $k \le m$ a $k \le n$, platí:

$$\sum_{i = 0}^{k} \binom{m}{i} \binom{n}{k-i} = \binom{m+n}{k}$$

2. Pro $d \in \natnums$ definujeme graf $G_d$ takto: $V(G_d) = \{0,1,. ..,d\}^d$, tj. jeho vrcholy jsou všechny posloupnosti $d$ čísel, v nichž se vyskytují pouze čísla $0, 1, ..., d$. Dvě takové posloupnosti tvoří hranu právě tehdy, když se liší ve všech souřadnicích. Zde je například obrázek $G_2$:

   (a) [2 body] Definujte pojem barevnost grafu.

   (b) [4 body] Jakou barevnost má $G_2$? Odůvodněte dostatečně obě nerovnosti, tj. najděte nějaké optimální obarvení a dokažte, že nestačí méně barev.

   (c) [6 bodů] Jakou barevnost má $G_d$? Odůvodněte dostatečně obě nerovnosti. Tedy pro důkaz jedné nerovnosti popište přesně nějaké optimální obarvení (tj. když Vám někdo dá nějakou posloupnost délky $d$, ve které jsou jen čísla $0,...,d$, tak byste měli být snadno schopni říct, jakou jí přiřadíte barvu) a odůvodněte, že tato funkce splňuje podmínky obarvení. Abyste odůvodnili druhou nerovnost, tak dokažte, že nestačí méně barev.

   Spoiler: řešení 2b

   $G_2$ obsahuje cyklus o délce 3, a ten nelze obarvit méně než 3 barvami. (Pak ukážu příklad obarvení 3 barvami, obrázkem, tím dokážu, že existuje.)

3. [4 + 10 bodů] Definujte pojmy šířka a výška částečně uspořádáné množiny $(X, \le)$. Formulujte a dokažte větu o jejich vztahu (Věta o dlouhém a širokém).

4. (a) [2 body] Definujte pojem podmíněná pravděpodobnost

   (b) [4 body] Jaká je střední hodnota počtu šestek při deseti hodech běžnou šestistěnnou kostkou?

   (c) [6 body] Hodím dvěma běžnými šestistěnnými kostkami, černou a bílou. Určete pravděpodobnost, že součet hodů je alespoň sedm za podmínky, že na bílé kostce padlo sudé číslo.

   Spoiler: řešení 4b

   Elementární jev $\omega$ je desetice hodů 1-6, takže $|\Omega| = 6^{10}$.

   $$P(\{\omega\}) = \frac{1}{|\Omega|} = \frac{1}{6^{10}}$$

   Náhodná veličina $f_1$ je "počet 6 při 10 hodech".

   Jev $A_i$ definujeme jako v $i$-tém hodu padla $6$.

   $$P(A_i) = \frac{|A_i|}{|\Omega|} = \frac{1 \cdot 6^9}{6^{10}} = \frac 1 6$$ Takže:

   $$\underbrace{f_1(\omega)}_{\text{počet 6}} = \underbrace{I_{A_1}(\omega) + \dots + I_{A_{10}} (\omega)}_{\text{součet počtů 6 na všech indexech}}$$

   Takže $$f_1 = I_{A_1} + \dots + I_{A_{10}}$$

   Využijeme linearity střední hodnoty.

   $$\mathbb{E}(f_1) = \mathbb{E}(I_{A_1} + \dots + I_{A_{10}}) = \mathbb{E}(I_{A_1}) + \dots + \mathbb{E}(I_{A_{10}})$$

   Využijeme $\mathbb{E}(I_{A_i}) = P(A_i)$

   $$\mathbb{E}(f_1) = P(A_1) + \dots + P(A_{10}) = 10 \cdot \frac 1 6 = \frac 5 3$$

5. (a) [2 body] Definujte pojem bipartitní graf.

   (b) [10 bodů] Určete, pro které hodnoty $n \in \natnums$ existuje bipartitní graf, jehož obě partity mají velikost $n$, vsechny vrcholy jedné partity maji liché stupně a všechny vrcholy druhé partity mají stupně sudé. (Nápověda: vrcholy jedné partity nemusí mít všechny stejný stupeň.) Úplné řešení by mělo obsahovat dvě části:

   • Měli byste formulovat nějakou podmínku, kterou musí $n$ splňovat, a dokázat, že když ji nesplňuje, tak takový graf najít nejde.

   • Potom byste, pro každé $n$, které splňuje Vaši podmínku, měli najít graf $G_n$, který splňuje požadavky popsané výše.