\documentclass[11pt]{article}
\usepackage{a4wide}
\usepackage[utf8]{inputenc}
\usepackage[czech]{babel}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}


\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\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


\newtheorem{pr}{Příklad}


\renewcommand{\qedsymbol}{}		% zmena znaku na konci dukazu

\begin{document}
\section*{Soutěžní příklady}
\begin{pr}%[SNMÚ]
Uvažte dvě přirozená čísla $(15)_z$ a $(26)_z$ zapsaná v číselné soustavě o základu~$z$, kde $z \geq 7$ je přirozené číslo. Určete všechny hodnoty $z$, pro něž jsou čísla $(15)_z$ a $(26)_z$ nesoudělná.\hfill (2 body)
\end{pr}


\vfill


\begin{pr}%[MO - A51iii - 3]
Dokažte, že dané přirozené číslo $A$ je druhou mocninou některého přirozeného čísla, právě když pro každé přirozené $n$ je aspoň jeden z rozdílů
\begin{gather*}
(A+1)^2 - A,\\
(A+2)^2 - A,\\
(A+3)^2 - A,\\
\vdots\\
(A+n)^2 - A
\end{gather*}
dělitelný číslem $n$. \hfill (4 body)
\end{pr}


\vfill


\begin{pr}%[MO - A54ii - 4]
Najděte všechny dvojice přirozených čísel, jejichž součet má poslední cifru 3, rozdíl je prvočíslo a součin je druhou mocninou přirozeného čísla. \hfill (4 body)
\end{pr}


\vfill


\begin{pr}%[MO - A47i - 1]
\begin{enumerate}
\item Dokažte:
\[
\forall n \in \N\colon 2^{n+2} \mid 2013^{2^n} - 1 \quad\text{a zároveň}\quad 2^{n+3} \nmid 2013^{2^n} -1.
\]
\item Nalezněte všechna $k \in \Z$ splňující: 
\[
\forall n \in \N\colon 2^{n+2} \mid k^{2^n} - 1 \quad\text{a zároveň}\quad 2^{n+3} \nmid k^{2^n} -1.
\]
\end{enumerate}
\hfill (3 body)
\end{pr}


\vfill


%\begin{pr}%[SNMÚ]
%Dokažte: $\forall n \in \N \colon n \mid 3^n-2 \Rightarrow 3^n -1 \mid 3^{3^n-1}-3$.
%\end{pr}


\begin{pr}%[SNMÚ]
Najděte všechny pravoúhlé trojúhelníky s obvodem 180, jejichž délky stran jsou vyjádřeny přirozenými čísly. \hfill (2 body)
\end{pr}


\vfill


\begin{pr}
Dokažte, že číslo $5^n + 7^n + 13^n$ je složené pro každé přirozené číslo $n$. \hfill (2 body)
\end{pr}


\newpage
\section*{Řešení}
\begin{proof}[Řešení]
Přepíšeme zadaná čísla do desítkové soustavy a využijeme jeden krok Euklidova algoritmu
\[
2z + 6 = 2\cdot\ce{z+5} - 4.
\]
Největší společný dělitel čísel $2z+6$ a $z+5$ musí dělit také číslo $4$. Pokud společným dělitelem $2z+6$ a $z+5$ nebude dvojka, bude to už nutně jednička. Určitě $2 \mid 2z + 6$, nicméně $2 \mid z + 5$ pouze pro $z$ lichá. Hledané hodnoty $z$ jsou tedy všechna sudá čísla větší než 7.
\end{proof}

\vfill

