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

\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 2. 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

\centerline{\bf\large Dirichletov princ�p (DP)}
\begin{enumerate}
  \item %1
    Mo�n�ch s��tov je 11 (od 2 po 12), preto treba hodi� aspo� $12$-kr�t.
  \item %2
    Mo�n�ch s��tov je 16 (od 3 po 18), preto treba hodi� aspo�
    $(3.16+1)=49$-kr�t.
  \item %3
    \begin{itemize}
      \item[a)]
        Rozl��en� kocky : r�znych dvoj�c je $6.6=36$, treba aspo�
        $2.36+1=73$ hodov.
      \item[b)]
        Nerozl��en� kocky : r�znych dvoj�c je 21, treba aspo�
        $2.21+1=43$ hodov.
    \end{itemize}
  \item %4
    \begin{itemize}
      \item[a)]
        Sporom. Ak s� v�etky men�ie ako $b\over n$, s��et je men�� ako
        $n.{b\over n}=b$. Spor.
      \item[bcd)]
        A� na ostr�/neostr�/obr�ten� nerovnosti to ist� ako a).
    \end{itemize}
  \item %5
    Z Eulerovej vety $\then$, �e mnohosten m� 21 hr�n, teda s��et stup�ov
    vrcholov je 42. Ke�e $42\geq 37=9.4+1$, z DP $\then$, �e z niektor�ho
    vrcholu vych�dza aspo� 5 hr�n, q.e.d.
  \item %6
    Hr�n je 11, s��et po�tov hr�n v sten�ch 22, stien 7, z DP $\then$, �e
    $\exists$ stena s aspo� 4 hranami, ale ke�e ka�d� stena m� aspo� 3
    hrany, maj� steny dokopy aspo� 21 hr�n, preto jedin� mo�nos� je, �e jedna
    stena m� 4 hrany a v�etky ostatn� po 3 hrany.
  \item %7
    Z�hradu $80\times 90$ rozde�me na $10\times 18$ obd�nikov tvaru
    $8\times 5$. M�me 365 stromov v 180 obd�nikoch, z DP $\then$, �e v
    niektorom s� aspo� 3.
  \item %8
    Obd�nik $27\times 36$ rozde�me na $9\times 18$ obd�nikov tvaru
    $3\times 2$ a ka�d� z nich uhloprie�kou na dva trojuholn�ky s plochou 3.
    M�me 1945 bodov v $9.18.2=324$ trojuholn�koch, z DP $\then$ q.e.d.
  \item %9
    13 vysiela�ov pokryje max. plochu
    $13.\pi.80^2=83200.\pi<268138{\rm\ km}^2$.
  \addtocounter{enumi}{4}
