The Postal Owl

# 5. cvičení

## Konzultace po cvičení
Po příštím cvičení se můžeme přesunout na chodbu, snad najdeme místo u tabule (za dveřmi, na chodbě KAM 2. patro nebo na chodbě IUUK 3. patro) a můžeme tam konzultovat, kdokoliv byste chtěli něco probrat. Zejména otázky k relacím a funkcím.

Poznámky k dnešním úlohám:

## Konference

Správná odpověď je 21. Dojde se k ní principem inkluze a exkluze, kde si zadefinujeme $A_i$ jako množinu dní, kdy náš matematik obědval se známým $i$ pro $i=1,\dots, 5$. Potom $|A_i| = 10$, $|A_i \cap A_j| = 5$ pro každou $\{i,j\}$ t.ž. $|\{i,j\}| = 2$ (neboli $i \neq j$) atd.

Nakonec dostaneme výraz $5 \cdot 10 - \binom{5}{2} \cdot 5 + \cdots$, tedy hezký s kombinačními čísly. Je důležité si uvědomit, že nám zde velmi pomohlo to, že všechny průniky dvojic, trojic atd. se chovají stejně. To obecně nemusí platit a PIE to nepředpokládá, jen jsme zde měli štěstí.

## Prvočíselně vypadající

Opět PIE, ale zadefinujeme $A_1 = \{2,4,6,\dots\}$, $A_2$ jako násobky $3$ a $A_3$ jako násobky $5$ a pak počítáme, kolik je jejich sjednocení -- to nám dá všechna čísla, která jsou násobkem $2$, $3$ nebo $5$. Pozor na to, že jsme ale započítali i $2,3,5$, která jsou zároveň prvočísla, takže myslím, že odpověď není $92$ ale něco trochu jiného, každopádně idea je snad jasná, když tak se zeptejte dole komentářem :)

Více [zde](https://matematika.reseneulohy.cz/3472/prvociselne-vypadajici-cisla).

## Obdélníky v síti

Nejelegantnější řešení je říct, že máme $n^2$ možností, jak vybrat jeden roh a potom druhý roh musí být v jiném sloupci a jiném řádku, tedy $(n-1)^2$ možností pro druhý roh. Tedy dohromady $n^2 (n-1)^2$ možností, jak zvolit první a druhý roh. Ale tím jsme započítali každý obdélník $4$-krát a tedy je potřeba výraz podělit a dostaneme $\frac{n^2 (n-1)^2}{4}$.

## Podmnožiny bez sousedů

Toto je úloha, kterou jsem sám sebe i vás zmátl, za což se omlouvám.

Je pravda, že pomocí PIE lze dojít ke správné sumě -- zadefinujeme $A_i$ jako množinu podmnožin neobsahující dvojici $i, i+1$ a pak lze říct, že $|A_i| = 2^{n-2}$ a $|A_i \cap A_{i+1}| = 2^{n-3}$ a pro jiné dvojice je velikost průniku $2^{n-4}$ atd. Ale k uzavřenému vzorci takto nedojdete.

Lepší způsob je tento. Řekněme, že $a_n$ je počet "bezdvojčatových" podmnožin z $[n]$. Potom tyto množiny lze rozdělit do dvou typů: ty, které obsahují $1$ a ty ostatní. Pokud množina obsahuje $1$, tak nesmí obsahovat $2$ a potom obsahuje nějakou bezdvojčatovou podmnožinu $\{3,\dots, n\}$, tedy takových je přesně $a_{n-2}$. Pokud neobsahuje $1$, tak je to nějaká bezdvojčatová podmnožina $\{2,\dots,n\}$ a těch je $a_{n-1}$. Takže $a_n = a_{n-1} + a_{n-2}$ což vypadá podezřele jako Fibonacciho posloupnost, jen s jinými počátečními výrazy, protože $a_1 = 2$ (protože bezdvojčatová je $\emptyset$ i $\{1\}$) a $a_2 = 3$ (protože $\emptyset, \{1\}, \{2\}$).

Takže $a_n = F_{n+2}$ a tedy pokud chceme vzoreček pro $a_n$, zajímá nás vzoreček pro $F_n$ a ten není až tak jednoduché odvodit -- ale lze se to dozvědět např. na Kombinatorice a grafech 1 :)