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