%  \item %10
%  \item %11
%  \item %12
%  \item %13
    �tvorec rozre�eme na 25 �tvor�ekov so stranou $1\over 5$. Z DP v
    niektorom le�ia aspo� 3 z 51 bodov. Ke�e
    ${\sqrt{2} \over 2}\cdot{1\over 5}={\sqrt{2}\over 10}<{1\over 7}$,
    cel� tento �tvorec le�� v kruhu so stredom v jeho priese�n�ku uhloprie�ok
    a polomerom $1\over 7$. V tomto kruhu le�ia teda aspo� 3 body, q.e.d.
  \item %14
    Ozna�me na�e ��sla $c_1,\dots,c_{82}$. Ak niektor� z ��sel
    $c_1-c_2,c_1-c_3,\dots,c_1-c_{82}$ d�va po del. 81 zvy�ok 0, vyhrali sme.
    Ak nie, m�me 81 ��sel, ktor� d�vaj� nanajv�� 80 zvy�kov, pod�a DP
    niektor� dve d�vaj� rovnak� zvy�ok. BUNV nech s� to $c_1-c_i=81a+z$,
    $c_1-c_j=81b+z$, pri�om $i\not =j$ a $0\leq z<81$. Potom ale
    $c_i-c_j=(c_1-c_j)-(c_1-c_i)=(81b+z)-(81a+z)=81(b-a)$.
  \item %15
    Dok�eme tvrdenie, z ktor�ho bud� vypl�va� tvrdenia 16 a 17. Ku ka�d�mu
    $n$ nes�delite�n�mu s 10 existuje ��slo tvaru 111\dots1, ktor� je n�m
    delite�n�. D�kaz: Zoberme ��sla $1, 11,\dots,11...1$, z ktor�ch posledn�
    m� $n+1$ cifier. Z DP niektor� dve d�vaj� rovnak� zvy�ok po delen� $n$.
    Preto ich rozdiel je delite�n� $n$. (T�m je dok�zan� tvrdenie 16, lebo
    ich rozdiel je tvaru $11\dots100\dots0$.)
    Pre $n$ nes�delite�n� s 10 z toho dost�vame, �e ke�e $n$ del�
    $11\dots100\dots0=11\dots1.10^k$, del� aj $11\dots1$.
  \item %16
    Ke�e prvo��sla r�zne od 2 a 5 s� nes�delite�n� s 10, m��me pou�i�
    predch�dzaj�cu vetu.
  \item %17
    Ozna�me ��sla $a_1,\dots,a_n$. �alej ozna�me $b_i=a_1+\dots+a_i$. Ak
    niektor� $b_i$ d�va zvy�ok 0 po delen� $n$, hotovo, inak m�me $n$ ��sel,
    ktor� d�vaj� najvac $n-1$ zvy�kov. Z DP niektor� 2 d�vaj� rovnak� zvy�ok,
    preto ich rozdiel $b_j-b_i$ je delite�n� $n$. Ich rozdiel ale je
    $a_{i+1}+\dots+a_j$.
  \addtocounter{enumi}{1}
  % \item %18
  \item %19
    Vypl�va z �lohy 20.
  \item %20
    Zoberme ��sla $p,p^2,\dots,p^{10^{n+1}+1}$. Niektor� dve z nich pod�a DP
    d�vaj� rovnak� zvy�ok po delen� $10^{n+1}$. Nech s� to $p^k$ a $p^l$.
    Potom $10^{n+1}| p^l-p^k=p^k(p^{l-k}-1)$. Ke�e 10 je nes�delite�n�
    s $p$, $\then$ z toho, �e $10^{n+1}| p^{l-k}-1$, �i�e
    $p^{l-k}\equiv 1 ({\rm mod}\ 10^{n+1})$. To ale znamen�, �e $p^{l-k}$ kon�� skupinou
    $n$ n�l a jednotkou.
  \item %21
    Sporom. Keby boli najviac 2 ofic. jazyky, tak ofici�lnymi jazykmi hovor�
    dokopy najviac 30 deleg�tov. Ka�d�m z ostatn�ch 9 jazykov hovoria najviac
    4 deleg�ti. To ale znamen�, �e deleg�tov je najviac 66 -- spor.
  % \item %22
  % \item %23
  % \item %24
  % \item %25
  % \item %26
  % \item %27
  % \item %28
  % \item %29
  % \item %30
  % \item %31
  % \item %32
  % \item %33
  % \item %34
  % \item %35
