Příklad 1. Pro všechna přirozená $n$ dokažte rovnost $$\displaystyle\sum_{i=1}^ni^3=\left(\displaystyle\sum_{i=1}^ni\right)^2.$$
K řešení použijeme matematickou indukci.
Pro $i=1$ dostáváme $1=1$, což platí. Nyní mějme tvrzení dokázáno pro všechna $n \leq m$ a ukažme, že platí i pro $n=m+1$. Z rovnosti v zadání pro $n=m+1$ dostáváme: $$\begin{equation*} \begin{split} \displaystyle\sum_{i=1}^{m+1}i^3&=\left(\displaystyle\sum_{i=1}^{m+1}i\right)^2\\ \left(\displaystyle\sum_{i=1}^{m}i^3\right) + (m+1)^3&=\left(\displaystyle\sum_{i=1}^{m}i + m + 1\right)^2\\ \left(\displaystyle\sum_{i=1}^{m}i^3\right) + (m+1)^3&=\left(\displaystyle\sum_{i=1}^{m}i\right)^2 + 2(m+1)\left(\displaystyle\sum_{i=1}^{m}i\right) + (m + 1)^2\\ \end{split} \end{equation*} $$ Nyní můžeme využít indukčního předpokladu – víme, že nejlevější sčítance na obou stranách rovnice jsou si rovny, můžeme je tedy oba odečíst. $$\begin{equation*} \begin{split} (m+1)^3&=2(m+1)\left(\displaystyle\sum_{i=1}^{m}i\right) + (m + 1)^2\\ (m+1)^2&=2\left(\displaystyle\sum_{i=1}^{m}i \right) + (m + 1)\\ (m+1)^2-(m+1)&=2\displaystyle\sum_{i=1}^{m}i\\ (m+1)((m+1)-1)&=2\displaystyle\sum_{i=1}^{m}i\\ \frac{(m+1)m}2&=\displaystyle\sum_{i=1}^{m}i\\ \end{split} \end{equation*} $$ Rovnost, ke které jsme se dostali, platí například proto, že když v součtu na pravé straně spárujeme první a poslední sčítanec, poté druhý a předposlední a tak dále, dostaneme právě $\frac m2$ sčítanců, které budou mít hodnotu $m+1$. Kdybychom však na myšlenku s párováním nepřišli, mohli bychom tento vzorec znovu zkoušet dokazovat indukcí. Na závěr je dobré podotknout, že v našem důkazu by se mohlo zdát, že jsme tvrzení nedokázali – začali jsem s dokazovaným tvrzením, a nakonec jsme se dobrali pravdivého tvrzení. V důkazech je však nutné používat opačný postup – začít s pravdivým tvrzením a dobrat se dokazovaného tvrzení. Můžeme si ale všimnout, že všechny použité úpravy lze provést i opačným směrem a budou stále korektní.Příklad 2. Mějme nenulové reálné číslo $x$. Dokažte, že pokud $x+\frac1x$ je celé číslo, pak $x^n+\frac1{x^n}$ je celé číslo pro každé přirozené číslo $n$.
Příklad 3. Dokažte, že pro každé přirozené číslo $n$ je $n^5-n$ dělitelné pěti (nula je dělitelná všemi přirozenými čísly).
Příklad 4. (hvězdičkový) Bylo jedno mafiánské městečko a tam žila veliká spousta mafiánů. Mafiáni měli manželky a bohužel ne všechny manželky byly svým manželům věrné. Žádný z mafiánů však o své manželce neví, zda je mu věrná či ne. Na druhou stranu ví všechno ostatní, tedy i o ostatních mafiánech a věrnosti jejich manželek.
Jednoho dne byla oslava, kde se jeden svobodný mafián opil a přede všemi prohlásil: "V tomhle městě je alespoň jedna nevěrná manželka". Uběhlo 42 dní a všechny nevěrné manželky byly najednou v poledne oběšeny na náměstí. Kolik jich bylo a jak k tomu přesně došlo? Mafián nemá jinou možnost jak zjistit, zda je jeho manželka nevěrná, než pomocí vlastního logického uvažování – nikdo mu to nemůže říct. Uvažování mafiánů funguje po dnech. Pokud kterýkoliv mafián zjistí, že jeho manželka je nevěrná, následujícího dne ji na náměstí veřejně popraví (tedy všichni mafiáni se o tom dozvědí). Na druhou stranu nikdy nepopraví manželku, pokud si není absolutně jistý, že je mu nevěrná. Všichni mafiáni uvažují naprosto identicky a vědí to o sobě.Příklad 5. V rovině je nakresleno $n\in\mathbb{N}_0$ přímek tak, že žádné dvě nejsou rovnoběžné a žádné tři se neprotínají v jednom bodě. Dokažte, že je jimi rovina rozdělena právě na $\frac{n(n+1)}2+1$ částí.
Úlohu budeme řešit indukcí.
0 přímek dělí rovinu na 1 část, přípand $n=1$ tedy funguje. Mějme nyní rovinu rozdělenou podle indukčního předpokladu na $n(n+1)/2 +1$ částí $n$ přímkami a přidejme přímku $n+1$. Tato přímka protíná zbývajících $n$ přímek, prochází tedy $n+1$ částmi (v jedná začíná a po každém průsečíku přejde do jiné), každou z nich rozdělí na dvě a tedy vytvoří $n+1$ nových částí. Nyní už stačí dobrat se úpravami k rovnosti: $$\frac{n(n+1)}2 + 1 + (n+1) = \frac{n^2 + n + 2n + 2}2 + 1 = \frac{n^2 + 3n +2}2 +1 = \frac{(n+1)(n+2)}2 + 1,$$ čímž je úloha vyřešena.Příklad 6. (hvězdičkový) V prostoru je $n$ rovin tak, že žádné čtyři neprochází tímž bodem, ale libovolné tři mají právě jeden společný bod. Na kolik částí prostor dělí?
Příklad 7. Dokažte, že každý konvexní $3n$-úhelník lze rozdělit neprotínajícími se úhlopříčkami na trojúhelníky tak, že v každém vrcholu končí sudý počet těchto úhlopříček.
Úlohu budeme řešit indukcí. Pro $n=1$ máme trojúhelník, který rozdělený úhlopříčkami podle pravidel již je.
Nyní předpokládejme, že umíme rozdelit $3n$-úhelník a pojďme zkusit rozdělit $3n+3$-úhelník. Vzhledem k tomu, že $3n+3$ je alespoň 6, můžu si vzít 5 vedle sebe jsoucích vrcholů, a označit si je $A$, $B$, $C$, $D$ a $E$. $3n-3$-úhelník si označíme $U$. Dle indukčního předpokladu umíme rozdělit $3n-3$-úhelník, který dostaneme z $U$ smazáním $B$, $C$ a $D$. Bod, který je v tomto dělení v e společném trojúhelníku s úsečkou $AE$ si označíme $F$. Toto dělení nám rozdělilo $U$ na trojúhelníky a jeden šestiúhelník $ABCDEF$. Navíc má každý vrchol u sebe sudý počet uhlopříček. Přikreslíme tedy ještě uhlopříčky $AC$, $CE$ a $EA$. Tím jsme sudost ve vrcholech neporušili a celý $U$ je rozdělený na trojůhelníky, čímž je úloha vyřešena.Příklad 8. Pět loupežníků uloupilo 100 zlatých mincí. Rozhodi se, že si je rozdělí standardním loupežníckým způsobem, tedy:
Zkuste si rozmyslet, jak by hra dopadla, kdybychom měli pouze jednoho loupežníka. Jak hra dopadne když budeme mít dva? Inu, mladší loupežník ví, že když bude hlasovat proti, dostane všechny mince a navíc bude moct staršího loupežníka zabít. To znamená, že bude hlasovat proti bez ohledu na to, jaké dělení druhý loupežník navrhne (a tento loupežník hru nepřežije). Co z toho plyne pro situaci, kdy jsou loupežníci tři?
Příklad 9. Kolejní topinkovač opeče chleba z jedné strany za 5 minut a vejdou se na něj současně 2 chleby. Je možné s jeho pomocí opéci 3 chleby každý z obou stran během 15 minut?
Příklad 10. Tabulku čokolády o $m \times n$ dílcích chceme rozlámat na jednotlivé dílky. Kolik nejméně rozlomení potřebujeme? A kolik nejvíce?
Příklad 11. (hvězdičkový) Na špejli o délce $20\operatorname{cm}$ je několik mravenců. Každý se pohybuje rychlostí 1 centimetr za vteřinu nějakým směrem. Mravenec, který dojde na konec špejle, spadne ze špejle na zem. Když se dva mravenci potkají, každý z nich se otočí a pokračuje opačným směrem. Za jakou nejkratší dobu již na špejli jistě nebudou žádní mravenci?
Představte si na chvíli, že se mravenci o sebe neotáčejí, ale prostě se míjejí. Najdete určitou paralelu s naší situací?
Příklad 12. V tajuplném sklepení stojí 3 pytle. V jednom jsou červené míčky, v druhém modré míčky, ve třetím směs modrých a červených míčků. Jednou si někdo dal tu práci, aby každý pytel označil cedulkou popisující, co je uvnitř. A podruhé si někdo jiný dal tu práci, aby cedulky proházel tak, že ani jedna nesouhlasí. Ve sklepě je tma, ale můžeme vytáhnout jednu věc z pytle podle našeho výběru a jít se na ni pořádně podívat ven. Jak zjistit, který pytel je který, pomocí co nejméně cest ven?
Příklad 13. Kolika způsoby umíme vybrat množiny $A,B \subseteq \{1,\dots, n\}$, pro které platí:
Příklad 14. (hvězdičkový) Kolik je neklesajících zobrazení $f: \{1,\dots , n\} \rightarrow \{1,\dots , m\}$? Kolik takových zobrazení je monotónních?
Příklad 15. Opět lámání čokolády, tentokrát pro dva hráče. Hráči se pravidelně střídají v tazích. Ten, který je zrovna na tahu, si vybere jednu z částí čokolády a libovolně ji rozlomí, pouze je zakázáno odlamovat kousky $1\times1$. Kdo nemůže udělat tah, prohrál. Rozhodněte, kdo má vyhrávající strategii: