\documentclass{article}
\usepackage{slovak}
\usepackage{a4wide}
\usepackage{verbatim}
\usepackage{amssymb}  % kvoli \square
\usepackage{amsfonts} % kvoli \mathbb
\parskip 12pt

% Ma pisat aj riesenia? 
% \def\pisriesenia{1}
\def\odpovednie{nie }
\message{Maju byt vo vystupe aj riesenia? Ak nie, odpovedz `nie', ak ano, stlac ENTER: }
\read-1 to\odpoved
\ifx\odpoved\odpovednie\else\def\pisriesenia{1}\fi

% makra: jednoducha matika
\def\eps{\varepsilon}
\def\then{\Rightarrow}
\def\sgn{\mathop{\rm sgn}\nolimits}

% makra: ulohy
\newcounter{cntuloha}
\newcounter{cntpisomka}
\def\uloha{\noindent\stepcounter{cntuloha}{\bf \arabic{cntuloha}. }}
\def\pisomka{%
\ifnum\thecntpisomka >0 \bigskip\hrule\fi%
\stepcounter{cntpisomka}%
\setcounter{cntuloha}{0}}

% makra: vypisujeme aj riesenia?
\ifx\pisriesenia\undefined
 \let\riesenie=\comment
 \let\riesenie=\comment
 \let\endriesenie=\endcomment
\else
 \newenvironment{riesenie}[1][1]{%  nepovinny parameter, ak dame 0, nepise \\ za Riesenie
 \begin{center}\begin{minipage}{0.8\textwidth}%
 {\sl Rie�enie.}\ifnum #1=1\\\fi}{\end{minipage}\end{center}}
\fi

% makra: slovenske uvodzovky
\catcode`\"=13
\def "{\begingroup\clqq\def "{\endgroup\crqq}}
\def\dospecials{\do\ \do\\\do\{\do\}\do\$\do\&%
  \do\#\do\^\do\^^K\do\_\do\^^A\do\%\do\~\do\"}

% a ideme na vec
\begin{document}
\centerline{\Large\sc Diskr�tna matematika -- pr�klady zo sk��ok v lete} 
\medskip
\centerline{\large \copyright Mi�oF.}
\bigskip

\pisomka

\uloha
Dokaz, ze plati:
$$ { (n+r-1)! \over r! } - { n \over 1 }\cdot { (n+r-3)!\over (r-2)! }
   + {n(n-1) \over 1.2 }\cdot {(n+r-5)! \over (r-4)!} - \cdots = 
   {n!(n-1)! \over r!(n-r)!} $$

\begin{riesenie}
Prede�te obe strany $(n-1)!$, napravo ostane ${n\choose r}$, �o s� v�etky
kombin�cie $r$ prvkov z $n$. Na�avo ostane:
$$ {n+r-1 \choose r} - { n \choose 1 }\cdot { n+r-3\choose r-2 }
   + {n \choose 2 }\cdot {n+r-5 \choose r-4} - \cdots $$ 
Potrebujeme uk�za�, �e je to to ist�. Spo��tajme teda kombin�cie $r$ prvkov
z $n$ pomocou inkl�zie a exkl�zie. ${n+r-1 \choose r}$ s� v�etky 
kombin�cie s opakovan�m, od nich potrebujeme od��ta� tie, v ktor�ch sa
nie�o opakuje. �len ${n\choose k}\cdot {n+r-1-2k \choose r-2k}$ 
predstavuje kombin�cie s opakovan�m, v ktor�ch sa aspo� $k$ prvkov 
opakuje -- vyberieme, ktor�ch $k$ sa opakuje, ka�d� z nich vezmeme
dvakr�t a zvy�n�ch $r-2k$ prvkov vyberieme �ubovo�ne.
\end{riesenie}

\uloha
Nech $A$,$B$ su dve konecne mnoziny, $k\geq 1$ prirodzene cislo.  Medzi $A$ a $B$ je ustanoveny
mnohoznacny vztah, ze kazdemu prvku mnoziny $A$ zodpoveda prave $k$ prvkov mn. $B$ a naopak kazdemu prvku
mn. $B$ zodpoveda prave $k$ prvkov mn. $A$. Dokaz, ze medzi $A$ a $B$ existuje bijekcia (kazdemu prvku je
potom priradeny prvok v sulade s mnohoznacnym vztahom).

\begin{riesenie}
Zostrojme bipartitn� graf s part�ciami $A$ a $B$. Zadanie trochu kostrbato hovor�, �e ka�d� vrchol
tohto grafu m� stupe� $k$. Potom z Hallovej vety v �om existuje perfect matching = bijekcia.

Podrobnej�ie, zoberme �ub. mno�inu $M\subseteq A$. Z nej vych�dza $|M|k$ hr�n. Do ka�d�ho vrcholu v
$B$ vedie najviac $k$ hr�n, preto mno�ina $M$ m� aspo� $\lceil |M|k/k\rceil=|M|$ susedov a podmienka
z Hallovej vety je splnen�.
\end{riesenie}

\uloha
Dokaz odhad poctu Spernerovych systemov $A_n$, pricom $T_n={n\choose \lfloor n/2\rfloor}$:
$$ 2^{T_n} < A_n < {2^{T_n} \choose T_n} $$

\begin{riesenie}
Prv� nerovnos�: Zoberme Spernerov syst�m, ktor� obsahuje pr�ve v�etky 
podmno�iny $\{1,\ldots,n\}$, ktor� maj� pr�ve $\lfloor n/2 \rfloor$ prvkov.
Potom aj ka�d� jeho podmno�ina je Spernerov syst�m, tak�chto Spernerovych syst�mov
je pr�ve $2^{T_n}$, zjavne existuj� aj in� Spernerove syst�my, preto je nerovnos� 
ostr�.
\end{riesenie}

\uloha 
Dokaz, ze v dvojfarebnom $K_n$, $n\geq 10$ existuje aspon ${n^2\over 2}-{19n \over 2}+61$
jednofarebnych trojuholnikov.

\uloha
Nech $A$,$B$ su konecne mnoziny, $|A|=n$, $|B|=m$. Dokaz:
\begin{itemize}\itemsep -3pt
\item[a)] ak $A$ a $B$ su disjunktne, tak $|A\cup B|=n+m$
\item[b)] $|A\times B|=nm$
\item[c)] $|A^B|=n^m$
\end{itemize}

