Autorem materiálu a všech jeho částí, není-li uvedeno jinak, je Mgr. Daniel HanzlíkObchodní akademie a Střední odborná škola logistická, Opava, příspěvková organizace.

Materiál byl vytvořen v rámci projektu OP VK 1.5 – EU peníze středním školám,registrační číslo CZ.1.07/1.5.00/34.0809.

KOMBINATORICKÁPRAVIDLAII. ČÁST22.. října 2012 VY_32_INOVACE_110202_Kombinatoricka_pravidla _ II._ cast_DUM

obr. 1

KOMBINATORIKAKombinatorika je součástí finitní matematiky, která studuje konečné soubory, tj. množiny a uspořádané k-tice, .

obr. 2

KOMBINATORIKAOpět si objasníme, že mnohé kombinatorické úlohy se dají řešit pomocí dvou základních pravidel:a) kombinatorického pravidla součtub) kombinatorického pravidla součinu.

obr. 3

KOMBINATORICKÁ PRAVIDLANyní si připomeňme znovu obě kombinatorická pravidla, s nimiž jsme se seznámili v minulém výukovém materiálu.Kombinatorická pravidla – 1. část

obr. 4

KOMBINATORICKÉ PRAVIDLO SOUČTUJsou-li , …, konečné množiny s , , prvky a jsou-li každé dvě disjunktní, pak množina má + + … + prvků.

obr. 5

KOMBINATORICKÉ PRAVIDLO SOUČINUPočet uspořádaných k-tic, jejichž první členlze vybrat způsoby a každý další člen lzepo výběru všech předcházejících vybrat postupně , , …, způsoby, je roven …

obr. 5

KOMBINATORICKÁ PRAVIDLA – PRAKTICKÁ ČÁSTK názornějšímu pochopení oboukombinatorických pravidel součtu a součinu slouží opět čtyři matematické úlohy, které jsou uvedenéspolečně s řešením.obr. 3

NABÍDKA ÚLOH A JEJICH ŘEŠENÍÚloha 1

Řešení úlohy 4Úloha 4

Řešení úlohy 2

Úloha 2

Řešení úlohy 3

Úloha 3

Řešení úlohy 1

ÚLOHA 1 Na obrázku je vyznačen trojúhelníkový obrazec. Určete počet všech trojúhelníků, jejichž strany leží na přímkáchtohoto obrazce.

A

B C

zpět do nabídky úloh

ŘEŠENÍ ÚLOHY 1Množinu všech trojúhelníků se stranami na přímkách obrazce označme Následně utvořme její podmnožiny tak, že:v jsou všechny trojúhelníky o straně délky 1, v jsou všechny trojúhelníky o straně délky 2,v jsou všechny trojúhelníky o straně délky 3.Množiny jsou vzájemně disjunktní (průnikem jeprázdná množina) a jejich sjednocením je celá množina .Označme počet prvků množiny .Dále označme počty prvků všech tří podmnožin. Podle kombinatorického pravidla součtu platí:

pokračování

ŘEŠENÍ ÚLOHY 1Jednoduše určíme: .Počet trojúhelníků o straně délky 2 určíme tak, že si povšimneme, že každý z bodů A, B, C je středem právě jednoho takového trojúhelníku. Platí taky obráceně, že každý z trojúhelníků o straně délky 2 má střed právě v jednom z bodů A, B, C.Počet trojúhelníků o straně délky 2 se rovná počtu těchto bodů: Pro počet trojúhelníků, jejichž strany leží na přímkách obrazce jsme vyvodili:.Počet trojúhelníků je 13.

zpět do nabídky úloh

ÚLOHA 2 Z místa A do místa B vede 5 turistických tras. Z místa Bdo místa C 6 turistických tras. Určete:a) kolika způsoby může turista dojít z místa A do místa C, chce-li se zastavit v místě B,b) kolika způsoby může dojít z místa A jen do místa B a zpět, nechce-li jít zpátky stejnou cestou.

zpět do nabídky úloh

obr. 6

ŘEŠENÍ ÚLOHY 2a) Z místa A do místa B vede 5 turistických tras, označme je . Z místa B do místa C vede 6 turistických tras, tyto trasy označme . Počet způsobů, kterými může turista dojít z místa A do místa C (se zastávkou v místě B) odpovídá počtu uspořádaných dvojic: , kde je označení pro libovolnou trasu z místa A do místa B, je označení pro libovolnou trasu z místa B do místa C.Pro 1. místo v uspořádané dvojici máme 5 možností výběru, tj. .Pro 2. místo v uspořádané dvojici máme 6 možností výběru, tj. .Počet uspořádaných dvojic: .Turista může dojít z místa A do místa C (se zastávkou v místě B) třiceti způsoby.

pokračování

obr. 6

ŘEŠENÍ ÚLOHY 2 zpět do nabídky úlohb) Z místa A do místa B vede 5 turistických tras, označme je . Z místa B do místa A vede stejných 5 turistických tras.Počet způsobů, kterými může turista dojít z místa A do místa B a zpět, nepůjde-li zpátky stejnou cestou , odpovídá počtu uspořádaných dvojic: , kde je označení pro libovolnou trasu z místa A do místa B, je označení pro libovolnou trasu z místa B do místa A.Pro 1. místo v uspořádané dvojici máme 5 možností výběru, tj. .Pro 2. místo v uspořádané dvojici máme 4 možností výběru (podle podmínky musíme vyloučit tu trasu, kterou šel turista z místa A do místa B) tj. .Počet uspořádaných dvojic: .Turista může dojít z místa A do místa B a zpět, nepůjde-li zpátky stejnou cestou, dvaceti způsoby. obr. 6

ÚLOHA 3Určete počet všech trojciferných přirozených čísel, v jejichž dekadickém zápisu je každá z číslic 0, 4, 5, 6, 7 nejvýše jednou.

zpět do nabídky úloh

obr. 7

ŘEŠENÍ ÚLOHY 3 zpět do nabídky úlohKaždé trojciferné přirozené číslo, které splňuje podmínky, je určeno uspořádanou trojicí sestavenou pouze z číslic 0, 4, 5, 6, 7 tak, že každé 2 její členy jsou různé a její první člen není nula. Na 1. místě v trojciferném čísle mohou být 4 možnosti výběru (4, 5, 6, 7): 4 _ _ 5 _ _ 6 _ _ 7_ _.Pro 2. místo v trojciferném čísle máme opět 4 možnosti výběru (může zde být nula, ale nesmí tady být číslice z 1. místa).Pro 3. místo v trojciferném čísle máme 3 možnosti výběru (nemohou zde být číslice vybrané pro 1. a 2. místo).Počet uspořádaných trojic je podle kombinatorického pravidla součinupři označení = 3 počtů možností výběru 1., 2. a 3. místa v trojciferném čísle:.Existuje 48 trojciferných přirozených čísel z daných číslic.

obr. 7

ÚLOHA 4Silnice vedoucí podél břehů řeky jsou mezi místem A najednom břehu řeky a místem B na druhém břehu řeky propojeny 4 mosty. Určete, kolika způsoby je možno dojet z A do B, jestliže po každém mostu a každým bodem každé silnice smíme projet nejvýše jednou. Na obr. je vyznačen jeden ze způsobů.

A

B

a a a

b b b

zpět do nabídky úloh

obr. 8

ŘEŠENÍ ÚLOHY 4Označme písmenem a každý úsek mezi dvěma sousedními mosty na tom břehu řeky, na kterém se nachází místo A. Dále označme písmenem b každý úsek mezi dvěma sousedními mosty na druhém břehu. Každou cestu z A do B vyznačíme pomocí uspořádané trojice sestavené z písmen a, b podle toho, kterým z úseků a v jakém pořadí cesta povede. Např. podle úvodního obr. uspořádaná trojice (b, b, a). Takovéto uspořádané trojici odpovídá právě jedna cesta z místa A do místa B.Počet způsobů, jak dojít z místa A do místa B se rovná počtu uspořádaných trojic.

pokračování

obr. 8

