IBOOO Úvod do informatiky -- príklady na procvičení
Sada 1 -- Řešení
Upozornění
Vzorová řešení dostáváte k dispozici, abyste mohli zkontrolovat správnost svých řešení.
Můžete je použít i jako návody k řešení jednotlivých příkladů tak, že je budete číst po
částech a budete se snažit další krok provést vždy sami. Příklady ztratí veškerý svůj
smysl, pokud se je budete učit jako básničku. Snažte se nad nimi přemýšlet a vyřešit je
sami, než se podíváte do vzorových řešení.
Téma
Základní důkazové techniky. Přímý důkaz, důkaz obměnou, důkaz sporem. Protipříklad.
Matematická indukce.
Příklad 1.
Dokažte následující tvrzení. Používejte matematické zápisy.
a) Součet dvou sudých čísel je sudé číslo.
b) Součet dvou lichých čísel je sudé číslo.
c) Je-li x2
sudé číslo, potom i x je sudé číslo. (Vizte větu 6 z přednášky.)
Řešení
a) Tvrzení dokážeme přímo. Nechť 2m a 2n, m,n E Z, jsou dvě libovolná sudá čísla.
Potom 2m + 2n = 2{m + n) je také sudé číslo.
b) Toto tvrzení je analogické předchozímu, dokážeme jej také přímo. Nechť 2m + 1 a
2n + 1, m, n E Z, jsou dvě libovolná lichá čísla. Potom {2m+ 1) + (2n + 1) = 2{m + n + 1)
je číslo sudé.
c) Dokážeme obměnu tvrzení. Budeme tedy dokazovat: ,,Není-li x sudé číslo, potom x2
není sudé číslo." Číslo není sudé právě tehdy, pokud je liché. Proto můžeme dokazované
tvrzení ještě dále upravit na ,,Je-li x liché číslo, potom i x2
je liché číslo."
Mějme tedy libovolné liché číslo 2n + 1, n E Z. Potom (2n + l)2
= An2
+ An + 1 =
= 2{2n2
+ 2n) + 1 je také liché číslo.
Protože platí obměněné tvrzení, platí i tvrzení původní.
Příklad 2.
Rozhodněte, zda platí následující tvrzení a jejich platnost dokažte nebo vyvraťte.
a) Pro každé přirozené číslo n platí, že (n + l)3
+ (n -- l)3
je dělitelné dvěma.
b) Pro každé přirozené číslo n platí, že (n + l)3
+ (n -- l)3
je dělitelné třemi.
c) Každé přirozené číslo je dělitelné dvěma různými přirozenými čísly.
Řešení
a) Tvrzení platí. Pokud se vám nepodařilo jej dokázat, zkuste to nyní, když
víte, že platí.
Tvrzení dokážeme opět přímo, algebraickými úpravami výrazu.
(n + l)3
+ (n- l)3
= (n3
+ 3n2
+ 3n + 1) + (n3
- 3n2
+ 3ra - 1) = 2n3
+ 6n = 2(n3
+ 3ra)
1
b) Tvrzení neplatí. Pokud jste tento příklad nevyřešili, zkuste to nyní, když
víte, že neplatí.
Pokud chceme ukázat, že tvrzení neplatí, zpravidla bývá nejlepší nalézt protipříklad.
V případě, že tvrzení je ve tvaru implikace, se protipříkladem rozumí konkrétní hodnoty,
které splňují předpoklady tvrzení, ale nesplňují jeho závěr.
Předpokladem tohoto tvrzení je ,,nechť n je přirozené číslo". Závěr tohoto tvrzení je
,,výraz je dělitelný třemi". Musíme tedy nalézt takové přirozené číslo n, pro nějž výraz
nebude dělitelný třemi. Takovým číslem je například n = 1. Platí
(1 + 1)3
+ ( 1 - 1 ) 3
= 8
ale 8 není dělitelné třemi.
Existují i další protipříklady? Umíte je všechny stručně charakterizovat?
c) Tvrzení neplatí. Pokud jste tento příklad nevyřešili, zkuste to nyní, když
víte, že neplatí.
Protipříkladem je číslo 1, které je dělitelné pouze sebou samým.
Existují i další protipříklady? Umíte je všechny stručně charakterizovat?
Příklad 3.
Dokažte, že pro všechna přirozená čísla n, 0 < n platí:
n / n
\
<'= EO
í=0 \í=0 /
Řešení
K důkazu využijeme tvrzení, jehož platnost byla dokázána na přednášce:
^-^ . n(n + 1)
Důkaz povedeme matematickou indukcí.
Základní krok. Pro n = 0 rovnost zřejmě platí:
o / o \ 2
>3
= "= EO
í=0 \i=0 J
Indukční předpoklad. Předpokládejme, že rovnost platí pro nějaké přirozené číslo m.
Pozor: nepředpokládáme platnost rovnosti pro všechna přirozená čísla; to teprve dokazujeme.
Předpokládáme tedy, že platí
m / m \ ^
E'3
= EO
i=0 \i=0 /
Indukční krok. Pomocí indukčního předpokladu dokážeme, že rovnost platí i pro
m + 1. Chceme tedy dokázat, že
9 2
m / m \ z
m+1 /m+1 \
Ei3
= EM =* Ei3
= EM
i=0 \í=0 J i=0 \í=0 J
2
Vyjdeme z pravé strany rovnosti a postupně ji budeme upravovat.
o o o
fm+1 \ / m \ z
m / m N z
^ i ) = í ( m + l ) + ^ í ) = (TO+1)2
+ 2 ( T O + 1 ) ^ \ + I J ^ \
. i=0 / V i=0 / i=0 \i=0
(m + l)2
+ 2(m + 1)--^ + J2l
"
(druhý člen jsme upravili podle tvrzení z přednášky,
třetí člen podle indukčního předpokladu)
m m
Til^ x ^ .'X / - \ 'x x ^ .3
(m + 1)2
(1 + 2-) + J ] z3
= (m + l)3
+ J2%
2
í=0 í=0
rn+l
= <3
i=0
To jsme měli dokázat.
Alternativně je možné dosadit vztah z přednášky do dokazovaného vztahu hned a
matematickou indukcí dokázat tvrzení: pro všechna přirozená čísla n, 0 < n platí
A . 3 _ n 2
( n + 1 ) 2
Z^ 4
i=0
Důkaz bude zcela analogický důkazu tvrzení z přednášky. Napište jej.
Příklad 4.
Dokažte, že pro libovolné přirozené číslo n, 0 < n je ^TM=1(2i -- 1) druhou mocninou
přirozeného čísla.
Řešení
Onou druhou mocninou přirozeného čísla je n2
. Budeme tedy dokazovat, že
(2i
-!) n2
i=l
pro všechna přirozená čísla n, 0 < n. Pokud jste tento příklad nevyřešili, zkuste
to nyní.
Tvrzení dokážeme matematickou indukcí.
Základní krok. Pro n = 1 rovnost platí, neboť
 ( 2 i - 1) = 1 = Is