\uloha
Nech $f$ je zobrazenie z $\mathbb N\times \mathbb N$ do $\mathbb N$ take, ze 
$\forall m,n \in\mathbb N;~ f(n,0)=n \land f(n,m+1)=f(n,m)+1$. Dokaz $f(m,n)=m+n$.

\pisomka

Na teorke daval klasiky -- $A(r)$, grafy, Ramseya, Halla, postupnosti,
nepriatelov... Ak mal niekto 4 priklady viac-menej dobre, dostal este
jeden a ak to mal 100\%-tne, po vacsine isiel za 2 do bace. Mat priklad
z pisomky dobre znamenalo tam mat pekne vyzerajucu omacku a spravny 
zaver, podrobnosti ho vobec nezaujimali.

\pisomka 

\uloha
$S$ je mnozina disjunktnych intervalov (nie jednoprvkovych) na $\mathbb R$. 
Dokazte, ze $S$ je spocitatelna.

\begin{riesenie}
V ka�dom z intervalov le�� nejak� racion�lne ��slo, tieto s� navz�jom r�zne,
lebo intervaly s� disjunktn�. Preto je intervalov najviac $|\mathbb Q|$.
\end{riesenie}

\uloha
Pocet rozsadeni $n$ nepriatelskych dvojic okolo okruhleho stola.

\uloha
Mnozina $A\subseteq\mathbb N$ je zhora neohranicena, potom $|A|=|\mathbb N|$.

\begin{riesenie}
Pod�a Cantor-Bernsteinovej vety n�m sta�� zostroji� dve injekcie. Jedna je trivi�lna, k druhej:
$f(0)$ nech je �ubovo�n� prvok z $A$. Ke� u� m�me hodnoty $f(0)$ a� $f(k)$, nech 
$f(k+1)$ je �ubovo�n� prvok z $A$ v��� ako v�etky doteraz vybran�. Ke�e $A$ je zhora 
neohrani�en�, tak� prvok (a teda aj h�adan� injekcia) ur�ite existuje.
\end{riesenie}

\uloha
Dokazte, ze system mnozin $\{S_1,\ldots,S_m\}$ ma $m$ roznych reprezentantov, ak
kazda z mnozin ma prave $r$ prvkov a kazdy prvok sa nachadza prave v $r$ mnozinach.

\begin{riesenie}
E�te raz pou�itie Hallovej vety na $r$-regul�rny bipartitn� graf.
\end{riesenie}

\uloha
Dokazte, ze v dvojfarebnom $K_{24}$ existuje aspon jeden jednofarebny $K_4$.

