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$?