\documentclass{article}
\usepackage{slovak}
\usepackage{a4wide}
\usepackage{amsfonts} % provides: maticke N
\usepackage{verbatim}
\usepackage{amssymb} % kvoli \square
\usepackage{color}
\usepackage{fancybox}
\usepackage{epsfig}

\def\then{\Rightarrow}
\def\eps{\varepsilon}
\def\N{{\mathbb N}}
\def\Z{{\mathbb Z}}
\def\Q{{\mathbb Q}}
\def\R{{\mathbb R}}
\def\Nadpis#1{\centerline{\Large #1}\bigskip\par}
\def\nadpis#1{\centerline{\large #1}\medskip\par}


\definecolor{lgray}{rgb}{0.90, 0.90, 0.90}
\newlength{\myboxwidth}      \myboxwidth=\textwidth       \advance\myboxwidth -13pt

\newenvironment{graybox}%
{%
 \vskip-1.8\baselineskip\noindent\begin{center}%
 \begin{Sbox}\begin{minipage}{\myboxwidth}%
}%
{%
 \end{minipage}\end{Sbox}\fcolorbox{black}{lgray}{\TheSbox}\end{center}%
% \vskip\baselineskip%
}
   

\begin{document}

\begin{graybox}
\medskip
\centerline{\Large\sc Rie�enia Tomanovych papierov z 1. semestra}
\smallskip
\centerline{\small \copyright Mi�oF. 1999--2003}
\vspace{0.5cm}
\end{graybox}

\centerline{\bf\large �tandardn� disclaimer}

\medskip

Tieto papiere {\bf NEMAJ�} sl��i� ako n�hrada za rie�enie pr�kladov. Pr�klady si najsk�r sk�ste 
prerie�i� sami, ak nie�o sami vymysl�te, omnoho �ah�ie si to zapam�t�te. V�etky v�sledky s� bez
akejko�vek z�ruky, som len �lovek a ob�as sa m�lim. �ubovo�n� prejavy uznania a v�aky s� v�tan�.

Tento dokument sa na�alej (aj ke� slima��m tempom, ale predsa) vyv�ja. Pokia� v �om n�jdete chyby, 
budem v�m v�a�n�, ak mi ich po�lete. Pokia� by ste do� chceli dop�sa� ve�a nov�ch vec�, zdroj�ky
s� va�e, len popros�m necha� v nich do bud�cna moje meno. Pokia� je to mo�n�, do r�znych online
arch�vov �tudijn�ch dokumentov neumiest�ujte k�piu tohto dokumentu, ale linku na�, aby sa pr�li�
ne��rili r�zne star� verzie. 

T�to verzia vznikla d�a {\bf\today{}} (a je explicitne nov�ia od v�etk�ch verzi�, ktor� nemaj� uveden� 
d�tum).

\bigskip


\Nadpis{Kombinatorika}

\nadpis{Papier za��naj�ci ``Nech m,n s� cel�..."}

\begin{itemize}
\item[1.]
Ka�d� tak� cesta zodpoved� postupnosti n�l a jednotiek, v ktorej je pr�ve m n�l. Tak�ch postupnost� je ale zjavne $m+n\choose n$

\item[2.]
Ka�d� matica $m \times n$ po�adovan�ho tvaru je jednozna�ne ur�en� svojou podmaticou $(m-1) \times (n-1)$, lebo zvy�n� ��sla sa daj� jednozna�ne ur�i�. Preto v�etk�ch mat�c po�adovan�ho tvaru je $2^{(m-1)(n-1)}$.

\item[3.]
Matick� alebo fyzik�lny nav�tevuje $35-10=25$ �ud�, ke�e $20$ matick�, $11$ fyzik�lny, tak oba nav�tevuje $20+11-25=6$ �ud�. A teda iba matick� $20-6=14$ �ud�.

\item[4.]
�peci�lny pr�pad 5.

\item[5.]
Kombinatorickou �vahou:
Ko�k�mi sp�sobmi m��me vybra� $k$ objektov spomedzi $m+n$ r�znych? $m+n\choose k$. Ale
ke� si objekty rozdel�me na $2$ k�pky, na jednej $m$, na druhej $n$, tak z jednej vyberieme $i$ $n\choose i$ sp�sobmi, z 
druhej $(k-i)$ $m\choose k-i$ sp�sobmi, toto zr�tame cez $\forall i$, mame sumu na �avej strane, q.e.d.

\item[5'.]
M��eme osta� pri kombinatorickej �vahe. Tentokr�t vyber�me $m$ predmetov spomedzi $n_1+\dots +n_q$,
pri�om t�ch $n_1+\dots +n_q$ predmetov si rozdel�me na k�pky ve�kost� $n_1$, \dots, $n_q$. Na �avej strane
s��tame cez v�etky mo�nosti, ko�ko prvkov z ktorej k�pky sme vybrali.

Form�lny d�kaz: Indukciou pod�a $q$.\\
Pre $q=1$ je ${n \choose m }={n \choose m }$, �o dos� o�ividne plat�.
Teraz nech
$\sum {n_1 \choose m_1 }\cdot{n_2 \choose m_2 }\cdot\dots\cdot{n_q \choose m_q }={n_1+\dots +n_q\choose m} $
Dok�me, �e to plat� aj pre $q+1$. Je:
$$\sum_{m_1+\dots+m_{q+1}=m} \prod_{i=1}^{q+1} {n_i \choose m_i } =\sum_{m_1+\dots+m_{q+1}=m} {n_{q+1}\choose m_{q+1} } \cdot\prod_{i=1}^{q} {n_i \choose m_i } = $$
$$=\sum_{k=0}^{m} \left( {n_{q+1}\choose k} \cdot \sum_{m_1+\dots+m_{q+1}=m-k} \prod_{i=1}^{q} {n_i
\choose m_i } \right)={\rm (pod�a~ind.~predp.)}=$$
$$=\sum_{k=0}^{m} \left( {n_{q+1}\choose k} \cdot {n_1+\dots+n_q\choose m-k} \right)={\rm
(pod�a~�l.~5)}={n_1+\dots+n_{q+1}\choose m}$$
�o bolo treba dok�za�. 

\item[6.]
\begin{itemize}
\item[a)] V ka�dom st�pci je jedna, pre t� v prvom m�me $n$ mo�nost�, pre druh� $(n-1)$, \dots tak�e spolu $n!$.
\item[b)] Pre prv� m�me $n^2$ mo�nost�, pre druh� $(n-1)^2$, lebo 1 riadok a 1 st�pec s� obsaden�, \dots tak�e spolu $n^2.(n-1)^2.\cdots.1^2=(n!)^2$.
\item[c)] Analogicky, vyjde $\prod_{i=0}^{n-1} (m-i)$, resp. to cel� na druh�, pre $m<n$ to je zjavne 0 (v s��ine je nulov� �len), tak�e to funguje aj pre ne.
\end{itemize}

