# 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}$$

   <{Details(Spoiler: řešení 1a)}>
   Pro $n,k \in \natnums_0$, kde $n \ge k$, je kombinační číslo $\binom{n}{k}$ rovno $\frac{n!}{k! (n-k)!}$
   <{/Details}>

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$:
![G2](/NDMI002/Zkouška%20Pangrác%2027.%201.%202026/G2)

    (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.

   <{Details(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.)
   <{/Details}>


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.

   <{Details(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$$
   <{/Details}>

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.