\uloha
Oznacme $E_n=\{ (x_1,\ldots,x_n) ~|~ x_i\in\{0,1\} \}$, pre $x=(x_1,\ldots,x_n)$, 
$y=(y_1,\ldots,y_n)$ definujme $x\preceq y \iff \forall i; x_i\leq y_i$. 
Dokazte, ze $\left( E_n,\preceq \right)$ je ciastocne usporiadana mnozina. 
Aky je maximalny pocet navzajom neporovnatelnych prvkov?

\begin{riesenie}
V�eobecnej�ia verzia tohto tvrdenia sa vol� Dilworthova veta a hovor� to�ko, �e ve�kos�
najv��ej mno�iny navz�jom neporovnate�n�ch prvkov je rovnak� ako po�et "re�az�", ktor�ch
zjednotenie obsahuje v�etky prvky. (Re�az je postupnos� prvkov, v ktorej ka�d� �al�� je 
$\succeq$ ako v�etky predch�dzaj�ce.)

My ju nepotrebujeme dokazova�, sta�� si uvedomi� jej trivi�lnej�iu implik�ciu: Z ka�dej re�aze
m��eme vybra� najviac jeden prvok. Vyberme v�etky prvky z $E_n$, ktor� maj� pr�ve $\lfloor
n/2\rfloor$ jednotiek. Zjavne ka�d� dva s� neporovnate�n� a je ich $p=n \choose \lfloor n/2\rfloor$.
No a �ahko zostroj�me $p$ re�az�, ktor� spolu pokr�vaj� cel� $E_n$.
\end{riesenie}

\pisomka

\uloha
Mame $n^2+1$ prvkovu postupnost roznych prirodzenych cisel.
Ukazte, ze existuje jej monotonna podpostupnost dlzky $n+1$.

\begin{riesenie}
Sporom.
Zoberme pre ka�d� prvok ��sla $r_i$ a $k_i$ -- d�ku najdlh�ej rast�cej a najdlh�ej klesaj�cej
postupnosti, ktor� v �om kon��. V�etky $r_i$ aj $k_i$ s� aspo� 1 (ten prvok) a najviac $n$ (lebo
nem�me monot. postupnos� d�ky $n+1$). Mo�n�ch dvoj�c $[r_i,k_i]$ je teda $n^2$, prvkov je $n^2+1$,
ale potom n�m ujo Dirichlet hovor�, �e pre nejak� $i<j$ je $r_i=r_j$ a $k_i=k_j$. Ale to je spor,
lebo $j$-tym prvkom bu� vieme pred�i� najdlh�iu rast�cu, alebo najdlh�iu klesaj�cu postupnos�
kon�iacu $i$-tym prvkom.
\end{riesenie}

\uloha
Mame dane $j$, $k$ a $c_1,c_2,\ldots,c_k$. 
Kolko je vsetkych kombinacii s opakovanim $j$ prvkov z $k$, ze 
$\forall i;$ $i$-ty prvok sa opakuje najviac $c_i$ krat?

\uloha
Priklad s hyperkockou. Prelozene:
$A$ je lubovolna mnozina $n$-prvkovych binarnych vektorov s $k$ jednotkami 
a $B$ obsahuje vsetky take vektory, ktore dostaneme z niektoreho vektoru z $A$
pridanim jednotiek tak, aby jednotiek bolo $l$.
Treba ukazat:
$${|A|\over {n \choose k} } \leq {|B| \over {n \choose l} }$$

Napr. ked $n = 3$, $k = 1$, $l = 2$, $A = \{(0, 0, 1), (1, 0, 0)\}$
tak $B = \{(1, 0, 1), (1, 1, 0), (0, 1, 1)\}$.

\uloha
Konigova veta (to s tou maticou jednotiek a nul)

\uloha
Ak $R(m, n-1) = 2p$, $R(m-1, n) = 2q$ (teda su parne), potom
plati: $R(m, n) < R(m, n-1) + R(m-1,n)$.

\uloha
Mnozina $\mathbb Q \cup \left<0, 1\right>$ je spocitatelna. Dokazte.
{\sl (Pozn. autora: Takto sa to zachovalo. Zjavne je to blbos�, asi tam
m� by� prienik.)}

\pisomka

Z prikladov na skuske dalej: Pocet rozsadeni manzelskych parov,
Spernerova veta, Ramseyove cisla, Hallovo kriterium, $2k+1$ papierikov
kolko mozme vybrat tak aby ked vyberieme $a$,$b$,$c$ tak $a+b$ sa nerovna $c$,
dokazat inkluziu exkluziu, odvodit Eulerovu funkciu, odvodit $A'(r)$.