\item[7.]
Jednoduch�, len pracn�. Pre istotu hodnoty sedmov�ch kar�t: $D=2, H=3, K=4, 7=7, 8=8, 9=9$, $10=10, A=11$. A je $21=11+8+2=11+7+3=10+9+2=10+8+3=10+7+4=9+8+4$, v ka�dom z t�chto pr�padov
$4^3=64$ mo�nost�, $\dots=9+9+3$, to je ${4 \choose 2 }\cdot 4=24$ mo�nost�, $\dots=7+7+7$, to je ${4 \choose 3 }=4$ mo�nosti, spolu $6.64+24+4=412$ mo�nost�.

\item[8.]
A a B maj� dokopy $18$ kn�h. Tie spomedzi $27$ vyberieme $27 \choose 18 $ sp�sobmi. Medzi A a B ich rozdel�me $2^{18}$ sp�sobmi, lebo ka�d� m��eme da� A alebo B. T�m je u� ur�en� aj �o dostane C. Preto spolu to je ${27 \choose 18 }\cdot 2^{18}$\
 mo�nost�.

\item[9.]
$N$ mu�ov usad�me $(n-1)!$ sp�sobmi - prv�ho posad�me kamko�vek, ostatn�ch polohu u� ur�ujeme pod�a neho, id� len na 'nep�rne' miesta. Potom rozsad�me �eny na zvy�n� miesta $n!$ sp�sobmi, spolu $n!(n-1)!$ sp�sobov.

\item[10.]
Postupne vyberajme, ktor� guli�ky d�me do $1.,2.,\dots,k.$ �katule. Do prvej m�me pre $1.$ guli�ku $n$ mo�nost�, pre $2.$ $(n-1)$ mo�nost�, \dots, pre $n_1$ $n-n_1+1$ mo�nost�. Pre prv� guli�ku z �al�ej krabice m�me $n-n_1$ mo�nost�, at�.
Tak�e dokopy by to bolo $n!$ mo�nost�, ale v r�mci ka�dej krabice sme zar�tali $\forall$ usporiadania guli�iek, ktor�ch je pre $i.$ krabicu $n_i!$. Tak�e v�etk�ch rozdelen� je $n! \over {n_1!.n_2!.\cdots.n_k!}$

\item[11.]
Ke�e guli�ky s� rovnak�, m��me prv�ch s �kat�� naplni� hne� na za�iatku, ostane n�m $k=n-\sum a_i$ guli�iek a $l=m-s$ krab�c, to je ekvivalentn� s po�tom rie�en� rovnice $x_1+...+x_l=k \land x_i\geq 0$. Tak�e m�me $k+l-1 \choose k $ mo�nost�.

\item[12.]
Na za�iatku pod�vame guli�ky tam, kam treba, ostane n�m $k=n-\sum a_i$ guli�iek, ktor� m�me �ubovo�ne rozmiestni� do $m$ krab�c, to ide $m+k-1 \choose k$ sp�sobmi.

\item[13.]
Predstavme si $n$ objektov v rade. Medzi nimi je $n-1$ medzier. Ke� do $k-1$ z nich d�me priehradku, rozpadne sa n�m to na $k$ �ast�, ktor� ur�uj� nejak� usporiadan� rozklad.
 Zjavne ke� d�me priehradky na in� miesta, dostaneme r�zne rozklady. Naopak, ka�d�mu rozkladu vieme n�js� pr�slu�n� rozdelenie priehradok. Preto je rozdelen� priehradok a usp. rozkladov rovnako, teda $n-1 \choose k-1$.

\item[14.]
Ko�ko ��sel od $1$ po $n$ je delite�n�ch $p$? $\lfloor{n \over p}\rfloor$. V�etk�ch s��inov je $n^k$, t�ch, ktor� nie s� delite�n� $p$, je $(n-\lfloor{n\over p}\rfloor)^k$, tak�e zvy�n� s� delite�n� $p$.

\item[15.]
Z binomickej vety pre $(1+1)^n$.

\item[16.]
Rozoberieme $6$ pr�padov pod�a toho, ko�ko �ien vyberieme spomedzi zn�mych mu�a. (potom je jasn�, ko�ko vyber�me ostatn�ch). Ml�ky treba predpoklada�, �e mu� a �ena nemaj� spolo�n�ch zn�m�ch :-)

\item[17.]
Pre prv�ho $8$ mo�nost�, pre druh�ho $7$, at�., ka�d� rozostavenie sme zar�tali $8\times$, preto je to $7!$.

\item[18.]
Ke� t�ch $5$ kn�h vyberieme, ostatn� sa t�m rozdelia na $6$ �ast�, z ktor�ch stredn� $4$ s� nepr�zdne. M�me teda zisti�, ko�ko m� rie�en� rovnica $x_1+\dots+x_6=12-7=5$ za podmienok $x_1,x_6\geq 0 \land x_2,\dots,x_5>0$.
 To je ekvivalentn� s rovnicou $x_1+\dots+x_6=9 \land x_i>0$ o ktorej vieme, �e m� ${8 \choose 5 }={8.7.6 \over 3.2.1}=56$ rie�en�.

