\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$ 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}