Diskr´etn´ı matematika

1 / 43

Diskr´ etn´ı matematika

Petr Kov´aˇr petr.kovar@vsb.cz

Vysok´a ˇskola b´aˇnsk´a – Technick´a univerzita Ostrava

zimn´ı semestr 2021/2022

DiM 470-2301/01, 470-2301/03*, 470-2301/05

2 / 43

O tomto souboru

Tento soubor je zam´yˇslen pˇredevˇs´ım jako pom˚ucka pro pˇredn´aˇsej´ıc´ıho.

Radu d˚ˇ uleˇzit´ych informac´ı v souboru nenajdete, protoˇze pˇredn´aˇsej´ıc´ı je ˇr´ık´a, ukazuje, pˇr´ıpadnˇe maluje na tabuli. Pˇredn´aˇsky jsou na webu k dispozici, aby studenti mohli snadno dohledat prob´ıran´a t´emata z pˇredn´aˇsek, kter´e zameˇskali.

Pro samostatn´e studium doporuˇcuji skripta:

M. Kubesa: Z´aklady diskr´etn´ı matematiky, v´yukov´y text P. Kov´aˇr: ´Uvod do teorie graf˚u, v´yukov´y text

Pro pˇr´ıpravu ke zkouˇsce a p´ısemk´am doporuˇcuji cviˇcebnici:

P. Kov´aˇr: Cviˇcen´ı z diskr´etn´ı matematiky, sb´ırka pˇr´ıklad˚u Vˇse na http://homel.vsb.cz/~kov16/predmety dm.php

3 / 43

C´ıslo pˇredmˇˇ etu: 470-2301/01, 470-2301/03*, 470-2301/05 Rozsah: 6 kredit˚u (2/2/2), *5 kredit˚u (2/2/1)

Garant: Petr Kov´aˇr

Pˇredn´aˇs´ı: cz: Petr Kov´aˇr, Michael Kubesa, en: Tereza Kov´aˇrov´a Web: am.vsb.cz/kovar

Email: petr.kovar@vsb.cz Kancel´aˇr: EA536

4 / 43

Bodov´e hodnocen´ı

Z´apoˇctov´e p´ısemky

kaˇzd´y t´yden (poˇc´ınaje tˇret´ım) 2–10 minut

boduj´ı se 0/1/2 (ne/t´emˇeˇr spr´avnˇe/zcela spr´avnˇe) kaˇzd´y druh´y t´yden nav´ıc teoretick´a ot´azka

poˇc´ıt´a se 4 nejlepˇs´ı 2-bodov´e a 4 nejlepˇs´ı 3-bodov´e z 10 p´ısemek celkem aˇz 20 bod˚u

pˇri absenci studenta se p´ısemka poˇc´ıt´a za 0 bod˚u

Zad´an´ı cviˇcebn´ıch pˇr´ıklad˚u najdete na http://am.vsb.cz/kovar.

Rozdˇeleno do 14 okruh˚u. Cviˇc´ıc´ı urˇc´ı, ze kter´ych okruh˚u se p´ıˇse p´ısemka.

5 / 43

Bodov´e hodnocen´ı (pokraˇcov´an´ı)

Samostatn´y projekt

zad´av´an´ı v druh´e polovinˇe semestru

projekt: dva aˇz ˇctyˇri pˇr´ıklady (diskr´etn´ı matematika & teorie graf˚u) Bonusov´e “Projekty, pro ty, kteˇr´ı se chtˇej´ı nˇeco nauˇcit”

dva pˇr´ıklady (1 diskr´etn´ı matematika & 1 teorie graf˚u) celkem 10 bod˚u (u bonusov´eho v´yjimeˇcnˇe i v´ıce) pro z´ısk´an´ı z´apoˇctu mus´ı b´yt projekt pˇrijat (detailn´ı popis projektu je na webu)

samostatn´e vypracov´an´ı, odevzd´av´arna http://odevzdej.cz dodrˇzet term´ın odevzd´an´ı7. prosince 2020

Z´apoˇcet =alespoˇn 10 bod˚ua pˇrijat´y projekt.

6 / 43

Bodov´e hodnocen´ı (pokraˇcov´an´ı)

Zkouˇska

zkouˇskov´e term´ıny stanoveny koncem semestru celkem 70 bod˚u