\item[19.]
\begin{itemize}
\item[a)]
Bu� s� obe ��sla p�rne, alebo obe nep�rne, v oboch pr�padoch m�me $15 \choose 2$ mo�nost�, spolu $15.14=210$ mo�nost�.
\item[b)]
Bu� d�vaj� v�etky tri rovnak� zvy�ok po delen� $3$, to s� $3$ pr�pady, v ka�dom $10 \choose 3$ mo�nost�, alebo dve z nich d�vaj� r�zny. Rozobrat�m pr�padov zist�me, �e jedin� mo�nos� je t�, �e jedno d�va
zvy�ok $0$, jedno $1$ a jedno $2$, tu je teda $10^3$ mo�nost�, spolu $3.{10 \choose 3 }+10^3=1360$ mo�nost�.
\end{itemize}

\item[20.]
Pre Jo�a a �ura s� len $3$ mo�nosti -- bu� ide Jo�o $5.$, alebo $6.$, alebo $7.$, v jednotliv�ch pr�padoch ide �uro $4.$, $5.$ alebo $6.$ 
Pre Jana m�me zaka�d�m $5$ mo�nost�, kedy m��e �s�. Preto dokopy m��u �s� na sk��ke $3.5=15$ sp�sobmi. (A �smimi sp�sobmi na nej dopadn�� :)
\end{itemize}

