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