(posts visible to all students)
Martin Koutecký — 2021-12-21 13:36 (380 days ago) — reply
## 11. cvičení ### Beztrojúhelníkový je $4$-obarvitelný Snadné - použijeme odhad na počet hran $|E| \leq 2|V| - 4$, ze kterého dostaneme, že tyto grafy jsou $3$-degenerované a tedy $4$-obarvitelné. ### Barevnost vnějškově rovinných Jednoduchý argument je tento: když si vezmu nakreslení vnějškově rovinného grafu t.ž. všechny vrcholy leží na vnější stěně a do ní přidám další vrchol a spojím jej se všemi existujícími vrcholy, dostanu rovinný graf. Když jej obarvím $5$ barvami, určitě nově přidaný vrchol má barvu, kterou nemá žádný další vrchol a tedy zbytek je obarven $4$ barvami. Dokonce lze dokázat, že vnějškově rovinné grafy jsou $3$-obarvitelné. "Jednoduchý" důkaz je vzít ten výše a použít větu o $4$ barvách (rovinné grafy jsou $4$-obarvitelné) a pak říct, že zbytek použije jen 3 barvy. To má háček, že věta o 4 barvách je velmi těžká a proto je dobré se jejímu použití vyhnout. Alternativní důkaz je ve [sbírce](https://matematika.reseneulohy.cz/3642/vnejskove-rovinne-grafy) -- ukáže se, že vnějškově rovinné grafy jsou $2$-degenerované. (Jedna skupina na cvičení téměř došla ke klíčovému pozorování, že duál vnějškově rovinného grafu, ve kterém si vezmu jen vrcholy odpovídající vnitřním stěnám, je strom a z toho už se to dá indukcí uhrát...) ### Žárovky Pravděpodobnost, že vezmu špatnou, lze určit jako součet pravděpodobností, že vezmu špatnou z první, z druhé a ze třetí krabice. Pravděpodobnost, že vezmu špatnou z první krabice je součin pravděpodobností výběru této krabice, což je $1/3$ a pravděpodobnost výběru špatné z této krabice, což je $4/10$, tedy $1/3 \cdot 4/10$. Podobně to určím pro další krabice. ### Hody kostkami Např. první část takto: v pokud třetí hod byl $1$, tak součet prvních dvou hodů byl $6$ a tedy to jsou možnosti $1,5$, $2,4$, $3,3$, $4,2$, $5,1$. Podobně si uděláme výčet když součet prvních dvou hodů byl $5,4,3,2$. Podíváme se a uvidíme, že je více možností, kdy je na první kostce $1$ než kdy je na první kostce $2$, tedy $1$ je pravděpodobnější. ### [Narozeniny](https://matematika.reseneulohy.cz/3502/stejne-narozeniny) ### [Populární verze Bertrandova paradoxu](https://matematika.reseneulohy.cz/3509/monty-halluv-problem) Pokud vás zajímají další úlohy, ptejte se :)