\nadpis{Papier za��naj�ci ``N�jdite s��et v�etk�ch..."}

\begin{itemize}
\item[21.]
Tak�ch ��sel je $24$, $6$ m� na mieste jednotiek $1$, $6$ m� $2$, at�., analogicky na mieste desiatok a stoviek, preto ich s��et je $(100+10+1).(6.1+6.2+6.3+6.4)=6660$.

\item[22.]
V�etk�ch $\triangle$ je $n \choose 3$. Z nich nevyhovuj� tie, ktor� maj� niektor� dva vrcholy susedn�. T�ch je $n.(n-2)$, lebo susedn� dvojicu vyberieme $n$ sp�sobmi, zvy�n� vrchol $n-2$ sp�sobmi. Tu sme ale dvakr�t zar�tali v�etky tie, ktor� maj�
 v�etky tri vrcholy id�ce po sebe. Tak�ch je zjavne $n$. Tak�e v�sledn� po�et je ${n \choose 3 }-n(n-2)+n$, pre $n=3$ treba poveda�, �e je to $0$, lebo tam vznik� chaos pri r�tan�\dots

\item[23.]
Ozna�me strany $a$,$b$,$c$ tak, aby $a\leq b\leq c$. Potom z $\triangle$ nerovnosti $\then$ $c < {40 \over 2}=20$, z�rove� z $a\leq b\leq c$ $\then$, �e $40=a+b+c\leq c+c+c=3.c \then c\geq {40 \over 3}$, pre ka�d� mo�nos� vieme n�js� max. a min.
 hodnotu b, (lebo $b\leq c \land 40-c=a+b\leq 2.b$), ka�dej zodpoved� 1 hodnota $a$, zr�tame, hotovo.

\item[24.]
Spomedzi $000\dots 999$ za��na jednotkou $100$, zo zvy�n�ch m� na $2.$ mieste jednotku $9.10=90$, zo zvy�n�ch m� na $3.$ mieste jednotku $9.9=81$ a navy�e ostala $1000$ $\then$ $1$ obsahuje $100+90+81+1=272$ ��sel.

\item[25.]
S��et v�etk�ch koeficientov dostaneme na pravej strane, ke� za v�etky $a_i$ dosad�me $1$. Vtedy ale �av� strana je $k^n$.

\item[26.]
Plat�: $k$-ty �len je $100 \choose k$ $.(\sqrt{2})^k.(\root{4}\of{3})^{100-k}$. �ahko uk�eme, �e toto ��slo je rac. pr�ve vtedy,
 ke� s� rac. $(\sqrt{2})^k$ a $(\root 4 \of 3)^{100-k}$. A to je zasa vtedy, ke� $2|k \land 4|(100-k)$. Preto je racion�lnych �lenov $26$.

\item[27.]
Cez $k.{n \choose k }=n.{n-1 \choose k-1 }$ a $(1-1)^{n-1}$.

\item[28-29.]
Z polynomickej vety.

\item[30.]
Plat� $1^n=({1+x \over 2} + {1-x \over 2})^n=({1+x \over 2})^n + ({1-x \over 2})^n + \sum_{i=1}^{n-1} {n \choose i }\cdot ({1+x \over 2})^i\cdot ({1-x \over 2})^{n-i} \geq ({1+x \over 2})^n + ({1-x \over 2})^n$,
 z �oho vyn�soben�m $2^n$ m�me dokaz. nerovnos�.

\item[31.]
To je na samostatn� papier...

\item[32.]
Plat� ${m \choose k }{m-k \choose n-k }={m!.(m-k)! \over k!.(m-k)!.(m-n)!.(n-k)!}={m! \over k!.(n-k)!.(m-n)!} =
{m!.n! \over n!.(m-n)!.k!.(n-k)!} = {m \choose n }{n \choose k }$, kon�tantu
 $m \choose n$ vyberieme pred sumu a ostane n�m zjavn� $0$.

\item[33-34.]
Pre $m=2 \land n=1$ je to $3$, tak�e neplat� ani $1$ z t�ch rovnost�\dots

\item[35.]
�portuj� $15$ chlapci s dobr�m prospechom, t.j. $3$ so zl�m. �portuje $11$ �iakov so zl�m prospechom, preto �portuje $8$ diev�at so zl�m prospechom.
 Diev�at so zl�m prospechom je v�ak len $6$, preto je v spr�ve chyba.

\item[36.]
Je ich $n-\varphi (n) = 210 - 210\cdot (1 - {1\over 2} )\cdot (1 - {1\over 3} )\cdot (1 - {1\over 5} )\cdot (1 - {1\over 7} ) = 210 - 210\cdot {1 \over 2}\cdot {2 \over 3}\cdot {4 \over 5}\cdot {6 \over 7} = 210 - 48 = 162$.

\item[37.]
Ko�ko je del. $2$? $\lfloor {100\over 2} \rfloor =50$. Analogicky tromi je del. $33$, piatimi $20$. Ko�ko nie je delite�n� $2$, $3$ ani $5$? $100-50-33-20=-3$??? Nie, lebo sme $2x$ odr�tali tie, ktor� s� del. dvomi z nich a $3x$ tie,
�o s� del. v�etk�mi tromi. Tie e�te mus�me prir�ta�. $2$ a $3$, teda $6$ je del. $16$, $2$ a $5$ $10$, $3$ a $5$ $6$, tie prir�tame, m�me $-3+16+10+6=29$, ale op� sme $3x$ prir�tali tie, �o s� del. v�etk�m, e�te ich
na z�ver mus�me odr�ta�, s� $3$, tak�e spomedzi ��sel $1\dots 100$ ich $29-3=26$ nie je del. $2$, $3$ ani $5$. Pr�ve (trochu �a�kop�dne a rozsiahlo, ale to len kv�li zrozumite�nosti) pou�it� princ�p
sa vol� princ�p zapojenia a vypojenia, alebo noblesnej�ie princ�p inkl�zie a exkl�zie.

\item[38.]
Je ${n-1 \choose 0 }+ {n \choose 1 }+\dots +{n+m-1 \choose m }={n \choose 0 }+{n \choose 1 }+\dots +{n+m-1 \choose m }={n+1 \choose 1 }+\dots +{n+m-1 \choose m }=\dots = {n+m-1 \choose m-1 }+{n+m-1 \choose m }={n+m \choose m }$. Alebo indukciou pod�a m.

\item[39.]
Cez $i.{ n \choose i } = i\cdot {n! \over i!.(n-i)!} = n\cdot {(n-1)! \over (i-1)!.(n-i)!} = n.$ $n-1 \choose i-1$, pre $0$ je $i.{n \choose i }=0$, tak�e tento �len m��me vynecha�.

\item[40.]
Bez kombinatorickej �vahy: z binomickej vety pre $((m-1) + 1)^n$ s vyu�it�m $m+n \choose m$ $=$ $m+n \choose n$.

Komb. �vahou: Vyberajme $n$ prvkov spomedzi $m$, z�le�� na porad�, m��u sa opakova�. Ko�ko je tak�ch, v ktor�ch je $k$ jedni�iek? ${n \choose k }\cdot (m-1)^{n-k}$, ke� to zr�tame cez v�etky
$k$, dostaneme po�et vari�cii s opak. $n$. triedy z $m$ prvkov, ktor�ch je $m^n$.

\item[41.]
Prienik ka�dej s povrchom gule je rovn�kov� kru�nica (t.j. kru�nica s rovnak�m polomerom ako gu�a). Zo zadania $\then$, �e �iadne $3$ kru�nice nemaj� spolo�n� bod. Ke� m�me jednu kru�nicu, t� del� povrch na $2$ �asti.
Nech $n$ kru�n�c del� povrch na $P(n)$ �ast�, na ko�ko ho m��e deli� $n+1$ kru�n�c? Ke� prid�me $(n+1).$ kru�nicu, t� pretne u� exist. $n$ v $2n$ bodoch. Tie ju rozdelia na $2n$ �sekov. Ka�d� z t�chto �sekov rozdel�
jednu z u� existuj�cich �ast� na $2$. Teda pribudlo presne $2n$ �ast�, �i�e ich je $P(n)+2n$. Teraz u� nie je a� tak� �a�k� spo��ta�/uh�dnu� a dok�za� indukciou vzorec $P(n)=n.(n-1)+2=n^2-n+2$.

\item[42.]
Polo��me $n=r+m$, m�me $38.$

\item[43.]
Pre $k<{n-1 \over 2}$ je ${n \choose k+1 }={n! \over (k+1)!.(n-k-1)!} = {n! \over k!.(n-k)!}\cdot {n-k \over k+1} = {n \choose k }\cdot {n-k \over k+1} > {n \choose k }$, druh� nerovnos� analogicky.
\end{itemize}

\nadpis{Papier za��naj�ci ``N�jdite maximum spomedzi..."}

\begin{itemize}
\item[44.]
Z $43.$ vypl�va, �e je to ${n \choose \lfloor {n \over 2} \rfloor}$.

\item[45.]
$p \choose k$ je cel�, plat� ${p \choose k }={p! \over k!.(p-k)!}$, p del� �itate�a, nedel� menovate�a, z toho vypl�va, �e del� $p \choose k$.

\item[46.]
Pren�sob�me $n+1$ a pou�ijeme ${a \over b}\cdot {a-1 \choose b-1 }={a \choose b }$ a binomick� vetu pre $(1+1)^a$.

\item[47.]
Trivi�lna indukcia

\item[48.]
Indukciou cez vzorec $1+\dots +n = {n.(n+1) \over 2}$.

\item[49.]
Je ${1 \over (a+i-1)(a+i)} = {1 \over a+i-1} - {1 \over a+i}$, preto cela suma vyzer� ${1 \over a} - {1\over a+1} + {1\over a+1} - {1\over a+2} +\cdots -{1\over a+n}$ z �oho
 sa n�m vyml�tia dvojice, ostane ${1\over a} - {1\over a+n} = {(a+n) - a \over a(a+n)} = {n \over a(a+n)}$

\item[50.]
O$5$ tr�pna indukcia pod�a $n$.

\item[51-52.]
Indukcia a� to bol�...

\item[53.]
Indukcia. $2.$ krok je: $$\prod_{i=1}^{n+1} (n+1+i)={(2n+2)(2n+1)\over n+1}\cdot \prod_{i=1}^n (n+i) =
2.(2n+1).2^n.\prod_{i=1}^n (2i-1) =$$
$$=2^{n+1}.\prod_{i=1}^{n+1} (2i-1)$$
\end{itemize}

\nadpis{Papier za��naj�ci ``Ak $A, B$ s� kone�n�..."}

\begin{itemize}
\item[54.]
Pre ka�d� z $m$ prvkov m�me $n$ mo�nost�, na �o ho zobrazi�\dots

\item[55.]
Pre prv� m�me $n$ mo�nost�, pre druh� $n-1$, \dots

\item[56-57.]
Priamo dosad�me do $55.$

\item[58.]
Ten hrozn� s��in je maskovan� $n \choose k $.

\item[59.]
A toto je maskovan� $\sum {n \choose i }=2^n$.

\item[60.]
\begin{itemize}
\item[a)]Z defin�cie.
\item[b)]Z a).
\item[c)]Z defin�cie.
\item[d)]Vi� $5.$
\item[e)]Z a)
\item[f)]In�mi slovami dok�te binomick� vetu. Napr. indukciou.
\item[g)]Z f) pre $x=-1$.
\item[h)]Vi� $32.$
\end{itemize}

\item[61-63.]
S� rie�en� na papieroch, �o sme fasovali\dots
\end{itemize}

\nadpis{Papier za��naj�ci ``Nech $k,n_1,\dots,n_k$ ..."}

\begin{itemize}
\item[64.]
Rie�en� na papieri, �o sme dostali.

\item[65.]
Vypl�va z $64.$, len to e�te treba predeli� v�etk�mi usporiadaniami t�ch $k$ podmno��n (ke�e na ich porad� n�m nez�le��), ktor�ch je $k!$.

\item[66.]
\begin{itemize}
\item[(1)]Vi� $39.$
\item[(2)]Analogicky ako $(1)$.
\item[(3)]$\sum (2k+1){n \choose k }=2.\sum k{n \choose k }+\sum {n \choose k }$
\item[(4)]Vi� $46.$
\item[(5)]Presne na to ist� kopyto ako $(4)$.
\item[(6)]Indukciou.
$$1+\cdots+{1\over n+1} = (1+\cdots+{1\over n})+{1\over n+1} = {\rm (z\ IP\ a\ pod�lohy\ (5))} = $$

$$= \sum_{k=1}^n (-1)^{k-1}\cdot {1\over k}{n \choose k } ~+~ \sum_{k=0}^n (-1)^k{1\over k+1}{n\choose k } = $$

$$= \sum_{k=1}^n (-1)^{k-1}\cdot {1\over k}{n \choose k } ~+~ \sum_{k=1}^{n+1} (-1)^{k-1}{1\over k}{n\choose k-1 }=$$

$$= {(-1)^n \over n+1} ~+~ \sum_{k=1}^n (-1)^{k-1}{1\over k}\left({n \choose k }+{n \choose k-1 }\right)=$$

$$= {(-1)^n \over n+1} ~+~ \sum_{k=1}^n (-1)^{k-1}{1\over k}{n+1 \choose k }=$$

$$=\sum_{k=1}^{n+1} (-1)^{k-1}{1\over k}{n+1 \choose k }$$
\item[(7)]Cez $(1+1)^n$ a $(1-1)^n$, v jednom pr�pade sa to s��ta, v druhom od��ta.
\item[(8)]Cez vhodn� s��et, resp. rozdiel v�razov $(1+1)^n$, $(1-1)^n$, $(1+i)^n$ a $(1-i)^n$ (treba zvoli� znamienka
tak, aby ostali len spr�vne �leny).
\end{itemize}

\end{itemize}

\nadpis{Dve chu�ovky na z�ver kombinatoriky...}

{\bf �loha 31.}\hfill\break
Tak� �plne nen�padn� �loha, skryt� v dave, ale teda ty� na poh�adanie.
Polo�me si najsk�r ot�zku, ko�ko je permut�cii, kde ni� nie je na svojom mieste (t.j. �pec. pr�pad $r=0$).
Ozna�me tento po�et $P(n)$. Je $P(1)=0$, $P(2)=1$. Ko�ko je $P(n)$?
Ak je $1$ prehoden� s nejak�m in�m prvkom (t.j. $1$ je $k$-ta a $k$ je prv�), tak m�me pre zvy�n� prvky P(n-2) mo�nost�, z�rove� (n-1) mo�nost�, ktor� prvok je $k$.
Ak $1$ nie je prehoden� s inou, ke� ju vymen�me s t�m, �o je na $1.$ mieste, na zvy�n�ch $n-1$ miestach dostaneme preh�dzan� $(n-1)$-ticu, zaka�d�m sme mali $n-1$ mo�nost�, kde mohla $1$ p�vodne by�.
Spolu teda m�me $P(n)=(n-1).(P(n-1)+P(n-2))$. To je s�ce pekn�, a pre na�e ��ely aj pou�n�, ale aj na pa�u.\\
Potrebovali by sme explicitn� vzorec. (t.j. tak�, do ktor�ho sa d� priamo dosadi�.)  Na to pou�ijeme zau��van� kombinatorick� delo, ktor� sme s�ce nemali t� �es� prebera�, ale pr�klady na� d� E.T. na
sk��ke ako vidie� s rados�ou. Princ�p inkl�zie a exkl�zie. Ten v takom Tomanovskom mno�inovom z�pise vyzer�:\\
Majme mno�iny $M_1,\dots ,M_n$, potom $|\bigcup M_i|=\sum |M_i| - \sum_{i\not =j} |M_i\cap M_j| +\dots =$
$$\sum_{k=1}^n \left( (-1)^{k-1} \cdot\sum_{i_1<\dots <i_k} \left| \bigcap_{j=1}^{k} M_{i_j}\right| \right)$$
�o vlastne znamen� to�koto: ko�ko prvkov m� prienik $n$ mno�in? To je po�et prvkov prvej $+$ \dots $+$ po�et prvkov $n.$, ale $2$-kr�t sme zar�tali ka�d� prvok, ktor� je v dvoch z nich, tak�e odr�tame prieniky v�etk�ch
dvoj�c mno��n. Prvky, ktor� s� v troch sme ${3\choose 1}$-kr�t prir�tali, ${3\choose 2}$-kr�t odr�tali, tak�e v�bec nie s� zar�tan�, mus�me ich prir�ta�, at�. (Toto nie je d�kaz, len tak� intuit�vne zd�vodnenie, �o to hovor�
a pre�o to funguje.)\\
No a ako to pou�ijeme v na�om pr�pade?
Nech $M_i$ je mno�ina v�etk�ch permut�ci�, ktor� maj� na $i$-tom mieste $i$. �o je zjednotenie t�chto mno��n? To s� pr�ve v�etky nevyhovuj�ce permut�cie. No a ke� si e�te uvedom�me, �e $M_i$ m� $(n-1)!$ prvkov,
$\bigcap_{j=1}^{k} M_{i_j}$ je mno�ina v�etk�ch permut�ci�, ktor� maj� $k$ miest pevne ur�en�ch, m� teda $(n-k)!$ prvkov. S t�m u� m��me r�ta�:
$$P(n)=n! - \sum_{k=1}^n \left( (-1)^{k-1} \cdot\sum_{i_1<\dots <i_k} \left| \bigcap_{j=1}^{k} M_{i_j}\right| \right)=$$
$$= n! + \sum_{k=1}^n \left( (-1)^k \cdot {n\choose k}\cdot (n-k)! \right)=\sum_{k=0}^n \left(
(-1)^k \cdot {n\choose k}\cdot (n-k)! \right)$$
Mo�no sa teraz zlomyse�ne p�tate, na�o vlastne bola t� prv� �vaha. Jednoducho - ak by E.T. nechcel zo�ra� inkl�ziu a exkl�ziu bez d�kazu, tak sa na�ho vytiahnu vz�ahy z prvej �vahy, povie sa tento vzorec a indukciou pod�a $n$
sa dok�e, �e vyhovuje tomu vz�ahu a ke�e t�m je $P(n)$ jednozna�ne ur�en�, je to vlastne d�kaz toho vz�ahu.\\
No a ko�ko je permut�ci� s pr�ve $r$ prvkami na svojom mieste? Prvky na svojich miestach vyberieme
$n\choose r$\ sp�sobmi, zvy�n� tvoria preh�dzan� permut�ciu s $n-r$ prvkami, tak�e je to
${n\choose r}\cdot\sum_{k=0}^{n-r} \left( (-1)^k{n-r\choose k}(n-r-k)! \right) $

No a ke� u� sme tak� rozbehnut�, tak rovno chu�ovka ��slo dva. (dve? jednoducho $2$!)

\medskip

{\bf Angli�ania a Franc�zi.}\hfill\break
Pre t�ch, �o nevedia, o �om je re�: m�me $n$ Angli�anov, $m$ Franc�zov. Ko�k�mi sp�sobmi ich mo�no postavi� do radu tak, aby ka�d� mal ved�a seba aspo� jedn�ho krajana?\\
Zabudnime najsk�r na to, �e Angl�ni aj Franc�zi s� individuality, teda ka�d� in�, e�te sa aj nejako volaj�, zauj�majme sa o nich najsk�r ako o farebn� guli�ky. Ko�k�mi sp�sobmi rozdel�me Angli�anov
na $k$ skup�n tak, aby v ka�dej boli aspo� dvaja? To je ekvivalentn� s rovnicou $a_1+\dots +a_k=n \land \forall i; a_i\geq 2$, �o je zase ekviv. s $a_1'+\dots +a_k'=n-k \land \forall i; a_i'=a_i-1\geq 1$, o ktorej vieme, �e
m� ${n-k-1\choose k-1}$\ rie�en�. A ako medzi nich narva� $m$ Franc�zov? T� musia by� v ka�dej medzere, teda ich skup�n mus� by� aspo� $k-1$, ale z�rove� ich m��e by� najviac $n+1$, lebo u� m��u pribudn��
len dve skupiny -- na za�iatku a na konci. Ak m�me $k-1$ skup�n Franc�zov, na to m�me analogicky
${m-k\choose k-2}$\ mo�nost� a je jasn�, ako ich tam postav�me. Podobne ak je Franc�zov $k+1$ skup�n, na to
m�me ${m-k-2\choose k}$\ mo�nost� a op� je jedin� mo�nos�, ako ich tam postavi�. Ak ich je $k$ skup�n, mo�nost� je 
${m-k-1\choose k-1}$, a postavi� ich tam m��me dvomi sp�sobmi -- bu� je jedna skupina na za�iatku, alebo je jedna
na konci. Dokopy to pre KA�D� rozostavenie $k$ skup�n Angli�anov d�va ${m-k\choose k-2}+2\cdot
{m-k-1\choose k-1}+{m-k-2\choose k}$ vyhovuj�cich rozostaven�. No a h�adan� po�et by bol potom s��et tohto cez v�etky $k$, teda:
$$\sum_{k=1}^{\infty} {n-k-1\choose k-1}\cdot\left( {m-k\choose k-2}+2\cdot {m-k-1\choose
k-1}+{m-k-2\choose k} \right)  $$
To ale e�te st�le vyzer� divne kv�li tej sume do $\infty$ a e�te sme nezar�tali rozl��ite�nos� �ud�. Ke� ale m�me nejak� usporiadanie, kde m�me povedan�, kde stoja Angli�ania a kde Franc�zi, tak konkr�tnych �ud�
na� m��me postavi� $n!.m!$ sp�sobmi -- Angli�anov rozmiestnime na ich miesta $n!$ sp�sobmi a Franc�zov na ich miesta n�sledne $m!$ sp�sobmi. No a z tej sumy je nenulov�ch len prv�ch $\lfloor {n\over 2} \rfloor$ �lenov, lebo pre
$k>\lfloor {n\over 2} \rfloor$ je $k-1>n-k-1$, teda ${n-k-1\choose k-1}=0$, �i�e aj cel� s��tanec je $0$. V�sledok �lohy teda je:
$$n!.m!.\sum_{k=1}^{\lfloor n/2 \rfloor} {n-k-1\choose k-1}\cdot\left( {m-k\choose k-2}+2\cdot
{m-k-1\choose k-1}+{m-k-2\choose k} \right)$$

\Nadpis{Mno�iny \& co.}
%\input mnozinyu.tex
%\input cb.tex
%\input warning.tex

\nadpis{Vybran� z 3 papierov U.x.yy}

\begin{itemize}
\item[U-2-20.]
\begin{itemize}
\item[$\Rightarrow$:]Nepriamo. Nech $A \not\subseteq C$. Potom $\exists x; x\in A\land x\not\in C$. Potom ale $x\in(A\cup(B\cap C))\ \land\ x\not\in((A\cup B)\cap C)$.
\item[$\Leftarrow$:]Nech $A\subseteq C$. Potom ak $x\in A$, tak $x\in$ do oboch mno��n, ak $x\not\in A$, tak
\ $x\in(A\cup(B\cap C)) \iff x\in(B\cap C) \iff x\in B\land x\in C \iff (x\in A \lor x\in B)\land x\in C \iff x\in((A\cup B)\cap C)$
\end{itemize}

\item[U-2-22.]
Sporom. Nech $A\not =B$. Potom BUNV $\exists x; x\in A\land x\not\in B$. Preto $x\in B\cup X \then x\in A\cup X \then x\in X$\\
Potom ale $x\in B\cap X \then x\in A\cap X \then x\in A$, �o� h�adan� spor.

\item[U-2-24.]
\begin{itemize}
\item[$\Rightarrow$:]$A \in A\cup B=B\cup C$, ostatn� rovnako.
\item[$\Leftarrow$:]Ak $x\not\in A\cap B\cap C$, tak $x\not\in A\cup B \land x\not\in B\cup C \land x\not\in C\cup A$\\
Inak BUNV nech $x\in A$. Je $A\subset B\cup C \then x\in B\cup C$ a zjavne aj $x\in A\cup B \land x\in A\cup C$.
\end{itemize}

\item[U-*-*.]
{\sl V�eobecn� �vaha.}
Drviv� v��ina rovnost� mno�inov�ch vz�ahov sa d� dokazova� tak, �e dok�eme, �e $x$ patr� do v�razu na �avej strane pr�ve vtedy, ke� do v�razu na pravej (a takto si to teda prevedieme na ekvivalentn� �lohu s v�rokmi, ktor� �ahko vieme
rie�i�.)\\
Demo: Dok�te: $A\cup B = A \cup (B-A)$\\
$x\in A\cup B \iff x\in A\ \lor\ x\in B \iff x\in A\ \lor\ (x\not\in A \land x\in B) \iff x\in A\ \lor\ x\in (B-A)$, q.e.d.
\end{itemize}

\nadpis{Cantor-Bernsteinova veta}

\begin{itemize}
\item[1.] M� by� prost� a na, in�mi slovami n�jdite bijekciu.
\begin{itemize}
\item[a)] $x \to {1\over x}$
\item[b)] Premietneme os $x$ na kruh so stredom v $(0,1)$ a polomerom $1$ so stredom premietania v $(0,2)$.
\item[c)] Priamke $y=ax+b$ prirad�me pre $a\not\in N_0$ dvojicu $(a,b)$, pre $a\in N_0$ dvojicu $(a+1,b)$, priamke $x=c$ dvojicu $(0,c)$.
\item[d)]??? �o s� paraboly v rovine? Musia ma� os rovnobe�n� s osou y? Asi nie... Ale v�dy sa to d� tak, �e ju pop��eme nejak�mi $4\dots 5$ ��slami, a n�jdeme bijekciu medzi $R^3$ a $R^4$ (alebo $5$), �o je ekvivalentn� s bijekciou medzi $R$ a $R^2$
\ a t� sa d� spravi� tak, �e pred aj za desatinnou �iarkou d�vame cifry striedavo z jedn�ho a druh�ho ��sla.
\item[e)] Kruh zobraz�me na $(stred_x,stred_y,polomer)$.
\item[f)] Ke� si to nakresl�me, vid�me, �e p�vodn� mno�ina tvor� kruh a v�sledn� �tvorec jemu op�san�. Bod $(0,0)$ nech sa zobraz� s�m na seba. Ostatn� body zobraz�me takto: sprav�me polpriamku so za�iatkom v $(0,0)$, prech�dzaj�cu dan�m bodom.
\ Ozna�me n� bod A, bod, v ktorom polpriamka pretne �tvorec B. Potom obraz bodu A je ten bod C polpriamky, pre ktor� je $|OA|={|OC|\over |OB|}$. (Teda cel� �se�ku le�iacu na tejto polpriamke ``natiahneme" tak, aby do�iahla a� po �tvorec)
\item[g)] Podobne ako $b)$, len tentokr�t premietame gu�u z bodu $(0,0,2)$ na rovinu $z=0$.
\end{itemize}

