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?