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


\begin{document}
%\setcounter{chapter}{6}
\chapter{Extremální princip}
%\section*{Teorie}
Při řešení matematických úloh je dobré mít více způsobů, jak na danou věc nahlížet, znát co nejvíce různých metod řešení. Nyní se budeme pokoušet o důkaz existence (či neexistence) řešení s určitými vlastnostmi. Extremální princip nám říká, abychom vybrali objekt, který maximalizuje či minimalizuje určitou funkci. Je-li takových objektů více, je často nedůležité, který z nich vybereme. Extremální princip je navíc často konstruktivní, takže dostáváme nejen důkaz existence zadaného objektu, ale i způsob, jak ho zkonstruovat. Při dokazování neexistence řešení můžeme postupovat tak, že sporem předpokládáme existenci řešení a uvážíme z nich to nejmenší (zvlášť, pokud řešením jsou například přirozená čísla). S jeho pomocí poté zkonstruujeme řešení ještě menší.

\section*{Návodné příklady}
\begin{pr}%E3
V~rovině je dáno $n$~bodů takových, že každé tři tvoří trojúhelník o~obsahu menším nebo rovném jedné. Dokažte, že všech $n$~bodů leží v~trojúhelníku o~obsahu menším nebo rovném čtyřem.
\end{pr}
\begin{proof}[Řešení]
Mezi všemi ${n \choose 3}$ trojicemi bodů zvolme trojici $A,B,C$ takovou, že $\triangle ABC$ má největší obsah, označme si ho~$S$. Zřejmě $F\leq 1$. Každým vrcholem $\triangle ABC$ veďme rovnoběžku s~protější stranou. Dostaneme $\triangle A'B'C'$, v~němž původní $\triangle ABC$ tvoří střední příčky. Proto jeho obsah $S'=4S\leq 4$. Nyní ukážeme, že všech $n$~bodů leží v~$\triangle A'B'C'$.

Sporem uvažme bod~$P$ ležící vně $\triangle A'B'C'$. Pak $\triangle ABC$ a~bod~$P$ leží v~opačných polorovinách určených jednou ze~přímek $A'B'$, $A'C'$, $B'C'$. BÚNO nechť je to $B'C'$. Pak je ale obsah $\triangle BCP$ větší, než obsah  $\triangle ABC$ (společná základna $BC$, ale výška z~$A$ je zřejmě menší než~z~$P$). Což je ale spor s~maximalitou obsahu zvoleného $\triangle ABC$.
\end{proof}


\begin{pr}%E8
Mějme v~rovině dánu klasickou mřížovou strukturu (rovnoběžné a~kolmé) a~v~každém mřížovém bodě přirozené číslo, přičemž každé z~těchto čísel je aritmetickým průměrem svých čtyř sousedů (nahoře, dole, vpravo, vlevo). Dokažte, že všechna čísla jsou si rovna.
\end{pr}
\begin{proof}[Řešení]
Uvažme~$m$ nejmenší z~čísel v~mřížových bodech, a~jeho sousedy~$a,b,c,d$. Pak $m=\frac{a+b+c+d}4$, neboli
\begin{equation}
a+b+c+d=4m.\label{extr:E8}
\end{equation}
Z~minimality $m$ máme $a\leq m, b\leq m, c\leq m, d\leq m$. Pokud však bude některá z~těchto nerovností ostrá, dostaneme z~nich nerovnost $a+b+c+d>4m$, což je ve sporu s~\eqref{extr:E8}. Proto $a=b=c=d=m$.

Rozšíříme-li tuto úvahu na~sousedy $a,b,c,d$, poté na~sousedy sousedů,\;\dots, dostaneme, že jsou všechna čísla v~mřížových bodech rovna~$m$.
\end{proof}


\begin{pr}%E9
V~oboru celých čísel řešte rovnici $$x^2+y^2=3\zk{z^2+u^2}.$$
\end{pr}
\begin{proof}[Řešení]
Čtveřice $(x,y,z,u)=(0,0,0,0)$ je zřejmě řešením. Ukažme, že jiné než nulové řešení tato rovnice nemá.