\item[2.] Treba vlastne n�js� injekt�vne zobrazenie $A$ do $B$. Vo v�etk�ch pr�padoch sa presved�te, �e uveden� zobrazenie je naozaj prost�!
\begin{itemize}
\item[a)] $x \to {x+20 \over {\rm mili�np�}}$
\item[b)] Postupnos� $\{a_n\}_{n=0}^{\infty}$ zobraz�me na postupnos� $\{b_n\}_{n=0}^{\infty}$, kde $b_i={a_1\over 2^i}$. Potom je $0<=\sum b_i<=\sum {1\over 2^i}=2$, preto $\sum b_i$ konverguje.
\item[c)] Ka�d� �len postupnosti A zap��eme pomocou dvoch �lenov B (vy��� a ni��� bit:)
\item[d)] Pre jednoduchos� nech s� $N$ od jednotky (ak ich chce E.T. od nuly, treba ich najsk�r zobrazi� ka�d� na o 1 v��ie). Teraz vieme vyu�i� to, �e bin�rny z�pis ka�d�ho prir. ��sla za��na jednotkou. Preto ka�d� prirodzen� ��slo
\ vieme zak�dova� tak, �e najsk�r zap��eme to�ko n�l, ko�ko miest m� jeho bin�rny z�pis, a potom bin�rny z�pis pr�slu�n�ho ��sla.
\item[e)] $(x,y) \to ({x\over 1999},{y\over 2000})$
\end{itemize}

