\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}
\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{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{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{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{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{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{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{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{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{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}
\end{document}