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ý.
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.
Příklad 3. Dokažte indukcí podle k  0, že číslo (26k - 1) je dělitelné
sedmi.
Příklad 4. Každá n-prvková množina má právě 2n podmnožin (včetně
prázdné). Formálně
2X
= 2|X|
.
Příklad 5. Počet všech permutací n-prvkové množiny je n!, pro každé
n  0.
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.
1
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ě.
2