\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}
\usepackage{enumerate}
%\parindent=0mm
\usepackage{pgf,tikz}
\usetikzlibrary{arrows}
\usepackage{enumerate}
\usepackage{paralist}
\usepackage{xypic}

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

\DeclareMathOperator{\tg}{tg}
\DeclareMathOperator{\cotg}{cotg}
\DeclareMathOperator{\ch}{ch}
\DeclareMathOperator{\sh}{sh}
\DeclareMathOperator{\tgh}{tgh}
\DeclareMathOperator{\cotgh}{cotgh}
\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)}}	% definice \ce 	- argument bude v~kulatych zavorkach
\newcommand{\cce}[1]{\ensuremath{\left[#1 \right]}}	% definice \cce	- argument bude v~hranatych zavorkach

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

\begin{document}
\setcounter{chapter}{3}
\chapter*{Invarianty a Dirichletův princip}
\section*{Invarianty}
Chceme-li hovořit o invariantech, musíme se zabývat úlohami, ve kterých máme počáteční stav, povolené kroky a koncový stav. Otázkou pak je, zda se můžeme z počátečního stavu dostat do koncového stavu za použití povolených kroků. Invariantem v~takovém procesu je něco, co se nemění. Tímto způsobem se často dokazuje neexistence řešení (tj. že není možné dojít z počátečního stavu do koncového). V~informatice se invariantů používá také k~dokazování korektnosti algoritmů (tj. pokud algoritmus skončí, jeho výstup bude správný).
\begin{pr}
Ve vrcholech pravidelného šestiúhelníka jsou po směru hodinových ručiček napsaná čísla 1, 0, 1, 0, 0, 0. V každém kroku můžeme navýšit hodnotu ve dvou sousedních vrcholech o~1. Je možné, aby po konečně mnoha takových krocích bylo ve všech vrcholech napsáno stejné číslo?
\end{pr}
\begin{proof}[Řešení]
Označme $a_1, a_2, \dots, a_6$ čísla ve vrcholech šestiúhelníku. Uvažme hodnotu
\[
V = a_1 - a_2 + a_3 - a_4 + a_5 - a_6.
\]
V libovolném kroku zvýšíme hodnotu $a_i$ o 1, ale stejným způsobem zvýšíme hodnotu $a_{j}$, $j \equiv i+1 \pmod{6}$. Proto jejich rozdíl zůstává stejný. Hodnota $V$ je tedy invariant. Na začátku platí $V = 2$, v koncovém stavu je $V = 0$. Proto koncový stav není z počátečního dosažitelný.
\end{proof}
\begin{pr}
Na tabuli jsou napsána čísla $1,2,\dots,4n-1$. V každém kroku smažeme dvě čísla a~místo nich napíšeme jejich rozdíl. Dokažte, že na konci (tj. po $4n-2$ krocích) zůstane na tabuli sudé číslo.
\end{pr}
\begin{proof}[Řešení]
Označme číslo $V$ součet všech čísel, která jsou na tabuli napsaná. Budeme chtít ukázat, že invariantem je parita tohoto čísla. Označme $x$, $y$ čísla, která se chystáme smazat. V~následujícím kroku bude
\[
V_{new} = V_{old} - x - y + (x-y) = V_{old} -2y \equiv V_{old} \pmod{2}.
\]
Parita $V$ je tedy skutečně invariantem. Nyní nám stačí ukázat, že $V$ je na začátku sudé. Dostáváme
\[
V = \sum_{k = 1}^{4n-1} k = \frac{4n \cdot \ce{4n-1}}{2} = 2n\cdot\ce{4n-1} \equiv 0 \pmod{2}.
\]
\end{proof}

\section*{Dirichletův princip}
\begin{center}
Máme-li alespoň $nk+1$ předmětů v $k$ přihrádkách,\\
pak existuje alespoň jedna přihrádka s~alespoň $n+1$ předměty.
\end{center}
\begin{pr}
V místnosti je $n$ lidí. Každý si s každým podá ruku. Dokažte, že v průběhu podávání rukou vždy existují dva lidé, kteří si podali ruce se stejným počtem lidí.
\end{pr}
\begin{proof}[Řešení]
Počet lidí je $n$. Počet potřesení rukou každého člověka je číslo z množiny $\{0,1,2,\dots, n-1\}$. Není však možné, aby u dvou lidí nastaly případy $n-1$ a 0 současně. Proto rozdělujeme $n$ lidí do $n-1$ přihrádek a tedy alespoň dva lidé jsou ve stejné přihrádce (tj. podali si ruce se stejným počtem lidí).
\end{proof}


\section*{Příklady}
%%%%%%%%%%% Invarianty
\begin{prikl}
Buď $n \in \N$. Na tabuli je napsáno $2n+1$ celých čísel. V každém kroku smažeme libovolné tři z nich, označme je $x$, $y$, $z$, a místo nich napíšeme číslo $\frac{x \cdot y}{z} \in \Q$ ve zkráceném tvaru (tj. zbavíme se složených zlomků a upravíme do tvaru, kdy čitatel a jmenovatel jsou nesoudělná celá čísla). Zdůvodněte, že se tímto způsobem dostaneme do situace, kdy na tabuli bude jediné racionální číslo. Označme jej $t = \frac{r}{s}$. Nalezněte nutnou a postačující podmínku k tomu, aby nejvyšší mocnina daného prvočísla $p$ dělící $r \cdot s$ byla sudá.
\end{prikl}
\begin{proof}[Řešení]
Nejprve ukažme, že tímto postupem získáme na tabuli jediné číslo. Počet čísel je na začátku lichý. V každém kroku snížíme počet čísel o 2, tedy paritu nezměníme. Zřejmě se dostaneme do situace, kdy budeme mít na tabuli 3 čísla a~v~dalším kroku číslo jedno.\\
Nechť jsou na tabuli čísla $a_1 = p^{t_1}\cdot\frac{r_1}{s_1}$, $\dots$, $a_k = p^{t_k}\frac{r_k}{s_k} \in \Q$, kde $t_i \in \Z$, $(r_i, p) = (s_i, p) = 1$. Označme 
\[
V = \sum_{i=1}^{k} t_i.
\]
Vyberme čísla $a_h$, $a_i$, $a_j$. Jejich smazáním a nahrazením za $\frac{a_i \cdot a_j}{a_h}$ dostáváme po úpravě na jednoduchý zlomek
\[
V - 2t_h \equiv V \pmod{2}.
\]
Dále si uvědomme, že krácení ve zlomku nám paritu mocniny $p$ dělící $V$ taktéž nezmění. Parita $V$ je tedy invariantem. Zřejmě též parita $V$ pro $\frac{r}{s}$ a $r \cdot s$ je stejná.  Odtud okamžitě dostáváme, že hledaná podmínka je 
\[
V \equiv 0 \pmod 2.
\]
\end{proof}
%%%%%


\begin{prikl}%6
Na stole je $a$ červených, $b$ zelených a $c$ modrých žetonů. V každém kroku odebereme dva žetony různé barvy a přidáme žeton barvy zbývající. Dokažte, že pokud na konci zbývá jediný žeton, jeho barva závisí pouze na počátečním stavu.
\end{prikl}
\begin{proof}[Řešení]
Všimněme si, že parita počtu žetonů dané barvy se v každém kroku mění (hodnota se změní o $\pm 1$). Invariantem je tedy rovnost či nerovnost parit mezi počty žetonů daných barev. Odtud dostáváme, že nutně jedno z čísel $a$, $b$, $c$ má jinou paritu než zbylá dvě. Příslušná barva je pak ta, kterou bude mít poslední žeton.
\end{proof}
%%%%%


\begin{prikl}%27
Mějme na začátku dvojici přirozených čísel. V každém kroku můžeme $(x,y)$ nahradit za $(y,x)$, $(x+y, y)$ nebo $(x-y,y)$.
\begin{enumerate}
\item Lze se z počátečního stavu $(1,2)$ dostat do stavu $(19,79)$ respektive $(819,357)$?
\item Pro počáteční dvojici $(a,b)$ určete množinu stavů, do které jsme schopni se dostat.
\end{enumerate}
\end{prikl}
\begin{proof}[Řešení]
(Abychom nezaměňovali dvojici $(x,y)$ s největším společným dělitelem čísel $x$, $y$, budeme jej značit $\gcd(x,y)$.) Snadno nahlédneme, že hledaným invariantem je největší společný dělitel. Zřejmě totiž $\gcd(x,y) = \gcd(y,x) = \gcd(x+y,y) = \gcd(x-y,y)$. Povolené operace nám povolí provádět Euklidův algoritmus: nejprve větší číslo dostaneme na první pozici a pak jej zmenšujeme, než dostaneme číslo menší, než je na pozici druhé - totiž zbytek po dělení. To lze opakovat do chvíle, kdy jedno z~dvojice čísel je nulové. Díky tomu, že ke každé operaci máme operaci inverzní, lze se též z $(d,0)$ dostat na libovolné $(r,s)$, kde $\gcd(r,s) = d$. To nám dává odpověď na obě otázky:
\begin{enumerate}
\item Do stavu $(19,79)$ se dostat lze, neboť se jedná o různá prvočísla. Do stavu $(819,357)$ se dostat nemůžeme, neboť $\gcd{819, 357} \geq 3$.
\item Množina stavů, do které jsme schopni se dostat je $\{(x,y) \in \N^2 \mid \gcd{x,y} = \gcd(a,b)\}$.
\end{enumerate}
\end{proof}
%%%%%


\begin{prikl}%47
V pravidelném
\begin{enumerate}
\item pětiúhelníku
\item šestiúhelníku
\end{enumerate}
jsou zakresleny všechny úhlopříčky. Na začátku máme v každý vrchol a v každý průsečík úhlopříček označený číslem 1. V jednom kroku můžeme změnit znaménko u označení všech bodů na vybrané straně či diagonále. Je možné posloupností kroků změnit označení všech bodů na -1?
\end{prikl}
\begin{proof}[Řešení] % PRO DRUHÝ PŘÍPAD JE POTŘEBA DOPLNIT OBRÁZEK.
\begin{enumerate}
\item Invariantem je parita počtu $1$ ve vrcholech pětiúhelníku. Počáteční a koncový stav mají tuto hodnotu rozdílnou, odpověď je tedy ne.
\item Lze vybrat vhodným způsobem 9 průsečíků úhlopříček tak, aby parita počtu 1 byla invariantní. Odpověď je tedy opět ne.
\end{enumerate}
\end{proof}
%%%%%


\begin{prikl}%42 - IMO 1993, AUO 1992.
Na nekonečné šachovnici hrajeme následující hru. Na začátku máme v každém vrcholu čtverce velikosti $n \times n$ jednu figuru (zbytek nekonečné šachovnice je prázdný). V jednom tahu vybereme figuru a horizontálním či vertikálním skokem s ní přeskočíme jejího souseda do volného políčka za tímto sousedem (tj. skáčeme podobně jako v dámě, jen směr skoku není diagonální, ale vertikální či horizontální). Figuru, která byla přeskočena, z šachovnice odebereme. Nalezněte všechny hodnoty $n$, pro které je možné skončit s jedinou figurou na šachovnici.
\end{prikl}
\begin{proof}[Řešení] % ZDE JE CELÉ ŘEŠENÍ ZALOŽENÉ NA OBRÁZKU, JE POTŘEBA DODĚLAT.

\end{proof}



%%%%%%%%%%% Dirichlet
\begin{prikl}%15
Uvažujme dvacet po dvou různých přirozených čísel menších než 70. Dokažte, že mezi všemi rozdíly dvojic existují čtyři, které jsou si rovny.
\end{prikl}
\begin{proof}[Řešení]
%Nestačí jen uvážit počet rozdílů a počet možných hodnot rozdílů. 
Seřaďme a označme tato čísla
\[
0 < a_1 < a_2 < \dots < a_{20} < 70.
\]
Ukážeme dokonce, že hledané čtyři stejné rozdíly lze nalézt ve tvaru $a_{i+1} - a_i$. Jistě
\[
1 \leq (a_2 - a_1) + (a_3 - a_2) + \dots + (a_{20} - a_{19}) = a_{20} - a_1 \leq 68.
\]
Předpokládejme, že $a_{i+1} - a_{i} = k$ pro nejvýše 3 $i \in \{1,2,\dots,19\}$. Pak protože $a_{i+1} - a_i \in \N$, dostáváme
\[
68 \geq (a_2 - a_1) + (a_3 - a_2) + \dots + (a_{20} - a_{19}) \geq 3 \cdot 1 + 3\cdot 2 + 3 \cdot 3 + 3 \cdot 4 + 3 \cdot 5 + 3 \cdot 6 + 7 = 70,
\]
což je spor.
\end{proof}
%%%%%


\begin{prikl}%19
Buď $n$ přirozené číslo nedělitelné 2 ani 5. Dokažte, že existuje násobek čísla $n$, jehož dekadický zápis se sestává ze samých jedniček (například pro $n = 3$ máme $37\cdot 3 = 111$).
\end{prikl}
\begin{proof}[Řešení]
Uvažme čísla 
\[
1, 11, \dots, \underbrace{11\dots1}_{n}.
\]
Máme $n$ možných zbytků po dělení číslem~$n$. Pokud je nějaký zbytek nulový, pak jsme hotovi. V opačném případě existují dvě čísla, která dávají stejný zbytek po dělení~$n$. Jejich rozdíl je tedy dělitelný~$n$ a~máme 
\[
n \mid \underbrace{1\dots1}_{k}0\dots0.
\]
Protože ale $(n,10) = 1$, platí, že 
\[
n \mid \underbrace{11\dots1}_{k}.
\]
\end{proof}
%%%%%


\begin{prikl}%21
Buď $S$ množina $2n+1$ bodů taková, že v libovolné trojici bodů z $S$ jsou alespoň dva z nich vzdáleny nejvýše 1. Dokažte, že existuje podmnožina $S$ o $n+1$ bodech taková, že ji lze celou pokrýt koulí o poloměru 1.
\end{prikl}
\begin{proof}[Řešení] % Asi není potřeba zvlášť hrotit první případ, ale pro přehlednost jsem to tam dal.
Buďte $A$, $B \in S$ body, které mají ze všech dvojic bodů z $S$ největší vzdálenost. Je-li $\|A - B\| \leq 1$, pak koule se středem v libovolném z bodů pokrývá celou množinu $S$, zejména pak každou její podmnožinu. V opačném případě pro trojice $A$, $B$, $X$, kde $X \in S$ je libovolný, platí, že $X$ leží v jednotkové kouli se středem v $A$ nebo $B$. $|S \setminus \{A, B\}| = 2n-1$ rozdělujeme do dvou přihrádek, každá má alespoň $n$ prvků, což nám spolu s $A$ nebo $B$ dá hledanou podmožinu $S$ o $n+1$ prvcích.
\end{proof}
%%%%%


\begin{prikl}%25 - IMO1972
Dokažte, že z libovolné množiny deseti dvojciferných čísel můžeme vybrat dvě neprázdné a disjunktní podmnožiny takové, že součty všech jejich prvků jsou si rovny.
\end{prikl}
\begin{proof}[Řešení]
Počet všech možných součtů až deseti dvojciferných čísel lze jistě shora ohraničit 990. Počet všech podmnožin desetiprvkové množiny je $2^{10} = 1024$. To znamená, že alespoň dvě podmnožiny $S_1$ a $S_2$ dávají stejný součet (zejména jsou neprázdné). Pokud $S_1 \cap S_2 = \emptyset$, jsme hotovi. V opačném případě uvážíme množiny $T_1 = S_1 \setminus S_2$ a $T_2 = S_2 \setminus S_1$, tj. odstraníme společné prvky. Nutně tedy $T_1 \cap T_2 = \emptyset$. Jistě součet prvků v $T_1$ bude i nadále roven součtu prvků v $T_2$ (z obou jsme odstranili stejné prvky). Protože $S_1$ a $S_1$ byly různé podmnožiny, je jistě $T_i \neq \emptyset$ pro nějaké $i \in \{1,2\}$. Součet je tedy nenulový, proto každá z množin $T_1$, $T_2$ je neprázdná. Protože disjunktnost jsme si zajistili výše, je důkaz hotov.
\end{proof}
%%%%%


\begin{prikl}%66 - Putnam 1980
\begin{enumerate}
\item Dokažte, že existují $a$, $b$, $c \in \Z$, $|a|, |b|, |c| < 10^6$, $|a| + |b| + |c| \neq 0$ taková, že
\[
|a + b\sqrt{2} + c\sqrt{3}| < 10^{-11}.
\]
\item Nechť $a$, $b$, $c \in \Z$, $|a|, |b|, |c| < 10^6$, $|a| + |b| + |c| \neq 0$. Dokažte, že
\[
|a + b\sqrt{2} + c\sqrt{3}| > 10^{-21}.
\]
\end{enumerate}
\end{prikl}
\begin{proof}[Řešení]
\begin{enumerate}
\item Uvažme množinu
\[
S = \{r + s\sqrt{2} + t\sqrt{3} \mid 0 \leq r,s,t \leq 10^6 - 1\}.
\]
Jistě $|S| = 10^{18}$. Položme dále
\[
d = (1 + \sqrt{2} + \sqrt{3}) \cdot 10^6.
\]
Pak pro $x \in S$ platí
\[
0 \leq x < d.
\]
Rozdělme inverval $[0,d)$ na $10^{18}-1$ stejně velkých polouzavřených intervalů $[(k-1)e, ke)$, kde 
\[
e = \frac{d}{10^{18}-1}, \qquad k \in \{1, \dots, 10^{18}-1\}.
\]
Z Dirichletova principu padnou alespoň dvě čísla z~množiny $S$ do stejného intervalu. Jejich rozdíl $a + b\sqrt{2} + c\sqrt{3}$ tak padne do intervalu $(0,e)$. Protože $e < 4,15 \cdot 10^{-12} < 10^{11}$, máme také, že
\[
0 < a + b\sqrt{2} + c\sqrt{3} < 10^{-11}.
\]
Zřejmě $0 \leq |a|,|b|,|c| < 10^{6}-1$, vždyť tyto koeficienty vznikly jako rozdíl přirozených čísel z~množiny $0,1, \dots, 10^{6}-1$.
\item Označme 
\[
F_1 = a + b\sqrt{2} + c\sqrt{3}
\]
a $F_2$, $F_3$, $F_4$ ostatní čísla tvaru $a \pm b\sqrt{2} \pm c\sqrt{3}$. Ukážeme, že $F_i$ jsou nenulová čísla. %(tj. $1,\sqrt{2},\sqrt{3}$ jsou $\Z$-nezávislá).
Pokud by 
\begin{align*}
r + s\sqrt{2} + t\sqrt{3} &= 0\\
r + s\sqrt{2} &= -t\sqrt{3}\\
r^2 + 2s^2 + 2rs\sqrt{2} &= tc^2
\end{align*}
Pravá strana je celé číslo, proto $r=0$ nebo $s = 0$. V obou případech dostáváme snadnou úvahou, že nutně $a=b=c=0$ (stačí se podívat na mocniny trojky na obou stranách). Protože koeficienty $a$, $b$, $c$ nejsou všechny nulové, nejsou nulové ani $F_i$. Uvažme dále
\begin{multline*}
F_1 F_2 F_3 F_4 = (a + b\sqrt{2} + c\sqrt{3}) (a - b\sqrt{2} - c\sqrt{3}) (a + b\sqrt{2} - c\sqrt{3}) (a - b\sqrt{2} + c\sqrt{3}) =\\
= [a^2 - (2b^2 + 3c^2 + 2bc\sqrt{6})]\cdot[a^2 - (2b^2 + 3c^2 -2bc\sqrt{6})] =\\
= [(a^2 - 2b^2 - 3c^2) - 2bc\sqrt{6}]\cdot[(a^2 - 2b^2 - 3c^2) + 2bc\sqrt{6}] = (a^2 - 2b^2-3c^2)^2 - 24b^2c^2 \in \Z.
\end{multline*}
Nutně tedy $|F_1 \cdot F_2 \cdot F_3 \cdot F_4| \geq 1$. Jistě tedy
\[
|F_1| \geq \frac{1}{|F_2 \cdot F_3 \cdot F_4|} > 10^{-21},
\]
neboť $|F_i| < 10^7$, což plyne z omezení na koeficienty $a$, $b$, $c$ a toho, že $1 + \sqrt{2} + \sqrt{3} < 10$.
\end{enumerate}
\end{proof}
\end{document}