\pisomka

\uloha
Kolko je moznych rozsadeni $n$ nepriatelskych dvojic okolo okruhleho stola s ocislovanymi stolickami?

\uloha
Mame postupnost $n^2+1$ roznych prir. cisel. Dokazte, ze existuje rydzo monotonna podpostupnost
dlzky $n+1$.

\uloha
Ostra nerovnost pri Ramseyho cislach, ak tie dve su parne. {\sl (Pozn. autora: presn� zadanie vi� vy��ie)}

\uloha
Hallova veta.

\uloha
$\aleph_0 \times \aleph_0 = \aleph_0$

\uloha
Pocet particii cisla $n$ na najviac $m$ scitancov sa rovna poctu partici cisla
$m+n$ na $m$ scitancov.

\begin{riesenie}
Napr. cez Ferrersove diagramy, alebo aj priamo. Bijekcia je tak�, �e ka�d� s��tanec
zv���me/zmen��me o 1.
\end{riesenie}

\pisomka

\uloha
Dokazte, ze plati tato ohavna (na prve pohlady) suma, ci co:
$$ { (n+r-1)! \over r! } - { n \over 1 }\cdot { (n+r-3)!\over (r-2)! }
   + {n(n-1) \over 1.2 }\cdot {(n+r-5)! \over (r-4)!} - \cdots = 
   {n!(n-1)! \over r!(n-r)!} $$

\uloha
Dokaz odhad poctu Spernerovych systemov $A_n$, pricom $T_n={n\choose \lfloor n/2\rfloor}$:
$$ 2^{T_n} < A_n < {2^{T_n} \choose T_n} $$

\uloha
Student riesi ulohy v priebehu roka. Kazdy den riesi (neznamena, ze vyriesi)
aspon jednu ulohu. Aby nebol pretazeny, v kazdom tyzdni vyriesi najviac 12
uloh. Dokazte, ze existuje niekolko po sebe iducich dni, pocas ktorych student
vyriesi 20 uloh.

\begin{riesenie}
Takto zadan� to neplat�, napr. ke� �tudent ka�d� pondelok vyrie�i 12 �loh.
Keby tam bolo "ka�d� de� vyrie�i aspo� 1 �lohu", asi to u� plat�, aj ke� 
viac by sa mi p��ilo e�te zmeni� "ka�d� t��de�" na "ka�d�ch po sebe id�cich
7 dn�".
\end{riesenie}

\uloha
Dokazte, ze mnoziny $\{0,1\}^{\mathbb N}$ a $\{0,1,2\}^{\mathbb N}$ maju rovnaku mohutnost.

\uloha
Nech $A$,$B$ su konecne mnoziny, $|A|=n$, $|B|=m$. Dokaz:
\begin{itemize}\itemsep -3pt
\item[a)] ak $A$ a $B$ su disjunktne, tak $|A\cup B|=n+m$
\item[b)] $|A\times B|=nm$
\item[c)] $|A^B]=n^m$
\end{itemize}

\uloha 
Nech $X$ je konecna mnozina. Potom plati:
\begin{itemize}\itemsep -3pt
\item[a)] Ak $f:X\to X$ je injekcia, tak $f$ je bijekcia.
\item[b)] Ak $f:X\to X$ je surjekcia, tak $f$ je aj injekcia.
\end{itemize}

\begin{riesenie}[0]
\begin{itemize}\itemsep -3pt
\item[a)] Sporom, nech to nie je bijekcia, potom $\exists a\in X$, na
ktor� sa ni� nezobraz�. Teda m�me $|X|$ vzorov, $|X|-1$ obrazov. Z Dirichletovho
princ�pu sa niektor� 2 vzory musia zobrazi� na ten ist� obraz, a teda $f$ nie je
injekcia.
\item[b)] Sporom, nech to nie je injekcia. Potom $\exists a,b\in X; f(a)=f(b)$. 
Potom ale mus� by� $f(X\setminus \{a,b\})=X\setminus \{f(a)\}$. To sa ale ned�,
lebo mno�ina obrazov je v��ia ako mno�ina vzorov. (�udsky: Ak sa dva prvky 
zobrazia na ten ist�, tak na niektor� in� sa nezobraz� ni�.)
\end{itemize}
\end{riesenie}

\pisomka 

\uloha
Pocet permutacii $n$ prvkov takych ze $a_{i+1}$ nenasleduje bezprostredne za $a_i$.

\begin{riesenie}
Vraj v�sledok (neoveril som, ale vyzer� $\pm$ dobre):
$$ n! - \sum_{i=1}^{n-1} (-1)^{i+1} {n-1 \choose i}(n-i)!$$
\end{riesenie}

\uloha
Je danych $k$ prvkov v riadku, dokazte ze existuje medzi nimi postupnost po sebe 
iducich prvkov takych, ze ich sucet je delitelny $k$.

\begin{riesenie}
V�imnime si s��ty $a_1$, $a_1+a_2$, \dots, $a_1+\ldots+a_k$. 
Ak je niektor� z nich delite�n� $k$, vyhrali sme. V opa�nom pr�pade s�
v�etky zvy�ky po delen� $k$ z mno�iny $\{1,\ldots,k-1\}$. Z Dirichletovho
princ�pu d�vaj� 2 z nich rovnak� zvy�ok. No a sta�� tie dva od seba od��ta�.
\end{riesenie}

\uloha
Dokazte pomocou indukcie pre $n$ ze mohutnost komplementu zjednotenia $n$ mnozin sa rovna
$\sum_{k=0}^n (-1)^k S_k$

\uloha
Nutna a postacujuca podmienka existencie {\em viacerych} reprezentantov.
(Tento priklad je v tych lajstrach s prikladmi.)

\begin{riesenie}
Podmienka je: Aby mala ka�d� mno�ina $r$ reprezentantov, treba a sta��, aby zjednotenie 
ka�d�ch $k$ mno��n malo aspo� $rk$ prvkov.

Insight {\sl (Pozn. autora: Nez�aknite sa, ak nerozumiete. Mo�no pochop�te pred �t�tnicami.)}: 
Predstavme si bipartitn� graf, vrcholy na jednej strane bud� na�e mno�iny, vrcholy
na druhej strane ich prvky, hrana medzi nimi je iff prvok patr� do mno�iny. Dajme ka�dej
hrane kapacitu 1, pridajme odtok, z ka�d�ho prvku do� hranu s kapacitou 1, zdroj, z neho
do ka�dej mno�iny hranu s kapacitou $r$. Potom h�adan� syst�m reprezentantov existuje 
pr�ve vtedy, ke� v tomto grafe existuje tok s hodnotou $rn$, kde $n$ je po�et mno��n. 
Pr�ve uveden� podmienka je ekvivalentn� s t�m, �e ka�d� rez v na�om grafe m� kapacitu
aspo� $rn$. (V jednej �asti rezu bude $k$ vrcholov zodpovedaj�cich mno�in�m, tie prispej�
aspo� $rk$ hranami s kapacitou 1, v druhej zvy�n�, tie prispej� $n-k$ hranami s kapacitou $r$.)
\end{riesenie}

\uloha
Bijekcia $\mathbb N^3 \to\mathbb N$.

\begin{riesenie}
Zlo��me do seba dve dobre zn�me bijekcie $\mathbb N^2 \to\mathbb N$.
\end{riesenie}

\uloha
Dokaz Konigovej vety.

\begin{riesenie}
Insight {\sl (Pozn. autora: Nez�aknite sa, ak nerozumiete. Mo�no pochop�te pred �t�tnicami.)}: 
Na t� maticu sa m��eme d�va� ako na maticu susednosti bipartitn�ho grafu (ak $a_{i,j}=1$, 
$i$-ty vrchol prvej a $j$-ty vrchol druhej part�cie s� spojen� hranou). K\"onigova veta
vlastne hovor�, �e v �ubovo�nom bipartitnom grafe je ve�kos� najmen�ieho vrcholov�ho pokrytia
rovnak� ako ve�kos� najv��ieho p�rovania.

Z ka�dej hrany p�rovania mus�me do pokrytia vybra� aspo� 1 vrchol. A pre�o to�ko sta��? 
N�jdime maxim�lne p�rovanie $=$ maxim�lny tok. Z ka�dej hrany p�rovania vyberieme "spodn�/prav�"
vrchol (vzdialenej�� od zdroja), ak do� vedie zlep�uj�ca cesta (cez nejak� p�rovan�m
nepokryt� "horn�/�av�" vrchol, ktor� mus�me pokry�) a "horn�/�av�" vrchol inak.
\end{riesenie}

\pisomka

Ustna: Dokazat Eulerovu vetu o particiach. Definicia grafu.

\end{document}