vzorov´a p´ısemka na webu (http://am.vsb.cz/kovar) m˚uˇzete pouˇz´ıvat jednu stranu A4 rukou psan´ych pozn´amek definice, vˇety a vztahy, ale nesm´ı obsahovat ˇreˇsen´e pˇr´ıklady

7 / 43

Literatura

(ˇc´ast textu M. Kubesa: Z´aklady diskr´etn´ı matematiky, v´yukov´y text on-line).

P. Kov´aˇr: Algoritmizace diskr´etn´ıch strukturon-line.

P. Kov´aˇr: ´Uvod do teorie graf˚u, v´yukov´y texton-line.

P. Kov´aˇr: Cviˇcen´ı z diskr´etn´ı matematiky, sb´ırka pˇr´ıklad˚u on-line.

J. Matouˇsek, J. Neˇsetˇril: Kapitoly z diskr´etn´ı matematiky, Karolinum Praha 2000.

ˇreˇsen´e pˇr´ıklady formou pencast˚u on-line.

M˚uˇzete pouˇz´ıvat i jin´a skripta/knihy, ale pozor:detaily se mohou liˇsit!

U zkouˇsky nutno pracovat s pojmy, jak byly zavedeny na pˇredn´aˇsce.

Konzultaˇcn´ı hodiny

(pˇredbˇeˇznˇe) st 9:30–11:00 na EA536.

web http://am.vsb.cz/kovar

8 / 43

Ochutn´avka probl´em˚u

Ulohy, kter´´ e se nauˇc´ıme bˇehem semestru ˇreˇsit:

pod´av´an´ı rukou. . .

systematick´e vygenerov´an´ı vˇsech ˇsestic na tikety sportky . . . devˇet kamar´ad˚u si d´av´a po tˇrech d´arc´ıch. . .

tˇri domy a tˇri studny. . . sedm most˚u mˇesta Kr´alovce. . . chybˇej´ıc´ı cifra rodn´eho ˇc´ısla. . . oprava UPC k´odu. . .

Monty Hall. . .

Dalˇs´ı zaj´ımav´e probl´emy i pˇr´ıklady k procviˇcen´ı:

http://am.vsb.cz/kovar.

9 / 43

Z pˇredchoz´ıho semestru zn´ate

Kapitola 0. Opakov´ an´ı

ˇ

c´ıseln´e obory

mnoˇziny a mnoˇzinov´e operace relace

d˚ukazov´e techniky matematick´a indukce

10 / 43

C´ıseln´ˇ e obory a celoˇc´ıseln´y interval

Pˇrirozen´a a cel´a ˇc´ısla

pˇrirozen´a ˇc´ısla znaˇc´ıme N={1,2,3,4,5, . . .} neobsahuj´ıˇc´ıslo 0 pˇrirozen´a ˇc´ısla vˇcetnˇe nuly znaˇc´ıme N0 ={0,1,2,3,4,5, . . .}

cel´a ˇc´ısla znaˇc´ıme Z={. . . ,−3,−2,−1,0,1,2,3,4, . . .}

Interval cel´ych ˇc´ısel od a do b je mnoˇzina {a,a+ 1, . . . ,b−1,b}

znaˇc´ıme: [a,b] ={a,a+ 1, . . . ,b−1,b}

Srovnejte s intervalem re´aln´ych ˇc´ısel (a,b).

Pˇr´ıklady

[3,7] ={3,4,5,6,7} [−2,−2] ={−2}

[5,0] =∅ (pr´azdn´a mnoˇzina)

11 / 43

Kart´ezsk´y souˇcin a kart´ezsk´a mocnina

Kart´ezsk´y souˇcinmnoˇzin A×B ={(a,b) :a∈A, b ∈B}

je mnoˇzina vˇsech uspoˇr´adan´ych dvojic prvk˚u vybran´ych po sloˇzk´ach z mnoˇzin AaB v dan´em poˇrad´ı.

A₁×A₂× · · · ×A_n={(a₁,a₂, . . . ,a_n) :a_i ∈A_i, i = 1,2, . . . ,n}

Pro A₁ =A₂=. . .=A_ndostaneme kart´ezskou mocninu Aⁿ.

Definujeme A⁰ ={∅},A¹=A.

A

B A×B a

b

♣ ♥ ♠

(a,♣) (b,♣)

(a,♥) (b,♥)

(a,♠) (b,♠)

Kart´ezsk´y souˇcin mnoˇzin A×B={a,b} × {♣,♥,♠}.

Potenˇcn´ı mnoˇzina

je mnoˇzina obsahuj´ıc´ı vˇsechny podmnoˇziny mnoˇziny A 2^A ={X :X ⊆A}.

12 / 43

Mnoˇzinov´y syst´em nad A

nebo tak´e syst´em mnoˇzinnad Aje nˇejak´a mnoˇzina T ⊆2^A. D´av´ame pˇrednost term´ınu

”syst´em mnoˇzin“ pˇred

”mnoˇzina mnoˇzin“.

r b

g y

g r

b y

Vˇsechny moˇzn´e podmnoˇzniny mnoˇziny barev C ={r,g,b,y}.

13 / 43

Rozˇs´ıˇren´e sjednocen´ı a pr˚unik mnoˇzin Rozˇs´ıˇren´e sjednocen´ı

n

[

i=1

Xi a pr˚unik

n

\

i=1

Xi mnoˇzin.

Mˇejme indexovou mnoˇzinu J, lze pouˇz´ıt i [

j∈J

X_j a \

j∈J

X_j.

Pˇr´ıklady

Pro kaˇzd´ei ∈Npoloˇzme Ai ={1,2, . . . ,i}.

5

[

i=1

A_i ={1,2,3,4,5},

5

\

i=1

A_i ={1},

∞

\

i=1

A_i ={1}

Ot´azky Jak vypad´a \

j∈J

Aj proJ ={2,5}?

Jak vypad´a [

j∈J

A_j proJ =N?

14 / 43

Definice

(Homogenn´ı) bin´arn´ı relaceR na mnoˇzinˇeA je libovoln´e podmnoˇzina kart´ezsk´eho souˇcinuA×A=A², tj.

R⊆A².

Definice

(Homogenn´ı) n-´arn´ı relace S na mnoˇzinˇe Aje libovoln´e podmnoˇzina kart´ezsk´e mocniny A×A× · · · ×A=Aⁿ, tj.

S ⊆Aⁿ.

Pˇr´ıklad

Relace mezi studenty, kteˇr´ı z´ıskali stejnou zn´amku z DiM.

Relace mezi dvojicemi student˚u, kdo m´a vyˇsˇs´ı sk´ore z p´ısemky.

Relace mezi dokumenty s podobn´ymi pojmy (plagi´aty). . .

Bin´arn´ı relace je speci´aln´ı pˇr´ıpad n-´arn´ı relace. (un´arn´ı, tern´arn´ı, . . . ).

(Homogenn´ı) relace na dan´e mnoˇzinˇe je speci´aln´ı pˇr´ıpad (heterogenn´ı) relace mezi mnoˇzinami. V´ıce v pˇredmˇety UTI.

15 / 43

Relace ekvivalence Definice

Ekvivalence na mnoˇzinˇeA jereflexivn´ı, symetrick´a a tranzitivn´ıbin´arn´ı relace na mnoˇzinˇe A. Znaˇc´ıme '.

Definice

Mˇejme relaci ekvivalence'na mnoˇzinˇe A.Tˇr´ıdou ekvivalence prvkux (znaˇc´ıme ['x]) rozum´ıme podmnoˇzinu ['x] ={z ∈A:z 'x}.

['a]

['b]

['c]

['d]

Relace ekvivalence vyjadˇruje vztah

”m´ıt stejnou vlastnost“.

Pˇr´ıklady

relace kongruence(m´ıt stejn´y zbytek po dˇelen´ı ˇc´ıslemn); znaˇc´ı se ≡ relace vyjadˇruj´ıc´ı vztah mezi studenty

”m´ıt stejnou zn´amku z DIM“

relace

”synonyma v jazyce“ je (vˇetˇsinou) ekvivalence

16 / 43

Relace ˇc´asteˇcn´eho uspoˇr´ad´an´ı

Uspoˇr´ad´an´ı a ekvivalence jsou nejbˇeˇznˇejˇs´ı typy relac´ı.

Definice

C´ˇasteˇcn´e uspoˇr´ad´an´ıjereflexivn´ı, antisymetrick´a a tranzitivn´ıbin´arn´ı relace na mnoˇzinˇe A. Mnoˇzina s relac´ıse naz´yv´aposet.

Slovoˇc´asteˇcn´e zd˚urazˇnuje, ˇze se nemus´ı jednat o´uplnou relaci naA, tj. ne kaˇzd´a dvojice prvk˚u mus´ı b´yt v relacixRy nebo yRx.

C´ˇasteˇcn´e uspoˇr´ad´an´ı m˚uˇzeme zn´azornit pomoc´ıhasseovsk´eho diagramu je-lix y, bude prveky zakreslen v´yˇs neˇz prvek x,

prvkyx ay spoj´ıme ˇc´arkou, jestliˇze xy; vynech´ame vˇsechny spojnice, kter´e vyplynou z tranzitivity.

1

2 3

4

5 6

7 8

9 10

1 2

3

4 5

6

17 / 43

Pojem matematick´eho d˚ukazu

Struktura vˇety (tvrzen´ı) v matematice: P ⇒D

Pˇresnˇe formulovan´e pˇredpokladyP, za kter´ych plat´ıtvrzen´ı vˇetyD. Podrobn´y postup, jak z pˇredpoklad˚u odvodit tvrzen´ı vˇety naz´yv´ame d˚ukaz.

Matematick´y d˚ukaz

nˇejak´eho tvrzen´ıD je koneˇcn´a posloupnost krok˚u/v´yrok˚u, kde kaˇzd´y krok je:

axiom– obecnˇe platn´y ˇci pˇredpokl´adan´y fakt (volba axiom˚u z´avis´ı na matematick´e teorii^∗), pˇredpoklad P je podm´ınka, na kterou se omez´ıme,

v´yrok odvozen´yz pˇredchoz´ıch krok˚u uˇzit´em nˇekter´eho z platn´ych odvozovac´ıch pravidel (z´avis´ı na pouˇzit´e logice).

Posledn´ı krok obsahuje jako v´yrok tvrzen´ı D.

∗R˚uzn´a odvˇetv´ı matematiky vych´az´ı z r˚uzn´ych axiom˚u. Zat´ımco diskr´etn´ı matematika vych´az´ı z Peanov´ych axiom˚u, napˇr´ıklad geometrie (nejstarˇs´ı exaktnˇe budovan´a matematick´a discipl´ına) vych´az´ı z pˇetiEuklidov´ych axiom˚u.

19 / 43

K ˇcemu to budu jako absolvent potˇrebovat?

”K ˇcemu je novorozenˇe?“

spr´avn´e pochopen´ı omezen´ı pouˇzit´ych metod argumentace pro a proti navrˇzen´emu ˇreˇsen´ı srovn´an´ı kvality r˚uzn´ych ˇreˇsen´ı

100% korektnost metody/algoritmu je nˇekdy vyˇzadov´ana (autopilot, jednotka intenzivn´ı p´eˇce, ˇr´ızen´ı satelit˚u)

20 / 43

Princip matematick´e indukce

Princip matematick´e indukceje jedna z nejˇcastˇeji pouˇz´ıvan´ych d˚ukazov´ych technik pro tvrzen´ı (v´yrokov´e formy) z´avisl´e na pˇrirozen´em parametru n (oznaˇcujemeP(n)).

Matematick´a indukce

Mˇejme tvrzen´ıP(n) s celoˇc´ıseln´ym parametrem n. Necht’ plat´ı:

Z´aklad indukce:

Tvrzen´ıP(n₀) je pravdiv´e, kde n₀ = 0 nebo 1, nebo obecn´e cel´en₀. Indukˇcn´ı krok:

Vyslov´ımeindukˇcn´ı pˇredpoklad: Pro nˇejak´e n tvrzen´ıP(n) plat´ı.

Uk´aˇzeme, ˇze pro kaˇzd´e n>n₀ z platnosti P(n) plyne platnost P(n+ 1).

Pak P(n)plat´ı pro vˇsechna pˇrirozen´a n≥n₀.

Matematickou indukci lze ´uspˇeˇsnˇe vyuˇz´ıvat pˇri dokazov´an´ı spr´avnosti algoritm˚u.

Uk´aˇzeme nˇekolik pˇr´ıklad˚u. . .

21 / 43

Poˇckat!

Ale. . .

uk´aˇzeme z´aklad indukce,

uk´aˇzeme platnost indukˇcn´ıho kroku (s vyuˇzit´ım indukˇcn´ıho pˇredpokladu),

. . . nicm´enˇe tvrzen´ı m´a platit pronekoneˇcnˇe mnohohodnot!?!

Pˇr´ıklad

Jak vysoko lze vystoupat na ˇzebˇr´ık?

Pˇredpokl´adejme, ˇze um´ıme vstoupit na prvn´ı pˇr´ıˇcku,

z kaˇzd´e pˇr´ıˇcky n vystoupit na pˇr´ıˇckun+ 1.

. . . tak um´ıme vystoupat libovolnˇe vysoko!

22 / 43

Vˇeta

Souˇcet prvn´ıch n sud´ych ˇc´ısel jen(n+ 1).

2 + 4 + 6 = 12 = 3·4

2 + 4 + 6 + 8 + 10 + 12 + 14 + 16 + 18 + 20 = 110 = 10·11 D˚ukaz matematickou indukc´ı vzhledem k n:

Dokazujeme, ˇze ∀n∈Nplat´ıPn

i=12i =n(n+ 1).

Z´aklad indukce: Pro n= 1 tvrzen´ı P(1) zn´ı

”2 = 1·2“.

Indukˇcn´ı krok: Plyne z platnostiP(n) platnostP(n+ 1)?

Tj. pokudPn

i=12i =n(n+ 1), takPn+1

i=1 2i = (n+ 1)(n+ 2)?

Vyslov´ımeindukˇcn´ı pˇredpoklad P(n):

Pˇredpokl´adejme, ˇze ∃n∈N:Pn

i=12i =n(n+ 1).

Nyn´ı Pn+1

i=1 2i = Pn

i=12i+ 2(n+ 1)^IP=n(n+ 1) + 2(n+ 1) = (n+ 1)(n+ 2).

Uk´azali jsme ˇze s vyuˇzit´ım znalosti vztahu pro souˇcet prvn´ıch n sud´ych ˇc´ısel lze obdrˇzet odpov´ıdaj´ıc´ı vztah pro souˇcet prvn´ıch n+ 1 sud´ych ˇc´ısel.

Podle principu matematick´e indukce tvrzen´ı plat´ı∀n∈N.

23 / 43

Siln´a matematick´a indukce (ve srovn´an´ı s matematickou indukc´ı)

Matematick´a indukce

Mˇejme tvrzen´ıP(n) s celoˇc´ıseln´ym parametrem n. Necht’ plat´ı:

Z´aklad indukce:

Tvrzen´ıP(n₀) je pravdiv´e, kde n₀ = 0 nebo 1, nebo obecn´e cel´en₀. Indukˇcn´ı krok:

Vyslov´ımeindukˇcn´ı pˇredpoklad: Pro nˇejak´e n tvrzen´ıP(n) plat´ı.

Uk´aˇzeme, ˇze pro kaˇzd´e n>n₀ z platnosti P(n) plyne platnost P(n+ 1).

Pak P(n)plat´ı pro vˇsechna pˇrirozen´a n≥n₀. Siln´a matematick´a indukce

Z´aklad indukce: Tvrzen´ıP(n0) je pravdiv´e.

Indukˇcn´ı krok:

Indukˇcn´ı pˇredpoklad: Tvrzen´ıP(k) plat´ı pro vˇsechnan₀≤k <n.

Uk´aˇzeme, ˇze pak plat´ı tak´eP(n).

Pak P(n)plat´ı pro vˇsechna pˇrirozen´a n≥n₀.

24 / 43

Pˇr´ıklad

Pro nal´am´an´ı ˇcokol´ady rozmˇeru p×r d´ılk˚u je vˇzdy potˇrebapr−1 zlom˚u.

D˚ukaz silnou matematickou indukc´ı podle n=pr:

Z´aklad indukce:

Pro n₀ = 1 m´ame jeden d´ılek a je tˇreba pr−1 = 0 zlom˚u.

Indukˇcn´ı krok:

Necht’ nyn´ı tvrzen´ı plat´ı pro vˇsechny ˇcokol´ady o m´enˇe neˇz n d´ılc´ıch.

Mˇejme libovolnou tabulku o n d´ılc´ıch. Tabulku rozlom´ıme a dostaneme dvˇe menˇs´ı tabulky o s,t d´ılc´ıch, kde 1≤s,t<n a s+t=n. Kaˇzdou z nich um´ıme podle pˇredpokladu nal´amat pomoc´ı s−1 resp.t−1 zlom˚u. Celkem je tˇreba

(s −1) + (t−1) + 1 =s+t−1 =n−1 zlom˚u.

Podle principu siln´e matematick´e indukce tvrzen´ı plat´ı∀p,r ∈N.

25 / 43

Pˇrehled pˇredn´aˇsky

Kapitola 1. Posloupnosti

posloupnosti sumy a produkty aritmetick´a posloupnost geometrick´a posloupnost horn´ı a doln´ı cel´a ˇc´ast

26 / 43

Posloupnost

Posloupnost je seˇrazen´ım nˇekolika prvk˚u.

Koneˇcnou posloupnost znaˇc´ıme (ai)ⁿ_i=1 = (a1,a2, . . . ,an).

Nekoneˇcnou posloupnost znaˇc´ıme (a_i)^∞_i=1 = (a_i) = (a1,a2, . . .).

v matematick´e anal´yze definov´any jako zobrazen´ıp:N→R um´ıme urˇcit prvn´ı, druh´y, tˇret´ı, ... prvek posloupnosti indexy jsou pˇrirozen´a ˇc´ısla, obvykle od 1

prvky posloupnosti se mohouopakovat (na rozd´ıl od mnoˇzin) posloupnost m˚uˇze b´yt i pr´azdn´a

Pˇr´ıklady (x,v,z,v,y)

(2,3,5,7,11,13,17,19,23,29) (2,3,5,7,11,13,17,19,23,29, . . .) (1,−1,1,−1,1,−1,1,−1, . . .)

Zad´av´ame: v´yˇctem prvk˚u, rekurentnˇe nebo vztahem pro n-t´y ˇclen

27 / 43

Suma

Suma je souˇcet prvk˚u posloupnosti, znaˇc´ıme

n

X

i=1

a_i =a₁+a₂+· · ·+an−1+a_n X

i∈J

a_i =a_i1+a_i2+· · ·+a_in, kde J={i₁,i₂, . . . ,i_n}.

Ot´azka

X

i∈{1,3,5,7}

i² =?

Pˇr´ıklad

n

X

i=1

i =?

28 / 43

Souˇcin

Souˇcinprvk˚u posloupnosti, znaˇc´ıme

n

Y

i=1

ai =a1·a2· · · · ·an−1·an

Y

i∈J

a_i =a_i1·a_i2· · · · ·a_in, kde J={i₁,i₂, . . . ,i_n}

Pˇr´ıklady

5

X

i=2

ln(i) = ln

5

Y

i=2

i

!

= ln (2·3·4·5) = ln 120

n

X

i=1 n

X

j=1

(i·j) =

n

X

i=1



i·

n

X

j=1

j



=

n

X

i=1

i

!

·





n

X

j=1

j



= 1

2n(n+ 1) 2

pr´azdn´y souˇcet

2

X

i=3

i = 0 pr´azdn´y produkt

2

Y

i=3

i = 1

29 / 43

Pˇr´ıklady

n

X

i=1

(i+j) =

n

X

i=1

i+

n

X

i=1

j = n

2(n+ 1) +nj J ={2,8,12,21}, X

j∈J

j = 2 + 8 + 12 + 21 = 43

Ot´azky

5

X

i=1

ln(i) =?

100

X

i=1

i =?

6

Y

i=1

i =?

n

Y

i=1

i =?

n

Y

i=1

(n−i) =?

n

X

i=1

(n+ 1−i) =?

30 / 43

Ot´azka

Existuje takov´a posloupnost (ai)ⁿ_i=1, ˇze Pn

i=1ai <Pn

i=1(−a_i)?

Ot´azka

Najdete takovou posloupnost (a_i)ⁿ_i=1, ˇze Pn

i=1a_i >0 a Qn

i=1a_i <0?

Ot´azka

Existuje takov´a posloupnostkladn´ych ˇc´ısel (a_i)ⁿ_i=1, ˇze Pn

i=1a_i >Qn i=1a_i?

31 / 43

Aritmetick´a posloupnost

Nˇekter´e posloupnosti jsou speci´aln´ı a um´ıme o nich mnoho ˇr´ıci.

Aritmetick´a posloupnost

Posloupnost (ai) se naz´yv´aaritmetick´a, jestliˇze m´a tvar

a, a+d, a+ 2d, a+ 3d, . . .

Re´aln´e ˇc´ısloa jepoˇc´ateˇcn´ı ˇclen a re´aln´e ˇc´ıslod jediference posloupnosti.

Vˇsimnˇete si, ˇze posloupnost (a_i) je aritmetick´a, jestliˇze existuje takov´e re´aln´e ˇc´ıslod, ˇze pro kaˇzd´e i >1 plat´ıa_i −ai−1 =d.

Kaˇzd´y dalˇs´ı ˇclen vznikne z pˇredchoz´ıho pˇriˇcten´ım (stejn´e!) diferenced. Lze pracovat i s koneˇcnou aritmetickou posloupnost´ı.

M´amen ˇclen˚u

a,a+d,a+ 2d, . . . ,a+ (n−1)d.

32 / 43

Pˇr´ıklady

−2,3,8,13,18, . . . prvn´ı ˇclen −2, diference 5

−3,2,7,12,17, . . . prvn´ı ˇclen −3, diference 5 20,9,−2,−13,−24, . . . prvn´ı ˇclen 20, diference −11

√ 2,√

2,√ 2,√

2,√

2, . . . prvn´ı ˇclen √

2, diference 0 Pˇr´ıklad

Sestavte vztahy pro n-t´y ˇclen posloupnosti an z pˇredchoz´ıho pˇr´ıkladu

−2,3,8,13,18, . . . a_n=−2 + (n−1)5

−3,2,7,12,17, . . . a_n=−3 + (n−1)5 20,9,−2,−13,−24, . . . an= 20−(n−1)11

√ 2,√

2,√ 2,√

2,√

2, . . . an=√ 2 Pˇr´ıklad

Jakou posloupnost urˇcuje vztah pro n-t´y ˇclenan=−8 + 5n?

Druhou posloupnost−3,2,7,12,17, . . .

33 / 43

Souˇcet n ˇclen˚u aritmetick´e posloupnosti

a1+a2+· · ·+an=

n

X

i=1

ai

V naˇsem pˇr´ıpadˇe

a+ (a+d) +· · ·+a+ (n−1)d =

n

X

i=1

(a₁+ (i−1)d) plat´ı

n

X

i=1

(a₁+ (i−1)d) = n

2(a₁+a_n) =n

2(2a₁+ (n−1)d) =na₁+n(n−1)d

2 .

Souˇcet nˇekter´ych po sobˇe jdouc´ıchn ˇclen˚u aritmetick´e posloupnosti

k+n−1

X

i=k

ai = n

2(ak +ak+n−1) = n

2(2ak+ (n−1)d) =nak+n(n−1)d

2 .

34 / 43

Nˇekolik postˇreh˚u

Souˇcet nekoneˇcn´e aritmetick´e posloupnosti obecnˇe neexistuje.

Posloupnost ˇc´asteˇcn´ych souˇct˚u diverguje k +∞ prod >0, diverguje k −∞ prod <0,

prod = 0 diverguje k +∞ nebo k −∞ nebo konverguje dlea1. Aritmetickou posloupnost s prvn´ım ˇclenem aa diferenc´ıd lze zadat rekurentnˇe

a_n=an−1+d, a₁=a.

35 / 43

Pˇr´ıklad spoˇren´ı

Pˇr´ıklad

Str´yˇcek Skrbl´ık m´a v sejfu 4 514 cent˚u. Kaˇzd´y t´yden ukl´ad´a do sejfu 24 cent˚u. Sestavte vztah pro n-t´y ˇclen posloupnosti.

4 514,4 538,4 562,4 586,· · ·= 4 514 + 24(n−1) = 4 490 + 24n.

Pˇr´ıklad

Str´yˇcek Skrbl´ık m´a v sejfu 4 514 cent˚u. Tˇrem synovc˚um d´a kaˇzd´emu kapesn´e jeden cent a kaˇzd´y t´yden kaˇzd´emu kapesn´e o cent zv´yˇs´ı.

a) Sestavte vztah pro celkovou v´yˇsi kapesn´eho vn-t´em t´ydnu.

b) Sestavte vztah pro poˇcet cent˚u v sejfu zan t´ydn˚u.

a) kapesn´e k = 3 + 3(n−1) = 3n b) v sejfus = 4 514−3n

36 / 43

Geometrick´a posloupnost Geometrick´a posloupnost

Posloupnost (a_i) se naz´yv´ageometrick´a, jestliˇze m´a tvar a, a·q, a·q², a·q³, . . .

Re´aln´e ˇc´ısloa jepoˇc´ateˇcn´ı ˇclen a re´aln´e ˇc´ısloq jekvocient posloupnosti.

Vˇsimnˇete si, ˇze posloupnost (a_i) je geometrick´a, jestliˇze existuje takov´e re´aln´e ˇc´ısloq, ˇze pro kaˇzd´e i >1 plat´ı_a^ai

i−1 =q.

Kaˇzd´y dalˇs´ı ˇclen vznikne z pˇredchoz´ıho vyn´asoben´ım (stejn´ym!) kvocientem q.

Lze pracovat i s koneˇcnou geometrickou posloupnost´ı. Pro n ˇclen˚u a, a·q, a·q², . . . , a·qⁿ⁻¹.

Ot´azka

M˚uˇze b´yt posloupnost souˇcasnˇe geometrick´a a souˇcasnˇe aritmetick´a?

Pokud ano, najdete v´ıce moˇznost´ı? Nekoneˇcnˇe mnoho?

37 / 43

Pˇr´ıklady

2,10,50,250,1250, . . . prvn´ı ˇclen 2, kvocient 5 9,6,4,⁸₃,¹⁶₉, . . . prvn´ı ˇclen 9, kvocient ²₃ 4,−2,1,−¹₂,¹₄, . . . prvn´ı ˇclen 4, kvocient−¹₂

√ 2,√

2,√ 2,√

2,√

2, . . . prvn´ı ˇclen √

2, kvocient 1 Pˇr´ıklad

Sestavte vztahy pro n-t´y ˇclen an posloupnost´ı z pˇredchoz´ıho pˇr´ıkladu.

2,10,50,250,1250, . . . a_n= 2·5ⁿ⁻¹ 9,6,4,⁸₃,¹⁶₉, . . . a_n= 9· ²₃n−1

= ²⁷₂ · ²₃n

4,−2,1,−¹₂,¹₄, . . . an= 4· −¹₂n−1

=−8· −¹₂n

√ 2,√

2,√ 2,√

2,√

2, . . . a_n=√ 2 Pˇr´ıklad

Jakou posloupnost urˇcuje vztah pro n-t´y ˇclenan= ¹₂n

? ¹₂,¹₄,¹₈,₁₆¹, . . .

38 / 43

Souˇcet n ˇclen˚u geometrick´e posloupnosti

a1+a2+· · ·+an=

n

X

i=1

ai

V naˇsem pˇr´ıpadˇe

a+ (a·q) +· · ·+a·qⁿ⁻¹ =

n

X

i=1

(a₁·qⁱ⁻¹) pro q6= 1 plat´ı

n

X

i=1

(a1·qⁱ⁻¹) =a1

qⁿ−1 q−1 .

Proq = 1 je posloupnost souˇcasnˇe aritmetick´a a jej´ı souˇcet poˇc´ıt´ame jinak.

Ot´azka

Jak vypad´a souˇcet prvn´ıchn ˇclen˚u geometrick´e posloupnosti s kvocientem 1?

39 / 43

Nˇekolik postˇreh˚u

Souˇcet nekoneˇcn´e geometrick´e posloupnosti obecnˇe neexistuje pro|q| ≥1,

proq = 1 konstantn´ı posloupnost; souˇcet z´avis´ı na a₁, proq =−1 osciluj´ıc´ı posloupnost, souˇcet nem´a pro|q|<1 koneˇcn´y souˇcet _1−q^a1

Posloupnost ˇc´asteˇcn´ych souˇct˚u diverguje pro q ≥1,

osciluje (a nekonverguje) pro q≤ −1, konverguje k _1−q^a1 pro|q|<1.

Geometrickou posloupnost s prvn´ım ˇclenema a kvocientemq lze zadat rekurentnˇe

a_n=an−1·q, a₁ =a.

40 / 43

Pˇr´ıklad spoˇren´ı

Pˇr´ıklad

Str´yˇcek Skrbl´ık m´a v bance uloˇzeno 4 514 cent˚u. Kaˇzd´y rok mu ´uspory z´uroˇc´ı dvˇema procenty (bez zaokrouhlen´ı). Sestavte vztah pro ˇc´astku zan let.

4 514,4 604.3,4 696.4,4 790.3,4 886.1,4 983.8,· · ·= 4 514·1.02ⁿ⁻¹.

Pˇr´ıklad

Str´yˇcek Skrbl´ık m´a v sejfu 4 514 cent˚u. Tˇrem synovc˚um d´a kaˇzd´emu kapesn´e jeden cent a kaˇzd´y t´yden kaˇzd´emu kapesn´e zdvojn´asob´ı.

a) Sestavte vztah pro celkovou v´yˇsi kapesn´eho vn-t´em t´ydnu.

b) Sestavte vztah pro poˇcet cent˚u v sejfu zan t´ydn˚u.

a) kapesn´e k = 3·2ⁿ⁻¹ = ³₂ ·2ⁿ b) v sejfus = 4 514−3·2ⁿ⁻¹