i=l
Indukční krok. V indukčním kroku budeme dokazovat následující implikaci: platí-li
rovnost pro nějaké přirozené číslo m, potom platí i pro m + 1. Nechť je tedy m takové
přirozené číslo, pro nějž platí ^^= 1 (2i -- 1) = m2
.
Potom
m+l
Y^ (2i - 1) = h(m + 1) - l) + J2(2i - 1) = 2m + 1 + m2
= (m + l)2
i=i i=i
To jsme měli dokázat.
Příklad 5.
Matematickou indukcí dokažte tvrzení (je to zobecněná trojúhelníková nerovnost):
Pro všechna kladná přirozená čísla n platí
Ei=i
ˇJL">
n
i=i
kde xi,...,xn jsou libovolná reálná čísla.
Řešení
Nerovnost nejprve dokážeme pro n = 2. Dokážeme tedy, že platí \x\ + 21 < |^i| +
+ \x21ˇ Pokud jste tuto nerovnost brali jako známý fakt, zkuste ji dokázat
nyní. Důkaz rozdělíme na čtyři případy.
0 < xi, 0 < X2- Potom \xi + X2I = x\ + X2 = \x\\ + \x%\0
< x\, X2 < 0. Potom \x\ +X2I < max(|xi|, |a?21) < |^i| + |a?21 - Opravdu chápete,
proč to platí?
xi < 0, 0 < X2- Analogicky jako předchozí případ.
X\ < 0, X2 < 0. Potom \xi + X2I = --X\ -- X2 = \%i\ + \X2\Právě
dokázané tvrzení nemá žádný vztah ke struktuře důkazu matematickou indukcí,
který provedeme níže. Není to ani základní krok, ani indukční předpoklad. Je
to ,,jen" pomocné tvrzení, které nám umožní použít indukční předpoklad v indukčním
kroku.
Základní krok. Pro n = 1 dostáváme nerovnost \xi\ < \xi\, která zřejmě platí pro
libovolné reálné číslo x\.
Indukční krok. Nechť nerovnost platí pro nějaké přirozené číslo m, 0 < m, tedy nechť
platí
Ei=i
m
í=l
kde xi,... ,xm jsou libovolná reálná čísla. Musíme ukázat, že potom nerovnost platí i
pro m + 1. Nechť xi,..., xm+i jsou libovolná reálná čísla.
m+l
E
í=i
Xi Xm+1 + ^2Xi
í=l
< \x.m+l I Eí=i
m m+l
< \xm+l\ + ^2 \Xi\ = ^2 \Xi
í=l í=l
První nerovonost je aplikací speciálního případu pro n = 2, který jsme dokázali výše.
Druhá nerovnost plyne z indukčního předpokladu.
4