\end{enumerate}
\centerline{\bf\large Spo��tate�n� mno�iny}
\begin{enumerate}
  \addtocounter{enumi}{10}
  % \item %1
  % \item %2
  % \item %3
  % \item %4
  % \item %5
  % \item %6
  % \item %7
  % \item %8
  % \item %9
  % \item %10
    \item %11
    Intervalu $\left( a,b\right)$ prira�me dvojicu $a,b\in \Q\times \Q$. Zjavne
    je to injekcia, preto m� mno�ina v�. intervalov s rac. koncami mohutnos�
    nanajv�� rovn� mohutnosti mno�iny $\Q\times \Q$, t� je ale spo��tate�n�.
  \item %12
    Napr. $X=\Q^n$. Rac. ��sla s� hust� podmno�ina $\R$, teda 
    $\forall r,\eps\in \R;~ \exists q\in \Q;~ |r-q|<\eps$. Preto ke� m�me
    $a=(a_1,\dots,a_n)$, sta�� n�js�
    $x_1,\dots,x_n\in \Q; |a_i-x_i|<{\eps\over n}$. Tak� $x_i$ ur�ite existuj�
    a z�rove� je potom $\sum |x_i-a_i|<n\cdot {\eps\over n}=\eps$, tak�e $X=Q^n$
    naozaj vyhovuje.
  \item %13
    V ka�dom z nich le�� aspo� jedno rac. ��slo. Ka�d�mu intervalu prira�me
    niektor� rac. ��slo z neho. Ke�e s� disjunktn�, je to injekcia, teda
    mohutnos� mno�iny intervalov je nanajv�� rovn� mohutnosti $\Q$, teda
    mno�ina intervalov je spo��tate�n�.
  \item %14
    \begin{itemize}
      \item[a)]
        Z anal�zy vieme, �e pre rast�cu funkciu je
        $\lim_{x\to a+} f(x)=\sup_{x<a} f(x)$.
      \item[b)]
        $\dots$ nejako cez disjunktn� intervaly na osi $y$.
    \end{itemize}
  \item %15
    bolo na cvik�ch
  \item %16
    Zjavne $T_k({0})=\{ (0,0,\dots,0,\dots)\}$, preto $|T_k({0})|=1$.

    Ke� $X$ obsahuje aspo� 2 prvky (BUNV 0 a 1), m��me prirodzen�mu
    ��slu $n$ priradi� postupnos� $n$ n�l a nekone�ne ve�a jednotiek, preto je ur�ite
    $|T_k(X)|\succeq\aleph_0$. �peci�lne $|T_k({0,1})|\succeq\aleph_0$,
    $|T_k(\N)|\succeq\aleph_0$ a $|T_k(\Q)|\succeq\aleph_0$.

    Zobrazme ka�d� postupnos� z $T_k(X)$ na kone�n� postupnos�, ktor� z nej
    dostaneme, ke� z konca vynech�me v�etky rovnak� �leny okrem jedn�ho.
    (T.j. napr. postupnos� $3,1,4,1,5,2,2,$ $\dots,2,\dots$ na $3,1,4,1,5,2$.)
    Toto je zjavne injekcia, preto mohutnos� $T_k(X)$ je nanajv�� rovn�
    mohutnosti mno�iny v�etk�ch kone�n�ch postupnost� prvkov $X$.

    Mno�ina v�etk�ch kone�n�ch postupnost� 0 a 1 m� mohutnos� $\aleph_0$,
    lebo ka�d� z nich zodpoved� nejak�mu kone�n�mu desatinn�mu rozvoju
    re�lneho (a teda z�rove� racion�lneho) ��sla. (Teda napr. postupnosti 0,1,0,1,1,1
    prirad�me ��slo $0,010111{\bf 1}$ -- t� jednotku na konci mus�me ku ka�d�mu
    prida� kv�li postupnostiam, ktor� kon�ia 0.) Mno�inu kon. postupnost�
    prir. ��sel zobraz�me do mno�iny kon. postupnost� 0 a 1 tak, �e ��slo $n$
    zak�dujeme postupnos�ou $n$ n�l a jednotkou. Mno�inu kon. postupnost�
    rac. ��sel zobraz�me do postupnosti prir. ��sel tak, �e ��slu
    ${p\over q}; p\in Z,q\in N,(p,q)=1$ prirad�me $1,p,q$ ak $p\geq 0$ a
    $2,-p,q$ ak $p<0$. Preto aj mno�ina v�etk�ch kon. postupost� prirodzen�ch,
    resp. racion�lnych ��sel m� mohutnos� $\aleph_0$.

    Teda je $|T_k({0,1})|\preceq\aleph_0$,
    $|T_k(\N)|\preceq\aleph_0$, $|T_k(\Q)|\preceq\aleph_0$, a teda pod�a C-B
    vety $|T_k({0,1})|=|T_k(\N)|=|T_k(\Q)|=\aleph_0$.

    Zjavne ka�d�mu re�lnemu ��slu m��me priradi� nekone�n� postupnos� zlo�en�
    zo sam�ch tak�ch ��sel, preto $|T_k(\R)|\succeq c$. Keby sme dok�zali, �e
    mohutnos� mno�iny v�etk�ch kone�n�ch postupnost� re�lnych ��sel je $c$,
    boli by sme hotov�. Ke�e sa mi to u� nechce rozpisova�, vyu�ijem bez
    d�kazu, �e $|\R^n|=|\R|=|\left( 0,1\right) |$. Ka�dej kone�nej postupnosti
    $a_1,\dots,a_n$ re�lnych ��sel viem pod�a pr�ve uvedenej vety priradi�
    ��slo $x\in\left( 0,1\right)$. Ke� jej prirad�m ��slo $n+x$, dostanem
    takto injekciu z mno�iny v�etk�ch kon. postupnost� re�lnych ��sel do
    R, tak�e naozaj $|T_k(\R)|=c$.
  \item %17
    Ke�e $P$ je spo�. mno�ina, m��me jej prvky ozna�i� $P=\{ p_1,p_2,\dots\}$.
    Ke� bude druh� hr�� �aha� tak, �e v $n$-tom �ahu d� ��slicu, ktor� $p_n$
    nem� na $2n$-tom mieste, v�sledn� postupnos� nem��e patri� do $P$. (D�kaz
    ako pri Cantorovej diagon�lnej met�de - ke� tam patr�, nech je to $p_k$,
    ale od $p_k$ sa v�sledn� postupnos� l��i na $2k$-tom mieste.)
  \item %18
    Pre $P=\{0,1\}^N$ nech druh� hr�� �ah� ako chce, v�sledok bude patri� do $P$.
    Preto druh� hr�� nem� vyhr�vaj�cu strat�giu, �i�e $P$ nie je spo��tate�n�.
  \item %19
    Mno�ina v�etk�ch podgr�p grupy $(\Z,+)$ je spo��tate�n�, lebo ka�d� podgrupa je 
    jednozna�ne ur�en� svoj�m najmen��m kladn�m prvkom.