41 / 43

Pˇr´ıklad

Vych´yl´ıme kyvadlo do v´yˇsky 5 cm. Vlivem tˇren´ı se pˇri kaˇzd´em kmitu sn´ıˇz´ı energie kyvadla o jednu pˇetinu. Sestavte posloupnost v´yˇsek, do jak´ych kyvadlo vystoup´a po kaˇzd´em kmitu.

5 cm, 4 cm, 16

5 cm, 64

25 cm, 256

125 cm, . . . , 5· 4

5 n−1

cm prvn´ı ˇclen 5 cm,

kvocient ⁴₅. Ot´azka

Po kolika kmitech se kyvadlo zastav´ı?

42 / 43

Horn´ı a doln´ı cel´a ˇc´ast re´aln´eho ˇc´ısla

Cel´a ˇc´ast re´aln´eho ˇc´ısla

bxc(doln´ı) cel´a ˇc´astre´aln´eho ˇc´ısla x dxehorn´ı celou ˇc´astre´aln´eho ˇc´ıslax Pˇr´ıklady

b3.14c= 3 b−3.14c=−4 bxc=dxe ⇒ x∈Z

Ot´azka

Ud´av´a v´yraz dlogne poˇcet ˇc´ıslicn v des´ıtkov´e soustavˇe?

Pokud ne, um´ıte naj´ıt

”spr´avnou“ formuli?

Ot´azka l n

n+1

m

=?, kden ∈N (a pro n∈N0?)

43 / 43

Pˇr´ıˇst´ı pˇredn´aˇska

Z´ akladn´ı kombinatorick´ e v´ ybˇ ery

princip nez´avisl´ych v´ybˇer˚u kombinatorick´e pravidlo souˇctu kombinatorick´e pravidlo souˇcinu metoda dvoj´ıho poˇc´ıt´an´ı