\documentclass[11pt,a4paper]{report}
\usepackage[utf8]{inputenc}
\usepackage[czech]{babel}
\usepackage[T1]{fontenc}
\usepackage{mathptmx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{a4wide}
\usepackage{opakuj}
\makeatletter
\let\newmcodes@\relax
\makeatother

\usepackage{enumerate}
%\parindent=0mm
\usepackage{pgf,tikz}
\usetikzlibrary{arrows}
\usepackage{enumerate}
\usepackage{paralist}
\usepackage{xypic}

\usepackage{verbatim}

\usepackage[pdftex]{hyperref}
\hypersetup{hidelinks}

\DeclareMathOperator{\tg}{tg}
\DeclareMathOperator{\cotg}{cotg}
\DeclareMathOperator{\ch}{ch}
\DeclareMathOperator{\sh}{sh}
\DeclareMathOperator{\tgh}{tgh}
\DeclareMathOperator{\cotgh}{cotgh}
\DeclareMathOperator{\LM}{LM}
\DeclareMathOperator{\LT}{LT}
\DeclareMathOperator{\LC}{LC}
\newcommand{\dx}{\,\mathrm{d}x}
\newcommand{\dt}{\,\mathrm{d}t}
\newcommand{\ds}{\,\mathrm{d}s}

\newcommand{\I}{{\rm i}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\ce}[1]{\ensuremath{\left(#1 \right)}}
\newcommand{\cce}[1]{\ensuremath{\left[#1 \right]}}

\newcommand{\pp}[1]{\ensuremath{\left|#1\right|}}
\newcommand{\zk}[1]{\ensuremath{\left(#1 \right)}}
\newcommand{\zs}[1]{\ensuremath{\left<#1 \right>}}
\newcommand{\zh}[1]{\ensuremath{\left[#1 \right]}}
\newcommand{\zm}[1]{\ensuremath{\left\{#1 \right\}}}
\newcommand{\dcc}[1]{\ensuremath{\left\lfloor #1 \right\rfloor}}

\newcommand{\kon}[3]{\ensuremath{{#1} \equiv {#2}\pmod{#3}}}
\newcommand{\imp}{\ensuremath{\Rightarrow}}
\newcommand{\ekv}{\ensuremath{\Leftrightarrow}}
\newcommand{\bu}{\ensuremath{\bold{u}}}
\newcommand{\bv}{\ensuremath{\bold{v}}}

\newcommand{\psl}[1]{\ensuremath{\{{#1 }_n\}_{n=1}^\infty}}

\newtheorem{veta}{Věta}[chapter]
\newtheorem{lemma}[veta]{Lemma}
\theoremstyle{definition}
\newtheorem{definice}[veta]{Definice}
\newtheorem{dusledek}[veta]{Důsledek}
\newtheorem{prikl}{Příklad}[chapter]
\newtheorem{prikl*}[prikl]{*Příklad}
\newtheorem*{priklad}{Příklad}
\renewcommand{\qedsymbol}{$\blacksquare$}
\newtheorem{pr}{Návodný příklad}[chapter]
\newtheorem*{hint}{Hint}
\theoremstyle{remark}
\newtheorem{pozn}[veta]{Poznámka}

\overfullrule=2cm

\let\WITHSOLUTION 1 % added \usepackage{verbatim}
\newenvironment{reseni}
{ \ifx\WITHSOLUTION 1 \begin{proof}[Řešení]\else \comment \fi }
{ \ifx\WITHSOLUTION 1 \end{proof}\else \endcomment \fi }

\begin{document}
\setcounter{chapter}{10}
\chapter*{Opakování}
\begin{prikl}
Nechť $f \colon \R \to \R$ je monotónní funkce definovaná pro všechna $a \in \R$. Dokažte, že $f$ má nejvýše spočetně mnoho bodů nespojitosti.
\end{prikl}
\begin{reseni}% Dirichletův princip
Předpokládejme sporem, že funkce $f$ je definovaná na celém oboru reálných čísel, je monotónní a má nespočetně mnoho bodů nespojitosti. Bez újmy na obecnosti můžeme předpokládat, že $f(0) = 0$, v opačném případě bychom tuto funkci jen posunuli o nějakou konstantu. Dále předpokládejme, že $f$ má nespočetně mnoho bodů nespojitosti na intervalu $\ce{0, \infty}$ (případ pro opačný interval se udělá zcela stejným způsobem a~alespoň jedna z těchto možností nastat musí). Nakonec předpokládejme, že $f$ je neklesající (úvahy pro nerostoucí funkci by byly analogické).\\

Označme $K$ množinu všech bodů nespojitosti na intervalu $(0, \infty)$. Nejprve dokažme existenci $A \in \R^+$ takového, že $f$ má nespočetně mnoho bodů nespojitosti na intervalu $\ce{0, A}$. Pokud by takové $A$ neexistovalo, pak má $f$ nejvýše spočetně mnoho bodů nespojitosti na každém intervalu $\ce{0, n}$, kde $n \in \N$. Protože ale $\R^+ = \bigcup_{n \in \N} \ce{0,n}$, je též $K \cap R^+ = K \cap \bigcup_{n \in \N} \ce{0,n}$, přitom na pravé straně je spočetné sjednocení nejvýše spočetně velkých (ne nutně disjunktních) množin, což je nejvýše spočetná množina, a na levé straně je nespočetná množina. To je spor s neexistencí $A \in \R^+$. Označme dále $M$ (nespočetnou) množinu bodů nespojitosti funkce $f$ na intervalu $\ce{0,A}$.\\

Každému bodu $x \in M$ odpovídá nějaký skok funkce~$f$. Označme $g(x)$ velikost tohoto skoku. Formálně
\[
g(x) = \max\{f(x) - \lim_{y \to x^-} f(y), \lim_{y \to x^+} f(y) - f(x)\}.
\]
Nejprve potřebujeme ukázat, že $g(x) \colon M \to \R^+$ je dobře definovaná funkce. Obě jednostranné limity tedy musí být definované. Ukažme například existenci levostranné limity tj. existuje $L \in \R$ takové, že
\[
\forall \epsilon >0~\exists \delta >0~\forall y \in \ce{-\infty, x} (x-y)< \delta \Rightarrow |f(y) - L| < \epsilon.
\]
Položme $L = \sup_{y < x} f(x)$. Protože supremum je nejmenší horní závora víme, že pro libovolné $\epsilon > 0$ existuje $x_0 < x$ takové, že $f(x_0) > L - \epsilon$. Protože $f$ je monotónní, je pak na celém intervalu $(x_0,x)$ tato funkce mezi $L$ a $L - \epsilon$. Hledané $\delta$ je například $x - x_0 > 0$. Limita tedy existuje a~funkce $g$ je dobře definovaná.
Jistě $g(x) > 0$. V opačném případě by zde byla funkce $f$ spojitá, což je spor s~volbou $x \in M$.\\

Nyní chceme dospět ke sporu s tím, že počet bodů nespojitosti je nespočetný. Budeme chtít ukázat, že součet nespočetně mnoha libovolně malých kladných čísel musí být nekonečný (což pro spočetný součet platit nemusí). Tento součet je však potřeba formálně zavést. Položme proto
\[
\sum_{x \in M} g(x) = \sup_{\begin{subarray}{c}M' \subseteq M\\ M' \text{ spočetná} \end{subarray}} \sum_{x \in M'} g(x).
\]
Ukážeme, že takto definovaná suma je nutně nekonečná (tj. přestože bereme supremum pouze přes spočetné součty, dostáváme nekonečno. Nutně tedy každá rozumná interpretace součtu před nespočetnou množinu musí v tomto případě dát stejný výsledek). K tomuto využijeme Dirichletův princip.\\

Uvažme následující posloupnost intervalů
$I_0 = (1, \infty)$, $I_n = (\frac{1}{2^n}, \frac{1}{2^{n-1}}]$ pro $n \in \N$. Tyto intervaly jsou disjunktní a $\bigcup_{i \in \N_0} I_i = \R^+$, tvoří tedy rozklad na $\R^+$. Nutně tedy pro každé $x \in M$ existuje $i \in \N_0$ takové, že $g(x) \in I_i$. Protože existuje nespočetně mnoho bodů $x \in M$ a spočetné sjednocení spočetně velkých množin je pouze spočetné, musí podle Dirichletova principu existovat $n \in \N_0$ takové, že v~intervalu $I_n$ leží nespočetně mnoho (zejména tedy nekonečně mnoho) bodů $g(y)$, $y \in M$. Z~těchto nespočetně mnoha bodů $y \in M$ vybereme spočetně mnoho. Množinu těchto vybraných bodů označme~$N$. Pak platí
\[
\sum_{x \in M} g(x) \geq \sum_{x \in N} g(x) \geq \sum_{x \in N} \frac{1}{2^n} = \frac{1}{2^n} \sum_{x \in N} 1 = \infty.
\]
Funkce $f$ tedy na intervalu $(0,A)$ vyrostla nade všechny meze. Pak ale $f$ nemůže být definovaná v~$A$, vždyť $f$ je monotónní. To je nám dává hledaný spor.
\end{reseni}

\begin{prikl} % Gröbnerova báze
Řešte v $\R^3$\begin{alignat*}{4}
&x^2 &+ &y &+ &z  &= &1,\\
&x&+&y^2&+&z &=&1,\\
&x&+&y&+&z^2 &=&1.
\end{alignat*}
\end{prikl}
\begin{reseni}
Ukážeme algoritmický postup, jak řešit soustavu polynomiálních rovnic. Pokud je množina řešení konečná, obdržíme v rámci tohoto postupu polynom jedné proměnné, který budeme muset vyřešit. Náš postup využívá Buchbergerův algoritmus na hledání Gröbnerovy báze ideálu.\\

Zavedeme na polynomech lexikografické uspořádání, kde $x > y > z$. To znamená, že $f > g$, jestliže $f$ obsahuje člen s vyšším stupněm u $x$ než mají členy $g$ (v případě rovnosti pak u $y$ a nakonec u $z$). Například
\[
6xy^2 + 3yz^5 > 31xyz^12 + y^13z - 31 z^11.
\]
Původní soustavu přepíšeme jako
\begin{align*}
f_1 &= x^2 + y + z -1,\\
f_2 &= x+y^2+z-1,\\
f_3 &= x+y+z^2-1.
\end{align*}
Hledáme bod $(x,y,z) \in \R^3$, který nuluje polynomy $f_1, f_2, f_3$. Naším cílem bude hledat nové polynomy tak, aby $\ce{x,y,z}$ nuloval i tyto polynomy. Přitom se snažíme nové polynomy hledat co nejmenší v~našem lexikografickém uspořádání. Pokud je řešení jen konečně mnoho, pak takový polynom bude pouze v~proměnné $z$.\\

Označme $LT f_i$ vedoucí člen polynomu $f_i$. Označme $A$ nejmenší společný násobek vedoucích členů polynomů $f_i$ a $f_j$.\\
Pro všechna $i<j$ provádíme
\begin{itemize}
\item $S(f_i, f_j) = \frac{A}{LT f_i}f_i - \frac{A}{LT f_j}f_j$
\item pokud nedostaneme nulový polynom, budeme postupně odečítat vhodné násobky již zkonstruovaných polynomů tak, abychom přesně zrušili vedoucí člen (tj. abychom dostali polynom, který je v uspořádání menší)
\item pokud ani poté nedostaneme nulový polynom, přidáme jej mezi již existující polynomy (a počítáme další $S(f_i,f_j)$
\end{itemize}

Efektivita výše uvedeného algoritmu může hodně záviset na volbě $i,j$ při výpočtu $S(f_i, f_j)$. Algoritmus sice vždy zastaví, ale při nevhodné volbě pořadí $i,j$ může výpočet trvat velice dlouhou dobu. Proto se budeme snažit minimalizovat velikost nově vzniklého polynomu. Výpočet si můžeme ještě usnadnit tím, že nebudeme počítat $S(f_i, f_j)$ pro stejná $i,j$ dvakrát. Pokud jsme při prvním výpočtu přidali nějaký nový polynom, pak nám tento zabrání, abychom obdrželi něco nového. Dále nemusíme počítat $S(f_i, f_j)$ pro polynomy, které mají nesoudělné vedoucí koeficienty. Odečítáním vhodných násobků těchto polynomů jsme totiž schopni dostat nulu.\\

\begin{gather*}
S(f_2, f_3) = f_2 - f_3 = y^2 - y - z^2 + z\\
f_4 = y^2 - y - z^2 + z
\end{gather*}
Protože vedoucí koeficient $f_4$ je $y^2$, je tento nesoudělný s vedoucími koeficienty $f_1,f_2, f_3$. Počítejme proto
\begin{gather*}
S(f_1,f_2) = f_1 - xf_2 = -xy^2 - xz + x + y + z - 1 \stackrel{+y^2f_2}{\leadsto} -xz + x + y^4 + y^2z - y^2 + y + z -1 \stackrel{+ zf_2}{\leadsto}\\
x + y^4 + 2y^2z - y^2 +y + z^2 -1 \stackrel{-f_2}{\leadsto} y^4 + 2y^2z - 2y^2 +y + z^2 - z \stackrel{-y^2f_4}{\leadsto}\\
y^3 + y^2z^2 + y^2z - 2y^2 +y + z^2 - z \stackrel{-yf_4}{\leadsto} y^2z^2 + y^2z - y^2 + yz^2 - yz +y +  z^2 - z \stackrel{-z^2 f_4}{\leadsto}\\
y^2z - y^2 + 2yz^2  - yz +y + z^4  - z^3 + z^2 - z \stackrel{-zf_4}{\leadsto} -y^2 + 2yz^2 + y+ z^4 - z \stackrel{+f_4}{\leadsto}\\ 2yz^2  + z^4 - z^2\\
f_5 = 2yz^2  + z^4 - z^2
\end{gather*}
Nyní máme dvě možnosti, počítat $S(f_1,f_3)$, což vyjde podobně jako předchozí výsledek (dá se ukázat, že výsledek můžeme zredukovat na nulu), nebo $S(f_4, f_5)$. Zbytek má nesoudělné vedoucí členy. Počítejme proto tedy
\begin{gather*}
2\cdot S(f_4,f_5) = 2\cdot (2z^2f_4 - yf_5) \leadsto{+(z^2 + 1)}{f_5} z^6 - 4z^4 + 4z^3 - z^2\\
f_6 = z^6 - 4z^4 + 4z^3 - z^2
\end{gather*}
Dostáváme polynom jedné proměnné. Je tedy pouze konečně mnoho možností pro $z$. Ze symetrie je konečně mnoho možností pro $x$ a $y$. Již teď vidíme, že množina řešení soustavy bude konečná. Nalezněme tedy kořeny polynomu $f_6$. Jistě
\[
f_6 = z^2 \cdot (z-1)^2 \cdot (z^2 + 2z - 1)
\]
Odtud $z \in \{0,1,-1\pm \sqrt{2}\}$.
\begin{itemize}
\item $z = 0,1$: dosazením do $f_4$ dostáváme, že $y = 0,1$, což spolu s původní soustavou dává tři řešení
\[
\ce{0,0,1}, \quad \ce{0,1,0}, \quad \ce{0,0,1}.
\]
\item $z = -1 \pm \sqrt{2}$: dosazením do $f_5$ dostáváme, že $y = -1 \pm \sqrt{2}$ a dosazením do $f_2$ obdržíme, že $x = -1 \pm \sqrt{2}$, celkem tedy dostáváme další dvě řešení
\[
\ce{-1 + \sqrt{2},-1 + \sqrt{2},-1 + \sqrt{2}} \quad \text{ a }\quad \ce{-1 - \sqrt{2},-1 - \sqrt{2},-1 - \sqrt{2}}.
\]
\end{itemize}
Celkem má úloha 5 výše uvedených řešení.
\end{reseni}


\begin{prikl}%14.6-72
Dokažte, že pro~libovolné $n\in\N$ platí, že $2^n$ dělí $1+\dcc{\zk{3+\sqrt5}^n}$.
\end{prikl}
\begin{reseni}
Všimněme si, že
\[
\ce{\frac{1\pm\sqrt5}{2}}^2 = \frac{3\pm\sqrt5}{2}.
\]
Přitom víme, že Fibonacciho čísla můžeme zadat vzorcem pro $n$-tý člen
\begin{align*}
F_n &= \frac1{\sqrt5} \cce{\ce{\frac{1+\sqrt5}{2}}^n - \ce{\frac{1-\sqrt5}{2}}^n},\\
F^2_n &= \frac15\cce{\ce{\frac{3+\sqrt5}{2}}^n + \ce{\frac{3-\sqrt5}{2}}^n - \ce{-1}^n},\\
2^n \cdot 5 \cdot F^2_n &= \ce{3+\sqrt5}^n + \ce{3-\sqrt5}^n - \ce{-2}^n
\end{align*}
Protože $0< 3-\sqrt5< 1$, platí
\[
2^n \cdot \ce{5 \cdot F^2_n + \ce{-1}^n} =  \ce{3+\sqrt5}^n + \ce{3-\sqrt5}^n = \dcc{\zk{3+\sqrt5}^n} + 1,
\]
což je jistě číslo dělitelné $2^n$.
\end{reseni}
\end{document}