\end{enumerate}
\centerline{\bf\large Pr�klady r�znych typov}
\begin{enumerate}
  \addtocounter{enumi}{2}
  % \item %1
  % \item %2
  \item %3
    Ur�ite vieme vybra� $k+1$ ��sel -- napr. v�etky nep�rne. Sta�� dok�za�,
    �e nevieme viac. Indukciou.
    \begin{itemize}
      \item[$1^{\circ}$]
        Z 1 ��sla vieme vybra� najviac 1.
      \item[$2^{\circ}$]
        Majme $2k+1$ ��sel. Ak vyberieme ��slo $2k+1$, zo zvy�n�ch �iadna
        dvojica nesmie ma� s��et $2k+1$, preto z ka�dej z dvoj�c $[1,2k],
        [2,2k-1],\dots,[k,k+1]$ m��me vybra� najviac jedno ��slo, dokopy
        najviac $k+1$ ��sel.

        Ak ��slo $2k+1$ nevyberieme: Ak vyberieme $2k$, tak u� z ka�dej z
        dvoj�c $[1,2k-1],\dots,[k-1,k+1]$ m��me vybra� najviac jedno a navy�e
        m��me e�te vybra� $k$. Tak�e vyberieme najviac $1+(k-1)+1=k+1$ ��sel.
        Ak nevyberieme ani $2k$, vyber�me vlastne u� len z $2k-1$ ��sel, z
        nich pod�a ind. predp. vieme vybra� najviac $k$ ��sel.
    \end{itemize}
    Preto m��me vybra� najviac $k+1$ ��sel.
  \item %4
    Ka�d� s��et je z mno�iny $\{ -n,\dots,-1,0,1,\dots,n\}$. T� m� $2n+1$
    prvkov, riadkov, st�pcov a diagon�l je v�ak dokopy $2n+2$, preto tak�
    matica neexistuje.
  \item %5
    Ka�d� m� medzi 0 a $n-1$ zn�mymi. Ak �iadni dvaja nemaj� rovnako, znamen�
    to, �e jeden m� 0 zn�mych, at�., a� jeden m� $n-1$ zn�mych. Potom ale
    ten, �o pozn� v�etk�ch, sa pozn� aj s t�m, ktor� nepozn� nikoho, spor.
  \addtocounter{enumi}{4}
  % \item %6
  % \item %7
  % \item %8
  % \item %9
  \item %10
    Mo�n� v�sledky s� (v tvare [jednotky, dvojky, trojky]) : $[3,0,0]$,
    $[0,3,0]$, $[0,0,3]$, $[2,1,0]$, $[2,0,1]$, $[1,2,0]$, $[1,0,2]$,
    $[0,2,1]$, $[0,1,2]$, $[1,1,1]$. Mo�n�ch
    v�sledkov je teda 10, �tudentov 41 a z DP $\then$ dok. tvrdenie.
  \item %11
    Predstavme si kompletn� graf, ktor�ho vrcholy s� �lenovia komisie.
    Ofarbime hranu medzi $A$ a $B$, ke� s� spolu na zasadnut�. Zo zadania
    vieme, �e ka�d� hranu ofarb�me najviac raz. Pri jednom zasadan� v�ak
    ofarb�me ${10 \choose 2}=45$ hr�n, zasadan� bolo 40, teda tento graf
    mus� ma� aspo� 1800 hr�n. $K_n$ m� $n \choose 2$ hr�n. Je teda
    \begin{eqnarray*}
    1800 & \leq & {n \choose 2}={n.(n-1)\over 2}={1\over 2}n^2-{1\over 2}n\\
    n^2-n-3600 & \geq & 0\\
    \end{eqnarray*}
    Zjavne pre $n\leq 60$ je $n^2-n-3600<n^2-3600\leq 60^2-3600=0$, preto $n>60$.
  \item %12
    Podobne. Vrcholy s� �udia, ke� vytvor�me komisiu, v�etk�ch �lenov posp�jame
    hranami. Zo zadania $\then$, �e �iadni dvaja �udia nie s� spolu vo viac
    ako 1 komisii, preto ka�d� hranu ofarb�me max. raz. Hr�n je
    ${25\choose 2}=300$, 1 komisia ofarb� $10$ hr�n, preto je komisii najviac 30.
  \item %13
    To ist� ako �loha 7, len v svetlomodrej.
  % \item %14
  % \item %15
  % \item %16
  % \item %17
  %   Teda toto bol bu� blb� vtip, alebo som to zle pochopil.
  % \item %18
\end{enumerate}
\end{document}