\item[3.] Treba n�js� injekcie z $A$ do $B$ aj z $B$ do $A$.
\begin{itemize}
\item[a)] Trocha naokolo - ako v $2.d)$ uk�eme, �e maj� obe rovnak� mohutnos� ako $\{0,1\}^N$. Ozaj, keby to niekoho zauj�malo, tak $N_m^N$ je mno�ina v�etk�ch postupnost� ��sel $0,1,\dots,m$.
\item[b)] N�vod je blbos�, pre postupnos� sam�ch jednotiek dostaneme neohrani�en� fciu, navy�e
ich fciu treba v nule spojito dodefinova�. 
Spr�vna injekcia m��e vyzera� napr. tak, �e postupnosti $\{a_n\}$ prirad�me funkciu 
$f(x)=\sum_{n=1}^\infty {a_nx^n\over 2^n}$. 

Je netrivi�lne uk�za�, �e je to naozaj injekcia. Nech
$\sum_{n=1}^\infty {a_nx^n\over 2^n}=\sum_{n=1}^\infty {b_nx^n\over 2^n}$. Potrebujeme
uk�za�, �e $\forall k; a_k=b_k$. Sporom, zoberme najmen�ie $k$, pre ktor� to neplat�. 
Polo�me $f(x)=\sum_{n=1}^\infty {(a_n-b_n)x^n\over 2^n}$. Zjavne $f(x)$ je identicky 
rovn� nule. Uva�ujme fciu $g(x)=x^{-k}f(x)=\sum_{n=1}^\infty {(a_n-b_n)x^{n-k}\over 2^n}$.
Je $\lim_{x\to 0} g(x)=\lim_{x\to 0} x^{-k}\cdot 0 = 0$, na druhej strane $\lim_{x\to
0}=g(x)=b_k-a_k$, �o je h�adan� spor.

