\documentclass[a4paper,10pt]{article}
\usepackage[czech]{babel}
\usepackage{amsmath, amsthm, amsfonts, amssymb} %basic mathematical fonts and symbols
\usepackage{graphicx} %inclusion of pictures
\usepackage{fnpct} %proper footnotes spacing after commas and dots
\usepackage{footnotebackref} 		%Footnotes reference back to the original text
\usepackage{hyperref}						%references are clickable
\hypersetup{colorlinks=true, linkcolor=red, urlcolor=blue, citecolor=blue, pdfpagemode=UseNone, pdfstartview=FitH, bookmarksopen=true}
\hypersetup{pdftitle=Discrete Mathematics}
\usepackage[utf8]{inputenc}
\usepackage[inline]{enumitem}

\newcommand{\abs}[1]{\left|#1\right|} % absolute value
\newcommand{\lnorm}[2]{{\left\|#2\right\|_#1}}% an l_p norm
\newcommand{\norm}[1]{\left\|#1\right\|} % a norm
\newcommand{\R}{\mathbb{R}} 	%real numbers
\newcommand{\Z}{\mathbb{Z}} 	%integers
\newcommand{\N}{\mathbb{N}} 	%natural numbers
\newcommand{\Q}{\mathbb{Q}} 	%rational numbers
\newcommand{\C}{\mathbb{C}} 	%complex numbers

%opening
\title{}
\author{}
\usepackage{fullpage}

\begin{document}
\section*{Třináctá série domácích úkolů\\z diskrétní matematiky}
\subsection*{Deadline: 22. 1. 2020; 23:59:59.99}

U každého příkladu nezapomeňte svá řešení pořádně zdůvodnit. 
\subsection*{Zadání}
\begin{enumerate}
\item\relax[4b] Náhodně vybereme kladné celé číslo $N$, přičemž pravděpodobnost toho, že vybereme $i$ je $2^{-i}$. Pak  hodíme $N$ kostkami. Označme $S$ součet čísel, která padla. Určete podmíněné pravděpodobnosti $P[N=2|S=5]$ a $P[S=4|N \text{ je liché}]$.
\item\relax[2b] Když vypravěč vypráví nějaký příběh, je 40\% šance, že si vymýšlí. To děti poznají v 70\% případů. Na druhou stranu, i když si nevymýšlí, tak mu zase v 20\% případů nevěří.
\begin{enumerate}
    \item Jaká je pravděpodobnost, že následující zážitek budou děti vypravěči věřit?
    \item Pokud děti vypravěčovi uvěřili, jaká je pravděpodobnost, že si nevymýšlel?
\end{enumerate}
(Poznámka: Rozhodli jsme se pro klidné zadání této úlohy. Pro aktuálnější verzi zaměňte slovo vypravěč za virus a slovo děti za test, atd.)
\item\relax[4b] Mějme graf $G$ s $n$ vrcholy. Uvažme následující náhodný proces. Prvně náhodně uspořádáme vrcholy $G$ (tak, že každé uspořádní má pravděpodobnost $1/n!$). Poté dle zvoleného uspořádání probíráme vrcholy $G$ a když na nějaký narazíme, zahodíme všechny jeho sousedy; tak pokračujeme, dokud nám zbývají nějaké nenavštívené vrcholy.
Spočtěte střední hodnotu počtu nevyhozených vrcholů a na základě tohoto výpočtu dokažte, že $G$ má nezávislou množinu\footnote{Množina vrcholů je nezávislá tehdy, když neobsahuje  žádné hrany.} velikosti alespoň\[\sum_{v\in V(G)}\frac{1}{\deg v+1}.\]
\item\relax[bonus+2] Nechť $n$ je prvočíslo. Dále je $\Omega=\{1,2,3,\ldots, n\}$ množina všech elementárních jevů, kde každý nastane s~pravděpodobností $1/n$. Nalezněte všechny dvojice nezávislých jevů.

\end{enumerate}


\subsection*{Pokyny}
Řešení posílejte na ppatak@seznam.cz s předmětem ``diskretka''.
Řešení mohou být v jakémkoli formátu (v ideálním případě pdf z \LaTeX{u}, ale stačí i naskenované, nafocené pdf, jpeg), 
snažte se, aby byla řešení čitelná.
U bonusových příkladů se Vám body započítavají, 
ale body z bonusového příkladu se nepočítají do celkového maximálního počtu bodů.
Příklady můžete zaslat i opakovaně, počítá se nejlepší dosažení počet bodů.
\end{document}
