Příklady matematických důkazů
Zkoušejte hledat řešení (důkazy) pro následující příklady. Řešte je pokud
možno po pořadí, nejprve po týdnu zveřejním první půlku řešení, pak teprve
druhou.. .
Mnoho zdaru!
Příklad 1. Co je špatného na následujícím "důkaze"?
Ukážeme, že platí 2 = -2: Umocněním na druhou vzejde 22 = 4 = (-2)2,
což je platná rovnost, a proto i původní vztah 2 = -2 je platný.
Řešení. Špatné je, že byl použit obrácený postup kroků ­ od neznámého
závěru tvrzení zpět ke známým faktům, důkaz však musí jít vždy od
známého k závěrům. 2
Příklad 2. Co je špatného na následujícím "důkaze"?
Nechť a, b jsou celá čísla. Vyjdeme z předpokladu a = b a ukážeme, že
a = -b. (Tj. po dosazení a = b = 2 opět vyjde 2 = -2.) Umocněním
výchozího předpokladu a = b získáme a2 = b2, neboli 0 = a2 - b2 = (a +
b)(a-b). Pak je i 0(a-b) = 0 = (a+b)(a-b) a dále po zkrácení 0 = a+b,
tedy a = -b.
Řešení. Nyní je postup kroků správný, ale chybné je krácení výrazem
(a - b), neboť a - b = 0 a nulou se nesmí krátit. 2
Příklad 3. Dokažte indukcí podle k  0, že číslo (26k - 1) je dělitelné
sedmi.
Řešení. Budeme postupovat indukcí podle parametru k  0.
ˇ Pro k = 0 platí, že 20 - 1 = 0 je dělitelné sedmi.
ˇ Nechť nyní tvrzení platí pro nějaké k. Podívejme se, o kolik se změní
hodnota výrazu (26k - 1) při zvětšení k o jedna:
26(k+1)
- 1 - 26k
- 1 = 26
 26k
- 26k
= 26k
 (26
- 1) = 26k
 63
Důležitým faktem nyní je, že číslo 63 je dělitelné sedmi. To ale
znamená, že pokud (26k - 1) bylo dělitelné sedmi podle indukčního
předpokladu, bude sedmi dělitelné i 26(k+1) - 1.
Formálně tento indukční krok zapíšeme následovně: Nechť dle in-
dukčního předpokladu 26k - 1 = 7, kde  je nějaké přirozené číslo.
Pak
26(k+1)
- 1 = 26
 26k
- 1 = (26
- 1)  26k
+ 26k
- 1 = 63  26k
+ 7 =
1
= 7  9  26k
+  ,
takže i tento výraz je dělitelný sedmi.
2
Příklad 4. Každá n-prvková množina má právě 2n podmnožin (včetně
prázdné). Formálně
2X
= 2|X|
.
Řešení. Matematickou indukcí podle n:
ˇ Pro n = 0 tvrzení platí, neboť prázdná množina má jedinou
podmnožinu, opět prázdnou.
ˇ Nechť nyní tvrzení platí pro n  0. Vezmeme libovolnou množinu X
o n + 1 > 0 prvcích. Zvolme prvek a  X a označme X = X \ {a},
|X| = n. Potom všech podmnožin P  X je podle indukčního
předpokladu 2n. Pro prvek a navíc máme nezávislý výběr ze dvou
možností: buď a dáme do podmnožiny P, nebo nedáme. Celkem je
tak 2  2n = 2n+1 možností volby podmnožiny P  X, cbd.
Důkaz je hotov podle principu matematické indukce. 2
Příklad 5. Počet všech permutací n-prvkové množiny je n!, pro každé
n  0.
Řešení. Indukcí podle n: Tvrzení platí pro n = 0, protože žádné prvky
lze uspořádat jen jedním způsobem (stejně tak jeden prvek).
Mějme nyní n  0 a množinu P o n + 1 prvcích, předpokládejme pro
jednoduchost P = {1, 2, . . . , n + 1}. Zvolme první prvek p  P naší permu-
tace jedním z n + 1 způsobů. Chtělo by se přímo říct, že potom už je volba
zbytku permutace P \{p} nezávislá na volbě prvního p, ale to formálně není
pravda. Aby tomu tak skutečně bylo, musíme si zbylé prvky P \{p} nejprve
"přečíslovat" na {1, 2, . . . , n}, což počet voleb neovlivní.
Pak už však zbytek plyne jasně ­ n-prvková množina {1, 2, . . . , n} má
podle indukčního předpokladu n! permutací, proto P má celkem (n+1)n! =
(n + 1)! permutací. To je přesně to, co chceme. 2
2
Návod pro následující ­ metoda dvojího počítání:
Nechť každý případ nějakého (složeného) výběru lze dále rozlišit (zjemnit)
na stejný počet  zjemněných možností. Dále nechť získaný zjemněný výběr
má celkem m různých možností (které jsme schopni spočítat). Potom počet
všech možností původního výběru je dán podílem m/.
Příklad 6. Počet všech k-prvkových variací z n-prvkové množiny je n!
(n-k)!,
pro každé n  k  0.
Řešení. Metodou dvojího počítání:
Budeme se dvěma způsoby dívat na výběr permutací n-prvkové množiny.
Jak již víme, lze tyto permutace vybrat n! různými způsoby. Na druhou
stranu lze vzít některou k-prvkovou variaci, její prvky dát na začátek per-
mutace v jejich pořadí a zbylých n - k prvků seřadit za nimi jedním z
(n-k)! různých způsobů. Z různých variací tímto postupem zřejmě získáme
různé výsledné permutace, a přitom každou permutaci lze získat z variace
vybírající jejích prvních k prvků.
Označíme-li x neznámý počet všech k-prvkových variací z n-prvkové
množiny, lze výše popsaným postupem vytvořit právě x  (n - k)! všech
různých permutací n-prvkové množiny. Proto platí
x  (n - k)! = n! ,
x =
n!
(n - k)!
.
2
3
Příklad 7. Počet všech k-prvkových kombinací z n-prvkové množiny je
n
k , pro každé n  k  0.
Příklad 8. Dokažte platnost následujícího vztahu pro všechna přirozená
n  1:
n
i=1
(2i - 1)  3i
= (n - 1)  3n+1
+ 3
(Matematickou indukcí.)
Návod pro následující ­ Dirichletův princip:
Rozmístíme-li  + 1 (nebo více) objektů do  přihrádek, v některé přihrádce
musí být aspoň dva objekty.
Příklad 9. Mezi čtyřmi přirozenými čísly vždy najdeme dvě, jejichž rozdíl
je dělitelný číslem 3.
Příklad 10. Na letním táboře 29 dětí stráví celkem 16 dní a 15 nocí.
Každou noc jsou dva z táborníků na hlídce. Dokažte, že některé z dětí musí
jít na hlídku za celý tábor aspoň dvakrát.
Příklad 11. 8 kamarádů jelo na 9 dní dovolené. Každý den některá
(jedna) trojice z nich šla na výlet. Dokažte, že někteří dva z nich ani jednou
nebyli spolu na výletě.
4