\begin{proof}[Řešení]
Dokázat ekvivalenci znamená dokazovat dvě implikace.
\begin{itemize}
\item \uv{$\Rightarrow$}: Předpokládáme, že $A = a^2$, kde $a \in \N$. Buď $n$ libovolné, pak
\begin{gather*}
(A+1)^2 - A = \ce{a^2 + 1}^2 - a^2 = \ce{a^2+a+1}\ce{a^2-a+1},\\
(A+2)^2 - A = \ce{a^2 + 2}^2 - a^2 = \ce{a^2+a+2}\ce{a^2-a+2},\\
\vdots\\
(A+n)^2 - A = \ce{a^2 + n}^2 - a^2 = \ce{a^2+a+n}\ce{a^2-a+n}.
\end{gather*}
Jistě $n$ dělí alespoň jedno z těchto čísel (první závorky v rozkladu na součin tvoří posloupnost $n$ po sobě jdoucích přirozených čísel).
\item \uv{$\Leftarrow$}: Důkaz povedeme sporem, tj. předpokládáme, že libovolné $n \in \N$ dělí alespoň jeden ze zadaných rozdílů a $A$ není druhou mocninou přirozeného čísla. Pak nutně existuje prvočíslo $p$, které se nachází v rozkladu čísla $A$ na prvočísla v liché mocnině, tj. $p^{2k-1} \mid A$, ale $p^{2k} \nmid A$. Protože $n$ je libovolné přirozené, zvolme $n = p^{2k}$. Předpokládáme dále, že $p^{2k}$ dělí některý z rozdílů, tj. $p^{2k} \mid \ce{A+j}^2 - A$ pro nějaké $j$. Jistě
\[
p^{2k} \mid \ce{A+j}^2 - A \qquad \Rightarrow \qquad p^{2k-1} \mid \ce{A+j}^2 - A.
\]
Volbou $n$ máme, že $p^{2k-1} \mid A$, proto
\[
p^{2k-1} \mid \ce{A+j}^2 \qquad \Rightarrow \qquad p^{2k} \mid \ce{A+j}^2,
\]
vždyť $\ce{A+j}^2$ je druhá mocnina přirozeného čísla. Celkem
\[
p^{2k} \mid \ce{A+j}^2 - A \qquad \Rightarrow \qquad p^{2k} \mid A,
\]
což je spor.
\end{itemize}
Tím je důkaz hotov.
\end{proof}


%%%%%%%%%%%%%%%%%%%%
\newpage
\begin{proof}[Řešení]
Označme hledaná přirozená čísla $x$, $y$.
\begin{itemize}
\item Položme $d = (x,y)$, tj. $x = ad$, $y = bd$. Můžeme psát $x-y = d\ce{a-b} = p$. Je-li $d>1$, pak $p = d$ a $a-b = 1$, tj. $x = d(k+1)$, $y = dk$ pro nějaké $k \in \N$. Pak ale $xy = d^2k(k+1)$. To není druhá mocnina přirozeného čísla, což je spor. Proto $d = 1$ a můžeme psát $x = u^2$, $y = v^2$.
\item Víme, že poslední cifra součtu $x+y = u^2 + v^2$ má být 3. Uvažme čísla tvaru $n = 10k+j$, kde $j = 0,1,\dots, 9$ a podívejme se na poslední cifry $n^2$. Dostáváme
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
j & 0&1&2&3&4&5&6&7&8&9\\\hline
\text{zbytek}&0&1&4&9&6&5&6&9&4&1\\\hline
\end{array}
\]
Víme, že $u^2 - v^2 = \ce{u+v}\ce{u-v} = p$, proto $u+v = p$, $u-v = 1$, tedy $u = v+1$. Proto se můžeme zabývat pouze dvěma po sobě jdoucími druhými mocninami. Dostáváme dva typy řešení
\[
u_1 = 10k + 3, \quad v_1 = 10k + 2\qquad \text{a} \qquad u_2 = 10l+8, \quad v_2 = 10l+7
\]
pro vhodná $k,l \in \N_0$.
\item Uvažme $u_1^2 - v_1^2 = \ce{u_1 + v_1}\ce{u_2-v_2} = 20k + 5 = p$, odtud nutně $k = 0$. Snadno ověříme, že $x = 3^2$, $y = 2^2$ je řešení.
\item V druhém případě $u_2^2 - v_2^2 = \ce{u_2+v_2}\ce{u_2 - v_2} = 20l+15 = p$ nedostáváme žádné řešení.
\end{itemize}
Řešením je jediná dvojice čísel, a to 9 a 4.
\end{proof}


\vfill


\begin{proof}[Řešení]
Rozepíšeme číslo $2013^{2^n} - 1$ pomocí vzorce $a^2 - b^2 = \ce{a+b}\ce{a-b}$
\begin{multline*}
2013^{2^n}-1 =\\
 = \ce{2013^{2^{n-1}} + 1}\ce{2013^{2^{n-1}}-1} = \ce{2013^{2^{n-1}} + 1}\ce{2013^{2^{n-2}} + 1}\ce{2013^{2^{n-2}} - 1} = \dots\\
\dots = \ce{2013^{2^{n-1}} + 1}\ce{2013^{2^{n-2}} + 1}\dots\ce{2013^{2^{0}} + 1}\ce{2013^{2^{0}} - 1} = \\
= 2012\prod_{i = 0}^{n-1} \ce{2013^{2^{i}} + 1}.
\end{multline*}
Protože $4 \mid 2012$, ale $8 \nmid 2012$, stačí nám pro důkaz první části ukázat, že $2 \mid 2013^{2^i} + 1$, ale $4\nmid 2013^{2^i} +1$. Sudost je splněna triviálně. Protože 2013 = 2012+1, plyne nedělitelnost čtyřkou z binomické věty.\\
Stejnými úpravami jako výše můžeme dostat totožný tvar i pro obecné $k$
\[
k^{2^n} - 1 = \ce{k-1} \prod_{i = 0}^{n-1} \ce{k^{2^i} + 1}.
\]
Jednoduchou úvahou dospějeme k řešení, že $k = 8l \pm 3$  pro libovolné~$l \in \Z$.
\end{proof}



%%%%%%%%%%%%%%%%%%%%
\newpage
\begin{proof}[Řešení]
Označme jednotlivé délky stran jako $a,b$ a $c$, kde $a^2 + b^2 = c^2$. Navíc $a+b+c = 180$, můžeme tedy dosadit za $c$ a upravovat
\begin{align*}
a^2 + b^2 &= \ce{180 - a-b}^2,\\
a^2 + b^2 &= a^2 + b^2 + 180^2 - 2\cdot 180 a - 2 \cdot 180 b + 2ab,\\
ab - 180a - 180b + 180^2 &= 90\cdot 180,\\
\ce{180-a}\ce{180-b} &= 90 \cdot 180.
\end{align*}
Protože $a,b$ jsou délky odvěsen, platí $180 -a > 90$, $180 -b > 90$. Rozkládáme proto číslo $90 \cdot 180 = 2^3\cdot 3^4 \cdot 5^2$ na součin dvou přirozených čísel větších než 90.
\[
2^3\cdot 3^4 \cdot 5^2 = 120 \cdot 135 = 108 \cdot 150 = 100 \cdot 162
\]
Dostáváme tři řešení $\ce{30,72,78}$, $\ce{45,60,75}$ a $\ce{18,80,82}$.
\end{proof}


\vfill


\begin{proof}[Řešení]
Vypišme si nejprve několik prvních členů
\[
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
n 			&	1	&	2	&	3	&	4	&	5	&	6	&	7	\\\hline
5^n+7^n+13^n 	&	25	&	143	&	2\,665&31\,587	&391\,225	&4\,960\,083&63\,650\,185\\\hline
\end{array}
\]
Snadno rozmyslíme, že pro $n$ lichá jsou příslušná čísla vždy dělitelná pěti. O něco méně triviální je všimnout si, že pro $n$ sudá jsou všechna čísla dělitelná třemi. Nyní dokážeme, že toto skutečně platí pro všechna $n \in \N$, využijeme u toho binomické věty.
\begin{itemize}
\item Je-li $n$ liché, pak
\[
5 \mid 5^n + 7^n + 13^n = 5^n + \ce{5+2}^n + \ce{15-2}^n \quad \Leftrightarrow \quad 5 \mid 2^n + \ce{-2}^n = 0.
\]
Tedy skutečně pro všechna $n$ lichá naše hypotéza platí.
\item Je-li $n$ sudé, pak
\[
3 \mid 5^n + 7^n + 13^n = \ce{6-1}^n + \ce{6+1}^n + \ce{12+1}^n \quad \Leftrightarrow \quad 3 \mid \ce{-1}^n + 1^n + 1^n = 3.
\]
Dokázali jsme tvrzení i pro $n$ sudá.
\end{itemize}
Protože každý člen posloupnosti je jistě větší než $5$ a je dělitelný buď $3$ nebo $5$, musí být nutně složeným číslem. Tím je tvrzení dokázáno.
\end{proof}
\end{document}