E�te potrebujeme uk�za�, �e ak $\{a_n\}$ je ohrani�en�, tak aj 
$f(x)=\sum_{n=1}^\infty {a_nx^n\over 2^n}$ je ohrani�en� na $(-1,1)$. 
Nech $\forall n;|a_n|\leq c$. 
Potom ale
$$|f(q)|\leq c\cdot\sum_{n=1}^\infty \left({|q|\over 2}\right)^n = { c\over 1-{|q|\over 2} } \leq 2c$$

Opa�n� smer: Ka�d� spojit� funkcia je jednozna�ne ur�en� svoj�mi funk�n�mi hodnotami na 
�ubovo�nej hustej podmno�ine svojho defini�n�ho oboru. Nech $g$ je bijekcia z $N$ do
$Q\cap (-1,1)$ -- zjavne existuje. Potom ohrani�enej spojitej funkci� $f$ prirad�me 
postupnos� $\{a_n=f(g(n))\}$. (Teda vhodne zorad�me do postupnosti funk�n� hodnoty $f$ na 
racion�lnych ��slach z jej def. oboru.)

\item[c)] Jeden smer je zjavn�, v opa�nom zoberieme ka�d� prvok postupnosti re�lnych ��sel, arkus tangensom ho zobraz�me na $(-{\pi \over 2},{\pi \over 2})$, a ten interval potom u�apk�me na $(0,1)$.
\item[d)] To ist�, len to rob�me s funk�nou hodnotou.
\item[e)] Postupnos� $\{a_n\}_{n=0}^{\infty}$ zobraz�me na postupnos� $\{b_n\}_{n=0}^{\infty}$, kde $b_1=a_1\ \land\ b_{n+1}=b_n+a_{n+1}$.
\item[f)] Oba smery ako v $2.e)$.
\end{itemize}

\item[4.]
V prvom rade $f$ zo zadania chce by� injekt�vne, nie surjekt�vne, z existencie surjekt�vneho $f$
e�te nevypl�va, �e $|A|=|B|$.

Zjavne $B_0\supseteq A_0\supseteq B_1$. �alej indukciou. Nech $B_k\supseteq A_k\supseteq B_{k+1}$.
Ke�e $B_k\supseteq A_k$, tak aj $f(B_k)\supseteq f(A_k)$, �i�e $B_{k+1}\supseteq A_{k+1}$.
Analogicky z $A_k\supseteq B_{k+1}$ vypl�va $A_{k+1}\supseteq B_{k+2}$.

Zoberme $g$ zo zadania. Ozna�me $C=\bigcup_n (B_n-A_n)$, $D=B\setminus C$.
Trivi�lne plat�, �e ak $x\in A_n (B_n)$, tak $f(x)\in A_{n+1} (B_{n+1})$. 
Rozmyslite si, �e v�aka injekt�vnosti $f$ plat� aj opa�n� implik�cia.

Nech $g(x)=g(y)$. Ak $x,y\in D$, zjavne $x=y$. Ak $x\in C$ a $y\in D$ (alebo naopak), 
tak $\exists n$, $x\in B_n-A_n$, potom ale $f(x)\in B_{n+1}-A_{n+1}$. Teda $g(x)=f(x)\in C$,
ale $g(y)=y\in D$, spor. Ak $x,y\in C$, $g(x)=f(x)$ a $g(y)=f(y)$. Potom ale z injekt�vnosti
$f$ plat� $x=y$. Preto $g$ je injekt�vna. 

Nech teraz $z\in A$. Ak $z\in D$, zjavne $g(z)=z$. Nech teda $z\in C$. Zjavne $z\not\in B_0-A_0=B-A$.
Nech $k>0$ je najmen�ie tak�, �e $z\in B_k-A_k$. Ke�e $z\in B_k$, existuje $x\in B_{k-1}$ tak�, �e 
$f(x)=z$. Ke�e $f(x)\not\in A_k$, $x\not\in A_{k-1}$, preto $x\in C$ a teda $g(x)=z$. Preto $g$ je
surjekt�vna, a teda bijekcia.

Ak $f$ bola bijekcia, tak dostaneme $A_0=B_1$, $A_1=B_2$, \dots, odtia� $C=B$ a teda $f\equiv g$.

\item[5.]
Nech $X$, $Y$ s� mno�iny, nech $p:X\to Y$, $q:Y\to X$ s� injekcie. Polo�me $B=Y$, $A=p(X)$. Potom 
existuje injekcia $f:B\to A$ definovan� nasledovne: $f(z)=p(q(z))$. Pod�a predch�dzaj�cej �lohy 
existuje bijekcia $g:A\to B$. Potom ale zobrazenie $h:X\to Y$, kde $h(z)=g(p(z))$ je bijekcia 
medzi $X$ a $Y$, preto $|X|=|Y|$.
\end{itemize}

\end{document}