Nechť $(a,b,c,d)$ je nenulové řešení takové, pro~které je $x^2+y^2=a^2+b^2$ nejmenší. Pak $$a^2+b^2=3\zk{c^2+d^2} \;\imp\; 3\mid a^2+b^2 \;\imp\; 3\mid a \wedge 3\mid b \;\imp\; a=3a_1, b=3b_1, a,b\in\Z.$$ Dosazením $$a^2+b^2=9\zk{a_1^2+b_1^2}=3\zk{c^2+d^2} \;\imp\; c^2+d^2 = 3\zk{a_1^2+b_1^2}.$$
Našli jsme tak nové řešení $(c,d,a_1,b_1$, pro které platí $c^2+d^2 < a^2+b^2$, což je spor s~minimalitou volby $(a,b,c,d)$.
\end{proof}


\begin{pr}%13
Po~turnaji, na~kterém hrál každý s~každým a žádný zápas neskončil remízou, si každý hráč udělal seznam, na kterém byli všichni ti, které porazil, a~které porazili ti, které porazil. Dokažte, že nějaký hráč má na~svém seznamu všechny ostatní hráče.
\end{pr}
\begin{proof}[Řešení]
Uvažme hráče $A$, který má nejvíc výher, a~ukažme, že on má na svém seznamu všechny ostatní. Kdyby tomu tak nebylo, pak by existoval hráč $B$, který porazil hráče~$A$ i~všechny hráče, které porazil hráč~$A$. To by ale znamenalo, že hráč~$B$ má více výher než hráč~$A$, což je spor s~volbou~$A$.
\end{proof}


\section*{Příklady}
\begin{prikl}%E9
Mějme v~rovině $2n$ po~třech nekolineárních bodů. Právě~$n$ z~nich jsou farmy $F=\zm{F_1,F_2,\dots,F_n}$ a~zbylých~$n$ jsou studny $W=\zm{W_1,W_2,\dots,W_n}$. Ukažte, že můžeme každou farmu spojit cestou s~právě jednou studnou tak, že cesty jsou úsečky, všechny studny budou využívány, a~žádně dvě cesty se neprotnou.
\end{prikl}
\begin{proof}[Řešení]
Nejprve zapomeňme na požadavek neprotnutí. Takový systém cest je zřejmě bijekcí mezi farmami a~studnami. Ze~všech $n!$ těchto systémů, vyberme ten s~nejmenší celkovou délkou cest, a~ukažme, že v~něm se cesty neprotínají.

Předpokládejme sporem, že tam existují cesty $F_iW_k$ a $F_jW_l$, které se protínají. Pak bychom ale jejich nahrazení za~$F_iW_l$ a~$F_jW_k$ dostali systém, který by měl díky trojúhelníkové nerovnosti menší celkovou délku, což je spor.
\end{proof}


\begin{prikl}%24
Mějme v~rovině $2n+3$ po~třech nekolineárních bodů, přičemž žádné čtyři neleží na~jedné kružnici. Dokažte, že můžeme zvolit tři body takové, že v~kružnici jim opsané leží právě~$n$ ze~zbylých bodů, a~právě $n$ leží vně této kružnice.
\end{prikl}
\begin{proof}[Řešení]
Uvažme libovolné dva body $A,B$ takové, že všechny zbylé body leží v~jedné polorovině určené přímkou~$AB$. Zbylých $2n+1$ bodů $X_1,X_2,\dots,X_{2n+1}$ seřaďme tak, že $\pp{\measuredangle AX_iB}<\pp{\measuredangle AX_{i+1}B}$ pro všechna $i=1,\dots,2n$. Hledaným třetím bodem je pak bod~$X_{n+1}$, neboť body $X_1,\dots,X_n$ leží uvnitř kružnice opsané bodům $A,B,X_{n+1}$, zatímco body $X_{n+2},\dots,X_{2n+1}$ leží vně. Toto, jakož i~možnost předtím uspořádat body do~posloupnosti, plyne z~vlastností ekvigonály (množina bodů v~rovině, ze kterých je vidět úsečku pod~daným úhlem), a~že žádné čtyři body neleží ze~zadání na~jedné kružnici.
\end{proof}


\begin{prikl}%27
Ukažte, že libovolných 15 po~dvou nesoudělných přirozených čísel $n_1,\dots,n_{15}$, $1<n_1,\dots,n_{15} \leq 2015$, musí mít mezi sebou prvočíslo. 
\end{prikl}
\begin{proof}[Řešení]
Předpokládejme, že máme takových 15 čísel, které mezi sebou prvočíslo nemají.
Označme $p_i$ nejmenší prvočíslo dělící $n_i$ pro~každé $i=1,\dots,15$, a~$p$ největší z~nich. Protože čísla $n_1,\dots,n_{15}$ jsou po~dvou nesoudělná, jsou prvočísla $p_1,\dots,p_{15}$ po~dvou různá. Proto $p\geq 47$ (47 je 15té prvočíslo). Je-li $p=p_k$, pak $n_k \geq p^2 \geq 47^2 = 2209 > 2015$, což je spor.
\end{proof}


\begin{prikl}%40
Je dáno několik kladných reálných čísel, po~dvou různých. Součet všech jejich součinů po~dvou je roven jedné. Dokažtě, že lze jedno z~těchto čísel vynechat tak, že součet zbylých je menší než~$\sqrt2$.
\end{prikl}
\begin{proof}[Řešení]
Nechť $x_1$ je největší z~čísel $x_1,x_2,\dots,x_n$. Ze~zadání
\begin{equation}
\sum\limits_{1\leq i < j \leq n} x_ix_j =1.\label{extr:40:1}
\end{equation}
Vynechme číslo~$x_1$ a~počítejme
\begin{equation}
\zk{x_2+\dots+x_n}^2=\sum\limits_{i=2}^n x_i^2 + \sum\limits_{2\leq i < j \leq n} 2x_ix_j.\label{extr:40:2}
\end{equation}
Z~maximality $x_1$ plyne $x_i^2 < 2x_1x_i$ pro~$i=2,\dots,n$, odkud $$\sum\limits_{i=2}^n x_i^2 < \sum\limits_{i=2}^n 2x_1 x_i.$$
Dosaďme tuto nerovnost do~\eqref{extr:40:1}.
$$\zk{x_2+\dots+x_n}^2 < \sum\limits_{i=2}^n 2x_1 x_i + \sum\limits_{2\leq i < j \leq n} 2x_ix_j = 2 \sum\limits_{1\leq i < j \leq n} x_ix_j \stackrel{\eqref{extr:40:2}}{=} 2$$
Protože jsou čísla $x_2,\dots,x_n$ nezáporná, můžeme korektně odmocnit, čímž dostaneme požadovanou nerovnost $x_2+\dots+x_n <\sqrt2$.
\end{proof}


\begin{prikl}%42
Jsou dány dvě permutace $a_1,\dots,a_n$ a $b_1,\dots,b_n$ čísel $1,\frac12,\dots,\frac1n$. Dále platí nerovnosti $a_1+b_1 \geq a_2+b_2 \geq \dots \geq a_n+b_n$. Dokažte, že pro~každé $m=1,\dots,n$ platí $a_m+b_m \leq \frac4m$. 
\end{prikl}
\begin{proof}[Řešení]
Pro~každé $m=1,\dots,n$ uvažme $m$~dvojic $(a_k,b_k)$, $k=1,\dots,m$. Pak z~těchto $m$~dvojic splňuje jednu z~nerovností $a_k \geq b_k$ a~$b_k \geq a_k$ alespoň $\frac{m}2$ z~nich.

Nechť $b_k \geq a_k$ splňuje alespoň $\frac{m}2$ z~nich. Je-li $b_i$ nejmenší z~těchto~$b_k$, pak $b_i \leq \frac 2m$, vždyť $b_i$ je nejmenší z~alespoň $\frac{m}{2}$ členů posloupnosti, kde prvních $\frac{m}{2}$ největších je uspořádáno $1>\frac{1}{2} > \frac{1}{3} > \frac{1}{\frac{m}{2}} = \frac{2}{m}$. Potom $a_i+b_i \leq 2b_i \leq \frac4m$, a~z~$i\leq m$, $a_m+b_m\leq a_i+b_i \leq \frac4m$.

V~opačném případě analogicky s~minimálním~$a_k$.
\end{proof}


\begin{prikl}
Řešte v~$\N$ rovnici
\[
x^4 + y^4 = z^2.
\]
\end{prikl}
\begin{proof}[Řešení]
Budeme chtít dokázat, že žádné řešení neexistuje. Předpokládejme sporem, že máme řešení $x,y,z$, kde hodnota~$z$ je nejmenší mezi všemi řešeními. Pak nutně $(x,y,z) = 1$, a~tedy právě jedno z~čísel~$x,y,z$ je sudé. Při~pohledu na~rovnici modulo~4 vidíme, že to nemůže být~$z$. Ze~symetrie rovnice vzhledem k~$x$ a~$y$ můžeme předpokládat, že $2 \mid x$. Upravíme rovnici do~tvaru
\[
\big(x^2 \big)^2 + \big(y^2\big)^2 = z^2.
\]
Dostáváme, že trojice $x^2, y^2, z$ je řešením Pythagorovy rovnice, je tedy tvaru
\begin{align*}
x^2 &= 2ab,\\
y^2 &= a^2 - b^2,\\
z &= a^2 + b^2.
\end{align*}
Druhá rovnice je opět Pythagorejská
\[
a^2 = b^2 + y^2,
\]
kde $(a,b) = 1$. Protože $ 2 \nmid y$, můžeme opět určit tvar řešení této rovnice jako
\begin{align*}
a &= r^2 + s^2,\\
b &= 2rs,\\
c &= r^2 - s^2,
\end{align*}
kde $(r,s) = 1$. Dosadíme
\begin{align*}
x^2 &= 2ab = 4rs(r^2 + s^2),\\
\ce{\frac{x}{2}}^2 &= rs(r^2 + s^2).
\end{align*}
Protože $(r,s) = 1$, tak také $(r, s^2) = (r, r^2 + s^2) = 1$ a~podobně $(s, r^2 + s^2) = 1$. Tedy čísla $r, s, r^2  + s^2$ jsou po~dvou nesoudělná. Protože se však součin těchto čísel rovná druhé mocnině přirozeného čísla, musí být každé z~těchto čísel druhou mocninou. Tedy existují $u,v,w$ takové, že
\begin{align*}
r &= u^2,\\
s & = v^2,\\
r^2+s^2 &= w^2.
\end{align*}
Dosazením za $r$ a $s$ do poslední rovnice dostáváme
\[
u^4 + v^4 = w^2,
\]
kde
\[
w < w^2 = r^2 + s^2 = a < a^2 + b^2 = z.
\]
Dostáváme spor s~minimalitou~$z$. Úloha tedy nemá řešení.
\end{proof}

\begin{prikl}
Dva hráči hrají následující hru. Na začátku je na stole několik hromádek žetonů. Hráč, který je na řadě, každou z hromádek, která obsahuje více než 1 žeton, rozdělí na dvě (neprázdné) hromádky. Ten, kdo udělá poslední tah, vyhrává. Určete počáteční podmínky (tj. podmínky nutné a dostatečné), za kterých první hráč vítězí a nalezněte jeho vítěznou strategii.
\end{prikl}
\begin{proof}[Řešení]
Pro malá čísla můžeme udělat jednoduchá pozorování. Předpokládejme, že začínáme s jedinou hromádkou, $\Rightarrow$ znamená tah prvního hráče.
\[
\xymatrix{
3 \ar@{=>}[d]\\
21 \ar[d]\\
111
}\qquad
\xymatrix{
&4 \ar@{=>}[dl] \ar@{=>}[dr]&\\
31 \ar[d] && 22\ar[d]\\
211 \ar@{=>}[d] &&1111\\
1111
}\qquad
\xymatrix{
&5 \ar@{=>}[dl] \ar@{=>}[dr]&\\
41 \ar[d] \ar[dr] && 32 \ar[d]\\
311 \ar@{=>}[d] & 221\ar@{=>}[d] & 2111 \ar@{=>}[d]\\
2111 \ar[d] & 11111 & 11111\\
11111 &&
}
\]
Označme $K$ velikost počáteční hromádky. Vidíme tedy, že v případě $K = 3$ vyhrává druhý hráč, pro $K = 4$ první (stačí zvolit levou cestu), pro $K = 5$ opět první (stačí zvolit pravou cestu). Pro vyšší čísla můžeme využívat znalosti, jak hra dopadne, když se dostaneme do nějakého z dříve spočítaných stavů (přitom vždy můžeme zcela ignorovat hromádky velikosti 1 a 2, nachází-li se zde nějaká větší). Proto místo příslušných podstromů dáme jen list s hodnotou $V$, pokud zde první hráč vyhraje, nebo $P$, pokud by cesta sem znamenala jeho prohru (dolní index značí rozdělení hromádek).
\[
\xymatrix{
& 6 \ar@{=>}[ld] \ar@{=>}[d] \ar@{=>}[rd] & \\
P_{51} & P_{42} & 33 \ar[d]\\
&& 2211 \ar@{=>}[d]\\
&& 111111
}
\xymatrix{
& 7 \ar@{=>}[ld] \ar@{=>}[d] \ar@{=>}[rd] &\\
P_{61} & P_{52} & 43 \ar[ld] \ar[d]\\
& P_{3211} & 2221 \ar@{=>}[d]\\
&& 1111111
}
\xymatrix{
& 8 \ar@{=>}[dl] \ar@{=>}[d] \ar@{=>}[dr] \ar@{=>}[drr] &&\\
V_{71} & P_{62} &  P_{53} & 44 \ar[lld] \ar[ld] \ar[d]\\
& 3311 \ar@{=>}[d] & P_{3221} & P_{2222}\\
& P_{22111111} &&
}
\]
Snadno rozmyslíme, že pro 9 je rozdělení $72$ vítězné, pro 10 to bude $73$, pro 11 to bude 74. Všimněme si, že v případě $K = 8$ máme jedinou možnost v prvním kroku (a to jít na 71). Druhý hráč může dělat co chce, ale když pak zredukujeme největší hromádku na velikost 3, vyhráváme. V případě $K = 6,5,4$, vždycky musíme udělat první dělení tak, aby největší hromádka měla právě 3 žetony. Ukážeme, že toto chování není náhoda.\\
Nyní zrušíme omezení, že začínáme s jedinou hromádkou a označme $M$ velikost největší hromádky. Chceme ukázat, že pokud po našem kroku bude $M \in \{1,3,7, \dots \}$ tj. $M = 2^r - 1$ pro nějaké $r \in \N$, můžeme pokračovat tak, abychom vyhráli. Důkaz povedeme jednoduchou indukcí.\\
Pro $M = 1$ je tvrzení zřejmé (vždyť soupeř nemůže hrát, takže náš tah byl poslední).\\
Je-li po našem kroku $M = 2^{r+1} - 1$, pak po kroku soupeře bude $2^r \leq M \leq 2^{r+1}-2$. Opět tedy můžeme rozdělit hromádky tak, aby $M = 2^{r} - 1$, což dle indukčního předpokladu vede k výhře.
První hráč tedy vyhrává právě tehdy, když na začátku platí $M \neq 2^{r} - 1$, $r \in \N$, vítězná strategie je rozdělovat hromádky tak, aby $M = 2^s - 1$.
\end{proof}

\begin{prikl}
Uvažujme cestu v rovině s následujícími pravidly. Z bodu o souřadnicích $(x,y)$ se vždy můžeme pohnout do jednoho z bodů: $(x,y+2x)$, $(x,y-2x)$, $(x-2y,y)$, $(x+2y,y)$ s tím omezením, že po kroku jedním směrem se hned nesmíme vrátit zpět. Dokažte, že pokud začneme v bodě $(1, \sqrt{2})$, nikdy se do tohoto bodu nemůžeme vrátit.
\end{prikl}
\begin{proof}[Řešení]
Uvažme situaci, kdy jsme v nějakém bodě $(x,y)$ a podívejme se, jak se můžeme přiblížit k~počátku $O = (0,0)$. Druhé mocniny vzdáleností po nějakém kroku jsou
\[
x^2 \pm 4xy + 5y^2, \qquad 5x^2 \pm 4xy + y^2.
\]
Porovnání s původní vzdálenosti znamená porovnat tato čísla s $x^2 + y^2$. Zajímají nás tedy znaménka
\[
4y (y \pm x), \quad 4x(x \pm y)
\]
respektive jen
\[
y^2 \pm xy, \quad x^2 \pm xy
\]
Předpokládejme, že se nenacházíme na žádé z přímek $x = 0$, $y = 0$, $x = y$ nebo $x = -y$, pak se vzdálenost od počátku libovolným krokem vždy změní. Předpokládejme, že $|x| > |y|$, pak $x^2 \pm xy > 0$ a právě jedno z čísel $y^2 \pm xy$ je záporné. Symetricky pro $|y| > |x|$. Mimo výše uvedené přímky se tedy k~počátku můžeme přiblížit právě jedním krokem a ostatními se dostaneme dál. Protože na začátku je poměr souřadnic iracionální číslo, bude to tak po celou dobu cesty, vždyť
\begin{gather*}
\frac{x}{y} \in \mathbb{I} \quad\Rightarrow\quad \frac{x \pm 2y}{y} = \frac{x}{y} \pm 2 \in \mathbb{I},\\
\frac{x}{y} \in \mathbb{I} \quad\Rightarrow\quad \frac{y}{x} \in \mathbb{I} \quad\Rightarrow\quad \frac{y \pm 2x}{x} = \frac{y}{x} \pm 2 \in \mathbb{I}.
\end{gather*}
Pak se ale na žádné z přímek $x = 0$, $y = 0$, $x = y$ nebo $x = -y$ nemůžeme v průběhu cesty nacházet a vždy tedy platí, že právě jeden krok vede blíže počátku. Předpokládejme nyní, že $P_0 P_1 \dots P_n = P_0$ jsou jednotlivé kroky na cestě. Buď $P_i$ nejvzdálenější bod od počátku na této cestě. Protože vzdálenost $P_{i-1}$ od počátku je menší než vzdálenost $P_i$ a z bodu $P_i$ vede jediná cesta blíže počátku, je $P_{i+1} = P_{i-1}$. To ale znamená, že libovolná cesta, která by vedla zpět do původního bodu, se musela po nějakém kroku hned vracet zpět.
\end{proof}
\end{document}