# Zkouška Kantor 14. 1. 2025
1. *[9 bodů]* Kolik čísel **zbyde** z množiny $\{1, \ldots, 1000\}$ po vyškrtání všech **násobků** čísel $6, 7, 8$?

2. 
    (a) *[2 body]* Nechť $(X, \preccurlyeq)$ je nějaká částečně uspořádané množina. Doplňte definice *nejmenšího prvku* a *minimálního prvku* částečně uspořádané množiny $(X, \preccurlyeq)$:  
        $x \in X$ je *nejmenší prvek* č.u.m. $(X, \preccurlyeq)$, pokud…  
        $x \in X$ je *minimální prvek* č.u.m. $(X, \preccurlyeq)$, pokud…

    (b) *[3 body]* Nechť $W$ je množina všech přirozených čísel $n$ tvaru $n=2^a \cdot 5^b$, kde $a, b$ jsou celá čísla taková, že $a \geq 0, b \geq 0$ a $1 \leq a+b \leq 15$. (Například $25=5 \cdot 5$ a $40=5 \cdot 2^3$ a $32768=2^{15}$ do množiny $W$ patří, ale $1$ do $W$ nepatří a $6 = 3 \cdot 2$ také ne.) Kolik má množina $W$ prvků?

    (c) *[3 body]* Nechť ${\preccurlyeq}w$ značí relaci dělitelnosti na množině $W$ (definované výše), t.j. pro $x, y \in W$ máme $x\:{\preccurlyeq}w\:y$ právě tehdy, když $y$ je násobek čísla $x$. Napište nějaký nejdelší řetězec v množině $(W, {\preccurlyeq}w)$.

    (d) *[4 body]* Najděte nějaký netriviální dolní odhad pro velikost největšího antiřetězce (nezávislé množiny) v množině $P = (W, {\preccurlyeq}w)$ definované výše (t.j. nerovnost $\alpha(P)\geq\ldots$). Toto můžete udělat buďto přímo, nebo třeba s použitím nějaké věty z přednášky.

3. *[4+10 bodů]* **Formulujte** a **dokažte** větu, která nám říká, jaký *nejvyšší počet hran* může mít **rovinný** graf na $n$ vrcholech.

4. Nechť $n$ je přirozené číslo větší než $1$. **Definujeme** graf $G_n$ takto:  
Jeho **vrcholy** jsou všechny množiny $A \subset \{1, \ldots, n\}$, pro něž platí $|A|\lt n$.  
Dvě z nich jsou spojeny **hranou** právě tehdy, když jsou **disjunktní**.  
Například pro $n = 3$ dostaneme tento graf:

    (a) *[3 body]* Pro která $n$ je graf $G_n$ **souvislý**? Odpověď dostatečně zdůvodněte.

    (b) *[4 body]* Nechť $A \subset \{1, \ldots, n\}$ je množina velikosti menší než $n$. Jaký je **stupeň vrcholu**, který odpovídá množině $A$? (Závisí nějak na velikosti množiny $A$, na $n$, nebo případně na něčem jiném)?

    (c) *[3 body]* Pro která $n$ je graf $G_n$ **eulerovský**? Odpověď dostatečně odůvodněte.

5. 
    (a) *[2 body]* Nechť $X$ je náhodná veličina na pravděpodobnostním prostoru $(\Omega, \mathcal{P}(\Omega), P)$. **Napište vzorec** pro výpočet **střední hodnoty**. Můžete si vybrat: buďto ten, který střední hodnotu **definuje**, nebo praktičtější vzorec, podle kterého se stření hodnota **běžně počítá**.  
        $\mathbb{E}(X)=$

    (b) *[3 body]* Hodíme kostkou a definujeme náhodnou veličinu $X$ takto: pokud nám padla šestka, tak $X=1$, a pokud padlo jiné číslo, tak $X=0$. Spočítejte **střední hodnotu** náhodné veličiny $X$. Výsledek dostatečně odůvodněte, jen číslo nestačí.

    (c) *[5 bodů]* Nyní hodíme kostkou stokrát a označíme $Y$ počet jedniček, které nám v těch sto hodech padly (tedy $Y$ je náhodná veličina, která nabývá hodnot mezi $0$ a $100$). Spočítejte **střední hodnotu** náhodné veličiny $Y$. Svoje řešení dostatečně odůvodněte.

    (d) *[3 body]* Jaká je pravděpodobnost, že pro náhodnou veličinu $Y$ definovanou výše máme $Y = 10$?