ŘEŠENÍ ÚLOHY 4Počet způsobů určíme snadno: pro 1. člen máme 2 možnosti výběru (a, b), pro 2. i 3. člen máme opět 2 možnosti výběru. Výběr 2. a 3. členu není omezen výběrem 1. členu.Podle kombinatorického pravidla součinu pro počet uspořádaných trojic platí:.Počet způsobů, jak dojet z místa A do místa B, je 8.

zpět do nabídky úloh

obr. 8

ZÁVĚREMVe čtyřech kombinatorických úlohách jsme seprakticky zaměřili na využití dvou základníchkombinatorických pravidel.Volně jsme tak navázali na výukový materiál:„Kombinatorická pravidla – 1.část“.V dalších výukových materiálech se seznámíme s dalšími částmi kombinatoriky – tj. matematickévědy, která se zabývá množinami a uspořádanýmik-ticemi.

obr. 1

CITACE ZDROJŮPoužitá literatura:1) CALDA, Emil. Matematika pro netechnické obory SOŠ a SOU, 3. díl. Havlíčkův Brod: Prometheus, spol. s r. o., 2000, s. 168, 170. ISBN 80-7196-109-4. 2) POLÁK, Josef. Přehled středoškolské matematiky. Praha: Prometheus, spol. s. r. o., 1998., s. 288. ISBN 80-85849-78-X.

CITACE ZDROJŮPoužité obrázky:1) GLIVICKÝ, Petr. File:Mathematicsgeneral.jpg – Wikimedia Commons [online]. 6 September 2006 [cit. 2012-10-22]. Dostupné pod licencí Creative Commons z: http://commons.wikimedia.org/wiki/File:Mathematicsgeneral.jpg?uselang=cs#filehistory 2) PAJS. File:Math mnoziny cisel.png - Wikimedia Commons [online]. 14 August 2006 [cit. 2012-10-22]. Dostupné pod licencí Creative Commons z:http://commons.wikimedia.org/wiki/File:Math_mnoziny_cisel.png 3) SOUL, Obsidian. File:Stick figure - choosing.jpg - Wikimedia Commons [online]. 29 January 2012 [cit. 2012-10-22]. Dostupné pod licencí Creative Commons z: http://commons.wikimedia.org/wiki/File:Stick_figure_-_choosing.jpg 4) BAŤHA, Matěj. File:D6 smajlik.jpg - Wikimedia Commons [online]. 24 April 2008 [cit. 2012-10-22]. Dostupné pod licencí Creative Commons z: http://commons.wikimedia.org/wiki/File:D6_smajlik.jpg 5) SOUL, Obsidian. File:Stick figure - choice.jpg - Wikimedia Commons [online]. 29 January 2012 [cit. 2012-10-22]. Dostupné pod licencí Creative Commons z: http://commons.wikimedia.org/wiki/File:Stick_figure_-_choice.jpg

CITACE ZDROJŮPoužité obrázky:6) LONSPA. File:Turisticky denik.jpg – Wikimedia Commons [online]. 1 November 2011 [cit. 2012-10-22]. Dostupné pod licencí Creative Commons z: http://commons.wikimedia.org/wiki/File:Turisticky_denik.jpg?uselang=cs 7) GALAKSIAFERVOJO. File:Math.jpg - Wikimedia Commons [online]. 4 April 2006 [cit. 2012-10-22]. Dostupné pod licencí Creative Commons z: http://commons.wikimedia.org/wiki/File:Math.jpg 8) CAPPER, Ian. File:Greta bridges - Bridge 4 - geograph.org.uk - 771960.jpg – Wikimedia Commons [online]. 11 April 2008 [cit. 2012-10-22]. Dostupné pod licencí Creative Commons z: http://commons.wikimedia.org/wiki/File:Greta_bridges_-_Bridge_4_-_geograph.org.uk_-_771960.jpg?uselang=cs

Všechny úpravy psaného textu byly prováděny v programu MS PowerPoint.

KONEC PREZENTACE.DĚKUJI VÁM ZA POZORNOST.Mgr. Daniel Hanzlík