ˇ MASARYKOVA UNIVERZITA V BRNE Pˇr´ırodovˇedeck´a fakulta
Bakal´aˇrsk´a pr´ace z matematiky
Sb´ırka u ´ loh z kombinatoriky pro stˇ redoˇ skol´ aky
Brno 2007
ˇ Petr Surek
Prohl´ aˇ sen´ı: Prohlaˇsuji, ˇze jsem tuto bakal´aˇrskou pr´aci vypracoval samostatnˇe pod veden´ım doc. RNDr. Eduarda Fuchse, CSc. a uvedl v seznamu vˇsechnu pouˇzitou literaturu. Souˇcasnˇe souhlas´ım, aby byla pr´ace uloˇzena v knihovnˇe Pˇr´ırodovˇedeck´e fakulty Masarykovy univerzity v Brnˇe a popˇr´ıpadˇe tak´e zpˇr´ıstupnˇena na internetov´ ych str´ank´ach fakulty ke studijn´ım u ´ˇcel˚ um.
V Brnˇe dne 15. kvˇetna 2007
................................................... ˇ Petr Surek
Podˇ ekov´ an´ı: R´ad bych podˇekoval doc. RNDr. Eduardu Fuchsovi, CSc. za ochotu, vstˇr´ıcnost a trpˇelivost, se kter´ ymi vedl moji bakal´aˇrskou pr´aci, a za cenn´e rady a pˇripom´ınky k n´ı. D´ale bych chtˇel tak´e podˇekovat doc. RNDr. Zdenku Karp´ıˇskovi, CSc. a doc. Ing. Milanu Svobodovi, CSc. za poskytnut´ı literatury a spousty cenn´ ych rad, kter´e mi velmi pomohly bˇehem zpracov´av´an´ı moj´ı bakal´aˇrsk´e pr´ace.
Obsah ´ Uvod
6
Jednoduch´ e kombinatorick´ eu ´ lohy
7
1 Permutace
10
2 Variace
14
3 Kombinace
17
´ Ulohy k opakov´ an´ı I
20
4 Permutace s opakov´ an´ım
26
5 Variace s opakov´ an´ım
29
6 Kombinace s opakov´ an´ım
32
´ Ulohy k opakov´ an´ı II
35
7 Dirichlet˚ uv princip
38
8 Princip inkluze a exkluze
40
Seznam pouˇ zit´ e literatury
43
5
´ Uvod Ve sv´e bakal´aˇrsk´e pr´aci jsem se snaˇzil sestavit sb´ırku pˇr´ıklad˚ u z kombinatoriky v rozsahu stˇredoˇskolsk´eho studia. Pˇr´ıklady jsem strukturoval podle obt´ıˇznosti od standardn´ıch a jednoduch´ ych aˇz po n´aroˇcn´e pˇr´ıklady, vhodn´e pro voliteln´e doplˇ nkov´e semin´aˇre. Jednotliv´e u ´lohy byly pˇrevzaty a vybr´any z doporuˇcen´e literatury. Tato pr´ace obsahuje celkem 168 pˇr´ıklad˚ u z kombinatoriky pro stˇredoˇskol´aky. Je ˇclenˇena do ˇctyˇr odd´ıl˚ u podle n´aroˇcnosti u ´loh. Prvn´ı odd´ıl tvoˇr´ı jednoduch´e u ´lohy z kombinatoriky vyuˇz´ıvaj´ıc´ı vˇetu o pravidle souˇctu a pravidle souˇcinu. Obsahuje 16 pˇr´ıklad˚ u na procviˇcen´ı, vˇzdy s udan´ ymi v´ ysledky ˇreˇsen´ı. Druh´ y odd´ıl tvoˇr´ı kapitoly 1, 2, 3 obsahuj´ıc´ı jednoduˇsˇs´ı pˇr´ıklady permutac´ı, variac´ı a kombinac´ı. Kaˇzd´a kapitola uv´ad´ı potˇrebn´e definice a vˇzdy ˇreˇsen´ı nˇekolika zad´an´ı. Pak je pˇripojeno v tˇechto kapitol´ach celkem 28 pˇr´ıklad˚ u na procviˇcov´an´ı, vˇzdy s udan´ ymi v´ ysledky ˇreˇsen´ı. Na z´avˇer odd´ılu jsou pˇripojeny u ´lohy k opakov´an´ı l´atky kapitol 1, 2 a 3. Je to celkem 36 pˇr´ıklad˚ u, vˇzdy s udan´ ymi v´ ysledky ˇreˇsen´ı. Tˇret´ı odd´ıl tvoˇr´ı kapitoly 4, 5 a 6 obsahuj´ıc´ı n´aroˇcnˇejˇs´ı u ´lohy permutac´ı s opakov´an´ım, variac´ı s opakov´an´ım a kombinac´ı s opakov´an´ım. I v tomto odd´ılu, v kaˇzd´e kapitole, jsou uv´adˇeny potˇrebn´e definice a podrobnˇe pops´ano ˇreˇsen´ı nˇekolika zad´an´ı. Kaˇzd´a z kapitol tohoto odd´ılu je uzavˇrena vˇzdy deseti pˇr´ıklady na procviˇcov´an´ı, vˇzdy s udan´ ymi v´ ysledky ˇreˇsen´ı. Na z´avˇer tohoto odd´ılu jsou pˇripojeny u ´lohy k opakov´an´ı l´atky kapitol 4, 5 a 6. Je to celkem 18 pˇr´ıklad˚ u, vˇzdy s udan´ ymi v´ ysledky ˇreˇsen´ı. Posledn´ı dvˇe kapitoly tj. 7 a 8 uv´adˇej´ı n´aroˇcnˇejˇs´ı pˇr´ıklady vhodn´e pro voliteln´e semin´aˇre. Kapitola 7 se vˇenuje Dirichletovu principu, uv´ad´ı definice, n´azorn´a ˇreˇsen´ı pˇeti pˇr´ıklad˚ ua pˇet pˇr´ıklad˚ u na procviˇcov´an´ı opˇet s uv´adˇen´ ymi v´ ysledky ˇreˇsen´ı. Kapitola 8 se pak vˇenuje principu inkluze a exkluze, uv´ad´ı definice a n´azorn´a ˇreˇsen´ı pˇeti pˇr´ıklad˚ u. Nˇekter´e n´aroˇcnˇejˇs´ı pˇr´ıklady z tˇret´ıho odd´ılu (kap. 4, 5 a 6) vhodn´e i pro voliteln´ y semin´aˇr jsou oznaˇceny hvˇezdiˇckou. Na z´avˇer pr´ace je pak uvedena literatura, ze kter´e jsem ˇcerpal mimo r´amec literatury doporuˇcen´e v zad´an´ı. V textu se drˇz´ım obvykl´eho znaˇcen´ı definovan´ ych pojm˚ u. Mnoˇzina pˇrirozen´ ych ˇc´ısel je oznaˇcena N, pˇriˇcemˇz nula nen´ı povaˇzov´ana za pˇrirozen´e ˇc´ıslo. Pˇredpokl´ad´am, ˇze n, k jsou pˇrirozen´a ˇc´ısla, pokud nen´ı ˇreˇceno jinak, tj. n, k ∈ N. 6
Jednoduch´ e kombinatorick´ eu ´ lohy Vˇ eta (Pravidlo souˇctu). Jsou-li A1 , A2 , . . . , An koneˇcn´e mnoˇziny, kter´e maj´ radˇe S ı po ˇS p1 , p2 , . . . , pn prvk˚ u, a jsou-li kaˇzd´e dvˇe disjunktn´ı, pak poˇcet prvk˚ u mnoˇziny A1 A2 · · · An je roven p1 + p2 + . . . + pn . Vˇ eta (Pravidlo souˇcinu). Poˇcet vˇsech uspoˇr´ adan´ych k-tic, jejichˇz prvn´ı ˇclen lze vybrat n1 zp˚ usoby, druh´y ˇclen po v´ybˇeru prvn´ıho ˇclenu n2 zp˚ usoby atd. aˇz k-t´y ˇclen po v´ybˇeru vˇsech pˇredch´ azej´ıc´ıch ˇclen˚ u nk zp˚ usoby, je roven n1 · n2 · · · · · nk . 1. Ze dvou sportovn´ıch ˇserm´ıˇrsk´ ych odd´ıl˚ u, z nichˇz kaˇzd´ y m´a 100 ˇclen˚ u, je tˇreba vybrat po jednom ˇserm´ıˇri pro jistou soutˇeˇz. Kolika zp˚ usoby lze tento v´ ybˇer prov´est? [Podle pravidla souˇcinu existuje 1002 , tj. 10 000 zp˚ usob˚ u v´ ybˇeru] 2. Urˇcete poˇcet vˇsech trojcifern´ ych pˇrirozen´ ych ˇc´ısel, v jejichˇz dekadick´em z´apisu se kaˇzd´a ˇc´ıslice vyskytuje nejv´ yˇse jednou. [9 · 9 · 8· = 648] 3. Urˇcete, kolika zp˚ usoby lze na ˇsachovnici 8 × 8 vybrat dvˇe r˚ uznobarevn´a pol´ıˇcka tak, aby obˇe neleˇzela v t´eˇze ˇradˇe ani v t´emˇze sloupci. [32 · 24 = 768] 4. Ze 3 exempl´aˇr˚ u uˇcebnice algebry, 7 exempl´aˇr˚ u uˇcebnice geometrie a 7 exempl´aˇr˚ u uˇcebnice trigonometrie je tˇreba vybrat po jednom exempl´aˇri kaˇzd´e uˇcebnice. Kolika zp˚ usoby to m˚ uˇzeme prov´est? [3 · 7 · 7 = 147] 5. Urˇcete, kolik dvojjazyˇcn´ ych slovn´ık˚ u je tˇreba k tomu, aby byla zajiˇstˇena moˇznost pˇr´ım´eho pˇrekladu z anglick´eho, francouzsk´eho, nˇemeck´eho a rusk´eho jazyka do kaˇzd´eho z nich. [4 · 3 = 12] 7
6. Z mˇesta A do mˇesta B vede 5 cest, z mˇesta B do mˇesta C vedou tˇri cesty. Urˇcete poˇcet cest, kter´e vedou z A do C a pˇritom proch´azej´ı B. [Podle pravidla souˇcinu dost´av´ame 5 · 3 = 15 cest] 7. Z m´ısta A do m´ısta B vedou ˇctyˇri turistick´e cesty, z m´ısta B do C tˇri. Urˇcete poˇcet zp˚ usob˚ u, jimiˇz lze vybrat trasu (a) z A do C a zpˇet; [12 · 12 = 144] (b) z A do C a zpˇet tak, ˇze z tˇechto sedmi cest nen´ı ˇz´adn´a pouˇzita dvakr´at; [6 · 12 = 72] (c) z A do C a zpˇet tak, ˇze z tˇechto sedmi cest jsou pr´avˇe dvˇe pouˇzity dvakr´at. [1 · 12 = 12] 8. Angliˇcan´e obvykle d´avaj´ı sv´ ym dˇetem nˇekolik jmen. Kolika zp˚ usoby lze pojmenovat ne v´ıce neˇz tˇremi jm´eny novorozenˇe, je-li k dispozici 300 r˚ uzn´ ych jmen? [Novorozenˇe m˚ uˇze dostat 1, 2, nebo 3 jm´ena, pˇriˇcemˇz vˇsechna jm´ena jsou r˚ uzn´a. Celkem je 300 + 300 · 299 + 300 · 299 · 298 = 26 820 600 moˇznost´ı] 9. V koˇs´ıku je 12 jablek a 10 hruˇsek. Petr si m´a z nˇeho vybrat bud’ jablko, anebo hruˇsku tak, aby Vˇera, kter´a si po nˇem vybere jedno jablko a jednu hruˇsku, mˇela co nejvˇetˇs´ı moˇznosti v´ ybˇeru. Urˇcete, co si m´a vybrat Petr. [Jablko] 10. Otec m´a 5 kab´at˚ u, 7 vest a ˇsestery kalhoty. Kolika r˚ uzn´ ymi zp˚ usoby se m˚ uˇze obl´eci? [5 · 7 · 6 = 210] 11. Na vrchol hory vedou ˇctyˇri turistick´e cesty a lanovka. Urˇcete poˇcet zp˚ usob˚ u, kter´ ymi je moˇzno se dostat (a) na vrchol a zpˇet; [25] (b) na vrchol a zpˇet tak, aby zp´ateˇcn´ı cesta byla jin´a neˇz cesta na vrchol; [20]
8
(c) na vrchol a zpˇet tak, aby aspoˇ n jednou byla pouˇzita lanovka; [9] (d) na vrchol a zpˇet tak, aby lanovka byla pouˇzita pr´avˇe jednou. [8] 12. Z 12 slov muˇzsk´eho rodu, 9 ˇzensk´eho a 10 stˇredn´ıho rodu m´ame vybrat po jednom slovu kaˇzd´eho rodu. Kolika zp˚ usoby lze prov´est tento v´ ybˇer? [podle pravidla souˇcinu existuje 12 · 9 · 10 = 1 080 zp˚ usob˚ u] 13. Kolika zp˚ usoby lze vybrat jednu samohl´asku a jednu souhl´asku ze slova ”lavice”? [9] 14. M´ame 8 ˇcerven´ ych vz´ajemnˇe r˚ uzn´ ych kostek a 7 kostek modr´ ych, t´eˇz vz´ajemnˇe rozliˇsiteln´ ych. Kolika zp˚ usoby m˚ uˇzeme vybrat skupinu obsahuj´ıc´ı jednu ˇcervenou a jednu modrou kostku? [56] *15. Urˇcete poˇcet vˇsech ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel, v jejichˇz dekadick´em z´apisu nen´ı nula a ze zb´ yvaj´ıc´ıch dev´ıti ˇc´ıslic se v nˇem kaˇzd´a vyskytuje nejv´ yˇse jednou. Kolik z tˇechto ˇc´ısel je vˇetˇs´ıch neˇz 9 000? Kolik je menˇs´ıch neˇz 3 000? [3 024, vˇetˇs´ıch neˇz 9 000 je 336, menˇs´ıch neˇz 3 000 je 672] *16. Urˇcete poˇcet vˇsech ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel, jejichˇz dekadick´ y z´apis je sloˇzen z ˇc´ıslic 1, 2, 3, 4, 5 (kaˇzd´a z nich se m˚ uˇze opakovat), kter´a jsou dˇeliteln´a (a) pˇeti; [125] (b) dvˇema; [250] (c) ˇctyˇrmi. [125]
9
Kapitola 1 Permutace Definice. Necht’ M je mnoˇzina tvoˇren´a n r˚ uzn´ ymi prvky, n ∈ N. Libovolnou uspoˇr´adanou n-tici, tvoˇrenou prvky t´eto mnoˇziny, naz´ yv´ame n-prvkovou permutac´ı (popˇr. permutac´ı n prvk˚ u) bez opakov´an´ı. Poˇcet permutac´ı n r˚ uzn´ ych prvk˚ u je P (n) = n! kde symbol n! znaˇc´ı n-faktori´ al a n! = n(n − 1) · · · 2 · 1 pro n ∈ N. Speci´alnˇe klademe 0! = 1. Plat´ı (n + 1)! = n! · (n + 1). 1 . pˇ r´ıklad. 6 lid´ı m´ame postavit do fronty, tj. pˇriˇradit jim poˇrad´ı. Kolika zp˚ usoby to lze prov´est? ˇ sen´ı. Kaˇzd´a takov´a ˇsestice je jednou permutac´ı prvk˚ Reˇ u dan´e ˇsestiprvkov´e mnoˇziny. Jejich poˇcet je: P (6) = 6! = 6 · 5 · 4 · 3 · 2 · 1 = 720. 2 . pˇ r´ıklad. 10 r˚ uzn´ ych hraˇcek m´ame rozdat deseti r˚ uzn´ ym dˇetem. Kolika zp˚ usoby to lze prov´est? ˇ sen´ı. Kaˇzd´e d´ıtˇe m´a dostat pr´avˇe jednu hraˇcku, to znamen´a, mus´ıme utvoˇrit deReˇ setiˇclennou permutaci. Tˇechto permutac´ı je P (10) = 10! 3 . pˇ r´ıklad. Kolik slov lze vytvoˇrit z p´ısmen slova ”ˇzralok”(za pˇredpokladu, ˇze mus´ı b´ yt vˇsechna p´ısmena pouˇzita pr´avˇe jednou) Pozn.: Vytvoˇren´a slova nemus´ı m´ıt vˇecn´ y v´ yznam. ˇ sen´ı. Naˇs´ım u Reˇ ´kolem je naj´ıt vˇsechny ˇsestice, vytvoˇren´e z p´ısmen ˇz, r, a, l, o, k. Kaˇzd´a tato ˇsestice odpov´ıd´a jedn´e permutaci z ˇsesti prvk˚ u. Hledan´ y poˇcet je tedy roven poˇctu permutac´ı ˇsestiprvkov´e mnoˇziny, tj. 6! = 720. 4 . pˇ r´ıklad. Urˇcete poˇcet prvk˚ u tak, aby bylo moˇzno z nich utvoˇrit pr´avˇe 362 880 permutac´ı.
10
ˇ sen´ı. Naˇs´ım u Reˇ ´kolem je naj´ıt takov´e ˇc´ıslo n, pro kter´e by platilo: n! = n · (n − 1) · . . . · 2 · 1 = 362 880 Budeme tedy n´asobit po sobˇe jdouc´ı ˇc´ısla od jedn´e do n, dokud nedostaneme ˇc´ıslo 362 880. Velmi brzy zjist´ıme, ˇze 362 880 = 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 K utvoˇren´ı 362 880 permutac´ı je proto tˇreba 9 prvk˚ u. 5 . pˇ r´ıklad. Kolika zp˚ usoby m˚ uˇzeme rozestavit na ˇsachovnici 8 vˇeˇz´ı tak, aby se ˇz´adn´e dvˇe z nich vz´ajemnˇe neohroˇzovaly? ˇ sen´ı. Je zˇrejm´e, ˇze pˇri takov´em rozestaven´ı stoj´ı na ˇsachovnici v kaˇzd´em sloupci i Reˇ v kaˇzd´e ˇradˇe jedin´a vˇeˇz. Uvaˇzujme jednu z tˇechto poloh a oznaˇcme a1 ˇc´ıslo obsazen´eho pole v prvn´ı ˇradˇe, a2 v druh´e ˇradˇe,. . . ,a8 v osm´e ˇradˇe. Pak je a1 , a2 , . . . , a8 urˇcitou permutac´ı z ˇc´ısel 1, 2, . . . , 8 (je jasn´e, ˇze mezi ˇc´ısly a1 , a2 , . . . , a8 nejsou ani dvˇe sobˇe rovn´a; jinak by dvˇe vˇeˇze st´aly v t´emˇze sloupci). Obr´acenˇe, jestliˇze a1 , a2 , . . . , a8 je nˇejak´a permutace ˇc´ısel a1 , a2 , . . . , a8 , pak j´ı odpov´ıd´a jist´e rozestaven´ı vˇeˇz´ı, v nˇemˇz se vz´ajemnˇe neohroˇzuj´ı. To vˇsak znamen´a, ˇze poˇcet hledan´ ych poloh vˇeˇz´ı je roven poˇctu permutac´ı z ˇc´ısel a1 , a2 , . . . , a8 , tj. P8 = 8! = 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 = 40 320. Existuje tedy celkem 40 320 moˇzn´ ych rozestaven´ı vˇeˇz´ı, kter´a splˇ nuj´ı poˇzadovanou podm´ınku. 6 . pˇ r´ıklad. Kolik pˇeticifern´ ych pˇrirozen´ ych ˇc´ısel lze sestavit z ˇc´ıslic 0, 1, 2, 3, 4, maj´ı-li ˇc´ısla konˇcit ˇc´ıslic´ı 1 nebo 3. ˇ sen´ı. Vˇsech skupin dan´ Reˇ ych ˇc´ıslic, kter´e maj´ı na konci ˇc´ıslici 1, je P (4). Od tohoto poˇctu mus´ıme odeˇc´ıst skupiny, kter´e maj´ı na zaˇc´atku ˇc´ıslici 0 a jejichˇz je P (3), nebot’ permutujeme jenom 3 prvky. Tedy pˇeticifern´ ych pˇrirozen´ ych ˇc´ısel konˇc´ıc´ıch ˇc´ıslic´ı 1 je celkem P (4) − P (3). Obdobnou u ´vahou dostaneme poˇcet pˇeticifern´ ych pˇrirozen´ ych ˇc´ısel konˇc´ıc´ıch ˇc´ıslic´ı 3, tj. P (4) − P (3). Vˇsech pˇeticifern´ ych pˇrirozen´ ych ˇc´ısel konˇc´ıc´ıch ˇc´ıslic´ı 1 nebo 3 je tedy 2[P (4) − P (3)] = 2(4! − 3!) = 2 · 18 = 36. 1. V lavici sed´ı pˇet chlapc˚ u, z nichˇz dva bratˇri chtˇej´ı sedˇet vedle sebe. Kolika r˚ uzn´ ymi zp˚ usoby m˚ uˇzeme chlapce pˇresadit? [48] 2. Urˇcete, kolika zp˚ usoby se v ˇsestim´ıstn´e lavici m˚ uˇze posadit ˇsest hoch˚ u, jestliˇze (a) dva chtˇej´ı sedˇet vedle sebe; [2 · 5! = 240] (b) dva chtˇej´ı sedˇet vedle sebe a tˇret´ı chce sedˇet na kraji. [2 · 2 · 4! = 96] 11
3. Urˇcete, kolikr´at lze pˇrem´ıstit slova ve verˇsi ”S´am svobody kdo hoden, svobodu zn´a v´aˇziti kaˇzdou” tak, aby se neprom´ıchala slova vˇety hlavn´ı a vedlejˇs´ı. [2 · (4!)2 = 1 152] 4. Urˇcete poˇcet vˇsech dev´ıtim´ıstn´ ych (a) telefonn´ıch
(b) pˇrirozen´ ych
ˇc´ısel, v jejichˇz z´apisu je kaˇzd´a z deseti ˇc´ıslic kromˇe dev´ıtky. [(a)9!, (b)9! − 8!] 5. Kolik n´ahrdeln´ık˚ u lze sestavit ze 7 kor´alk˚ u r˚ uzn´ ych velikost´ı? Pˇredpokl´adejte, ˇze kaˇzd´ y n´ahrdeln´ık mus´ı obsahovat vˇsechny kor´alky. N´ahrdeln´ıky se nemˇen´ı ani pˇri cyklick´ ych permutac´ıch, ani pˇri ”pˇrevr´acen´ı”. 7! = 360] [ 14
6. Urˇcete, kolika zp˚ usoby je moˇzn´e pˇreskupit p´ısmena slova SYMBOL tak, aby byly mezi 2 samohl´askami pr´avˇe dvˇe souhl´asky. [3 · 2 · 4! = 144] 7. Urˇcete poˇcet prvk˚ u tak, aby (a) bylo moˇzno z nich utvoˇrit pr´avˇe 40 320 permutac´ı; [8] (b) pˇri zvˇetˇsen´ı jejich poˇctu o dva se poˇcet permutac´ı zvˇetˇsil 56kr´at; [6] (c) pˇri zmenˇsen´ı jejich poˇctu o dva se poˇcet permutac´ı zmenˇsil 20kr´at. [5] *8. Urˇcete, kolika zp˚ usoby m˚ uˇze m chlapc˚ u a n d´ıvek nastoupit do z´astupu tak, aby (a) nejdˇr´ıve st´aly vˇsechny d´ıvky a pak vˇsichni chlapci; [n!m!] (b) mezi ˇz´adn´ ymi dvˇema chlapci nebyla ˇz´adn´a d´ıvka ani mezi ˇz´adn´ ymi dvˇema d´ıvkami nebyl ˇz´adn´ y chlapec; [2n!m!] 12
(c) mezi ˇz´adn´ ymi dvˇema chlapci nebyla ˇz´adn´a d´ıvka. N´avod: Uspoˇr´adanou n-tici chlapc˚ u lze zaˇradit na n + 1 m´ıst mezi n dˇevˇcat. [(n + 1)!m!] *9. Pˇredstavte si, ˇze zap´ıˇsete pod sebe vˇsechny permutace ˇc´ısel 1, 2, 3, 4, 5; vznikne tak obd´eln´ıkov´e sch´ema, kter´e m´a 120 ˇr´adk˚ u a 5 sloupc˚ u. Urˇcete souˇcet vˇsech ˇc´ısel v kaˇzd´em sloupci. [360] *10. Urˇcete, kolika nulami konˇc´ı dekadick´ y z´apis ˇc´ısla 258!. N´ avod: Pˇredstavte si ˇc´ıslo 258! ve tvaru 2n1 · 3n2 · 5n3 · 7n4 · 11n5 · . . . · p, kde p je nejvˇetˇs´ı prvoˇc´ıslo menˇs´ı neˇz 258, a zd˚ uvodnˇete, ˇze hledan´ y poˇcet nul je roven menˇs´ımu z ˇc´ısel n 1 , n3 . [63]
13
Kapitola 2 Variace Definice. k-ˇ clenn´ a variace z n prvk˚ u (bez opakov´an´ı), kde n ≥ k, je uspoˇr´adan´a k-tice sestaven´a z tˇechto prvk˚ u tak, ˇze kaˇzd´ y se v n´ı vyskytuje nejv´ yˇse jednou. Poˇcet takov´ ych variac´ı je n! Vk (n) = n · (n − 1) · (n − 2) · . . . · (n − k + 1) = (n − k)! 1 . pˇ r´ıklad. M´ame za u ´kol sestavit ze ˇctyˇr barev (b´ıl´a, modr´a, ˇcerven´a, zelen´a) trojbarevn´e prapory tak, aby se kaˇzd´a barva u jednoho praporu vyskytovala jen jednou. U praporu vˇsak z´aleˇz´ı na poˇrad´ı barev, tj. nen´ı lhostejn´e, kter´a z nich n´asleduje za kterou. ˇ sen´ı. Zvol´ıme-li libovoln´e tˇri barvy, napˇr. b´ılou (oznaˇc´ıme ji struˇcnˇe b), modrou (m) a Reˇ ˇcervenou (ˇc ), m˚ uˇzeme zvolen´e tˇri barvy pˇreskupit tˇemito ˇsesti zp˚ usoby: b,m,ˇc b,ˇc,m m,b,ˇc m,ˇc,b ˇc,m,b ˇc,b,m Ze tˇr´ı zvolen´ ych barev jsme tak dostali 6 moˇzn´ ych seskupen´ı. Vymˇen´ıme-li nyn´ı postupnˇe vˇsechny tˇri barvy za zb´ yvaj´ıc´ı zelenou (z ) a provedeme-li v kaˇzd´e trojici barev podobn´a pˇreskupen´ı, dostaneme tˇechto dalˇs´ıch 18 moˇznost´ı: z,m,ˇc z,ˇc,m m,z,ˇc m,ˇc,z ˇc,m,z ˇc,m,z b,z,ˇc b,ˇc,z z,b,ˇc z,ˇc,b ˇc,z,b ˇc,b,z b,m,z b,z,m m,b,z m,z,b z,m,b z,b,m Zjistili jsme, ˇze ze ˇctyˇr barev je moˇzno sestavit tˇri barvy do trojbarevn´ ych prapor˚ u 24 zp˚ usoby. Takov´ y zp˚ usob sestavov´an´ı je ovˇsem velmi zdlouhav´ y a pracn´ y. Poˇcet moˇzn´ ych seskupen´ı budeme proto v dalˇs´ım poˇc´ıtat pomoc´ı pojmu variace, kter´ y jsme zavedli v´ yˇse. V3 (4) = 4 · 3 · 2 = 24 2 . pˇ r´ıklad. Hokejov´eho turnaje se u ´ˇcastn´ı 8 druˇzstev. Kolika zp˚ usoby mohou b´ yt obsazena prvn´ı tˇri m´ısta? ˇ sen´ı. Reˇ 8! V3 (8) = 8 · 7 · 6 = = 336 5! (Variaˇcn´ı ˇc´ıslo lze n´azornˇe zd˚ uvodnit u ´vahou: kter´ekoli z 8 druˇzstev m˚ uˇze obsadit 1. m´ısto. V kaˇzd´em z tˇechto 8 pˇr´ıpad˚ u m˚ uˇze b´ yt na 2. m´ıstˇe kter´ekoli ze zb´ yvaj´ıc´ıch 7, na tˇret´ım pak v kaˇzd´em pˇr´ıpadˇe kter´ekoli ze zb´ yvaj´ıc´ıch ˇsesti.) 14
3 . pˇ r´ıklad. V naˇs´ı prvn´ı fotbalov´e lize bojuje o titul 16 muˇzstev. Kolik je r˚ uzn´ ych moˇznost´ı obsazen´ı prvn´ıch tˇr´ı ”medailov´ ych” m´ıst? ˇ sen´ı. V dan´e u Reˇ ´loze hled´ame zˇrejmˇe poˇcet vˇsech uspoˇr´adan´ ych trojic vyb´ıran´ ych z 16 prvk˚ u, jejich poˇcet je V3 (16) = 16 · 15 · 14 = 3360. 4 . pˇ r´ıklad. Ve ˇskole se uˇc´ı 10 r˚ uzn´ ym pˇredmˇet˚ um a kaˇzd´emu se uˇc´ı nejv´ yˇse jednu hodinu dennˇe. Kolika zp˚ usoby je moˇzno sestavit rozvrh hodin na jeden den, je-li toho dne pˇet r˚ uzn´ ych pˇredmˇet˚ u? ˇ sen´ı. Protoˇze jde o skupiny, v nichˇz z´aleˇz´ı na poˇrad´ı prvk˚ Reˇ u, kter´e se neopakuj´ı, jde o variace 5-tˇr´ıdy z 10 prvk˚ u (n = 10, k = 5). Jejich poˇcet je V5 (10) =
10 · 9 · 8 · 7 · 6 · 5! 10! = = 30 240 (10 − 5)! 5!
Rozvrh hodin na jeden den je tedy moˇzno z deseti pˇredmˇet˚ u sestavit 30 240 zp˚ usoby. 5 . pˇ r´ıklad. Kolik ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel s navz´ajem r˚ uzn´ ymi ciframi lze sestavit z cifer 0, 1, 2, 3, 4, 5?Kolik je mezi nimi sud´ ych ˇc´ısel? ˇ sen´ı. Oznaˇcme n1 poˇcet vˇsech ˇctyˇrcifern´ Reˇ ych pˇrirozen´ ych ˇc´ısel s navz´ajem r˚ uzn´ ymi ciframi, kter´a jsou sestavena z cifer 0, 1, . . . , 5, a n2 poˇcet vˇsech tˇechto ˇc´ısel, kter´a jsou nav´ıc sud´a. Pak plat´ı n1 = 5 · V3 (5) = 5 · 5 · 4 · 3 = 300, nebot’ poˇca´teˇcn´ı cifru dan´eho ˇc´ısla lze vybrat 5 zp˚ usoby z cifer 1, 2, . . . , 5, zbyl´e tˇri cifry pak vybereme V3 (5) zp˚ usoby. K urˇcen´ı ˇc´ısla n2 rozdˇelme vˇsechna sud´a ˇc´ısla do dvou skupin S1 , S2 ; ve skupinˇe S1 budou ta ˇc´ısla, kter´a konˇc´ı cifrou 0, tˇech je zˇrejmˇe V3 (5) = 5·4·3 = 60, ve skupinˇe S2 ta ˇc´ısla, kter´a konˇc´ı nˇekterou z cifer 2, 4. Takov´ ych ˇc´ısel je podle pravidla souˇcinu 4 · 4 · 3 · 2 = 96. Dohromady n2 = |S1 | + |S2 | = 60 + 96 = 156. 1. V´ ybor sportovn´ıho klubu tvoˇr´ı sedm muˇz˚ u a pˇet ˇzen. Urˇcete: (a) kolika zp˚ usoby z nich lze vybrat pˇredsedu, m´ıstopˇredsedu, jednatele a hospod´aˇre; [V4 (12) = 11 880] (b) kolika zp˚ usoby z nich lze vybrat funkcion´aˇre podle (a) tak, aby ve funkci pˇredsedy byl muˇz a ve funkci m´ıstopˇredsedy ˇzena nebo obr´acenˇe; [7 · 5 · 10 · 9 + 5 · 7 · 10 · 9 = 6 300] (c) kolika zp˚ usoby z nich lze vybrat funkcion´aˇre podle (a) tak, aby pr´avˇe jedn´ım z nich byla ˇzena. [5 · 7 · 6 · 5 + 7 · 5 · 6 · 5 + 7 · 6 · 5 · 5 + 7 · 6 · 5 · 5 = 4 200] 15
2. Urˇcete, kolika zp˚ usoby lze sestavit rozvrh na jeden den pro tˇr´ıdu, v n´ıˇz se vyuˇcuje dvan´acti pˇredmˇet˚ um a kaˇzd´emu nejv´ yˇse jednu vyuˇcovac´ı hodinu dennˇe, m´a-li se skl´adat ze ˇsesti vyuˇcovac´ıch hodin. V kolika z nich se vyskytuje dan´ y pˇredmˇet a v kolika z nich je tento pˇredmˇet zaˇrazen na 1. vyuˇcovac´ı hodinu? [V6 (12) = 665 280, s dan´ ym pˇredmˇetem 6 · V5 (11) = 332 640, s dan´ ym pˇredmˇetem v 1. hodinˇe V5 (11) = 55 440] 3. Urˇcete poˇcet prvk˚ u, z nichˇz lze utvoˇrit (a) 240 dvouˇclenn´ ych variac´ı; [16] (b) dvakr´at v´ıce ˇctyˇrˇclenn´ ych variac´ı neˇz tˇr´ıˇclenn´ ych variac´ı. [5] 4. O telefonn´ım ˇc´ısle sv´eho spoluˇz´aka si Pavel zapamatoval jen to, ˇze je dev´ıtim´ıstn´e, zaˇc´ın´a dvojˇc´ısl´ım 23, neobsahuje ˇz´adn´e dvˇe stejn´e ˇc´ıslice a je dˇeliteln´e pˇetadvaceti. Urˇcete, kolik telefonn´ıch ˇc´ısel pˇrich´az´ı v u ´vahu. [2 · V5 (6) = 1 440] 5. Kolika zp˚ usoby je moˇzno rozdˇelit 8 chlapc˚ u a 4 dˇevˇcata na dvˇe ˇsestiˇclenn´a volejbalov´a druˇzstva tak, aby v kaˇzd´em druˇzstvu bylo aspoˇ n jedno dˇevˇce? [ 85 · 41 + 12 · 42 · 84 ] 6. Roztrˇzit´ y pan profesor byl po zhl´ednut´ı utk´an´ı v h´azen´e dot´az´an doma na v´ ysledek. Odpovˇedˇel, ˇze utk´an´ı neskonˇcilo nerozhodnˇe a ˇze ˇz´adn´e z obou muˇzstev nevstˇrelilo v´ıce neˇz 20 a m´enˇe neˇz 10 branek. Urˇcete poˇcet moˇzn´ ych v´ ysledk˚ u. [V2 (11) = 110] 7. Zvˇetˇs´ı-li se poˇcet prvk˚ u o dva, zvˇetˇs´ı se poˇcet tˇr´ıˇclenn´ ych variac´ı (a) desetkr´at
(b) o 150
Urˇcete p˚ uvodn´ı poˇcet prvk˚ u. [(a)3, (b)5] 8. Urˇcete poˇcet vˇsech nejv´ yˇse ˇctyˇrcifern´ ych ˇc´ısel s r˚ uzn´ ymi ˇc´ıslicemi, kter´a jsou sestavena z ˇc´ıslic 0, 2, 4, 6, 8. [V1 (5) + [V2 (5) − V1 (4)] + [V3 (5) − V2 (4)] + [V4 (5) − V3 (4)] = 165] *9. Dokaˇzte, ˇze pro poˇcet k-ˇclenn´ ych variac´ı z n prvk˚ u plat´ı V (k, n) = nV (k − 1, n − 1).
16
Kapitola 3 Kombinace Definice. Kombinace k-t´ e tˇ r´ıdy z n prvk˚ u (bez opakov´an´ı), kde n ≥ k, jsou libovoln´e k-prvkov´e podmnoˇziny dan´e n-prvkov´e mnoˇziny. Na poˇrad´ı prvk˚ u v podmnoˇzinˇe (k-tici) nez´aleˇz´ı, ˇz´adn´ y se v n´ı neopakuje. Poˇcet kombinac´ı k-t´e tˇr´ıdy je proto menˇs´ı nebo roven neˇz poˇcet variac´ı k-t´e tˇr´ıdy z t´eˇze mnoˇziny: vˇzdy k! variac´ı liˇs´ıc´ıch se pouze poˇrad´ım vybran´ ych prvk˚ u pˇredstavuje tut´eˇz kombinaci. n! Vk (n) = Ck (n) = k! (n − k)! · k! toto ˇc´ıslo se naz´ yv´a kombinaˇcn´ı ˇc´ıslo (nebo tak´e binomick´ y koeficient) a oznaˇcuje se nk 1 . pˇ r´ıklad. Kolika zp˚ usoby lze vyplnit tiket Sportky pro 1 tah? ˇ sen´ı. Vyb´ır´ame ˇsestici z 49 r˚ Reˇ uzn´ ych ˇc´ısel (nez´aleˇz´ı na poˇrad´ı, v nˇemˇz je zaˇskrt´av´ame) 49 · 48 · 47 · 46 · 45 · 44 6 C6 (49) = = 2 6·5·4·3·2·1 2 . pˇ r´ıklad. Ve tˇr´ıdˇe je 18 chlapc˚ u a 14 d´ıvek. Kolika zp˚ usoby je moˇzno zvolit do tˇr´ıdn´ı samospr´avy 3 z´astupce, maj´ı-li to b´ yt a) sam´ı chlapci; b) sam´e d´ıvky; c) dva chlapci a jedna d´ıvka? ˇ sen´ı. a) Ponˇevadˇz nez´aleˇz´ı na poˇrad´ı, jde o kombinace tˇret´ı tˇr´ıdy (vol´ıme 3 z´astupce) Reˇ z 18 prvk˚ u (ve tˇr´ıdˇe je 18 chlapc˚ u): 18 18! C3 (18) = = = 816 15! · 3! 3 Do tˇr´ıdn´ı samospr´avy lze z 18 chlapc˚ u zvolit 3 z´astupce 816 zp˚ usoby. b) V tomto pˇr´ıpadˇe, kter´ y je obdobn´ y s a), n = 14, k = 3; 14 14! C3 (14) = = = 364 3 11! · 3! 17
Do tˇr´ıdn´ı samospr´avy lze ze 14 d´ıvek zvolit 3 d´ıvky 364 zp˚ usoby. c) Dva chlapci se z 18 chlapc˚ u mohou vybrat C2 (18) zp˚ usoby, jedna d´ıvka z 14 d´ıvek C1 (14) zp˚ usoby. Ale kaˇzd´ y z C2 (18) zp˚ usob˚ u lze spojit s kter´ ymkoli z C1 (14) zp˚ usob˚ u; jde tedy o n´asoben´ı kombinac´ı: 18 14 18! · 14 C2 (18) · C1 (14) = · = = 153 · 14 = 2 142. 2 1 16! · 2! Z 18 chlapc˚ u a 14 d´ıvek lze dva chlapce a jednu d´ıvku zvolit do tˇr´ıdn´ı samospr´avy 2 142 zp˚ usoby. 3 . pˇ r´ıklad. Je n u ´ˇcastn´ık˚ u telefonn´ı s´ıtˇe. Kolik existuje moˇznost´ı souˇcasn´eho spojen´ı tˇr´ı dvojic? ˇ sen´ı. Nejprve vybereme 6 u Reˇ ´ˇcastn´ık˚ u C6 (n) zp˚ usoby. Uspoˇr´ad´ame tyto u ´ˇcastn´ıky v libovoln´em poˇrad´ı a rozdˇel´ıme do dvojic (prvn´ı, druh´ y; tˇret´ı, ˇctvrt´ y; p´at´ y, ˇsest´ y). To lze ´ prov´est 6! zp˚ usoby. Uˇcastn´ıky m˚ uˇzeme uvnitˇr kaˇzd´e dvojice libovolnˇe pˇrestavovat, d´ale je nepodstatn´e poˇrad´ı dvojic; proto je celkov´ y poˇcet zp˚ usob˚ u potˇreba vydˇelit ˇc´ıslem 23 · 3!. n! zp˚ usob˚ u. Dost´av´ame 48(n−6)! 4 . pˇ r´ıklad. Rotu tvoˇr´ı 3 d˚ ustojn´ıci, 6 podd˚ ustojn´ık˚ u a 60 voj´ın˚ u. Kolika zp˚ usoby z nich lze vybrat odd´ıl, kter´ y tvoˇr´ı jeden d˚ ustojn´ık, dva podd˚ ustojn´ıci a 20 voj´ın˚ u? ˇ sen´ı. D˚ Reˇ ustojn´ıky lze vybrat C1 (3) zp˚ usoby, podd˚ ustojn´ıky C2 (6) zp˚ usoby a voj´ıny C20 (60) zp˚ usoby. Celkov´ y poˇcet zp˚ usob˚ u je tedy podle pravidla souˇcinu roven C1 (3) · C2 (6) · C20 (60). 1. Je d´an ˇctverec ABCD a na kaˇzd´e jeho stranˇe n (n ≥ 3) vnitˇrn´ıch bod˚ u. Urˇcete poˇcet vˇsech troj´ uheln´ık˚ u s vrcholy v tˇechto bodech. [ 2. Troj´ uheln´ıkov´e ˇc´ıslo je ˇc´ıslo an = neˇz 100.
n 2
4n 3
−4
n 3
]
; n ≥ 2. Vyhledejte troj´ uheln´ıkov´a ˇc´ısla menˇs´ı
[Troj´ uheln´ıkov´a ˇc´ısla menˇs´ı neˇz 100 jsou: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91.] 3. Orchestr m´a 10 ˇclen˚ u. Kolika zp˚ usoby lze z nˇeho v pr˚ ubˇehu 3 dn˚ u vyb´ırat vˇzdy po 6 ˇclenech tak, aby kaˇzd´ y den bylo jin´e sloˇzen´ı orchestru? [
18
10 6
·(
10 6
− 1) · (
10 6
− 2)]
4. Hern´ı syst´em hokejov´eho turnaje pro deset muˇzstev spoˇc´ıv´a v tom, ˇze v kaˇzd´e ze dvou skupin po pˇeti druˇzstvech sehraje kaˇzd´e s kaˇzd´ ym jeden z´apas; prvn´ı dvˇe muˇzstva z obou skupin postupuj´ı do fin´ale, kde opˇet kaˇzd´e s kaˇzd´ ym sehraje jeden z´apas, avˇsak s v´ yjimkou druˇzstev, kter´a jiˇz spolu hr´ala ve skupinˇe. Urˇcete celkov´ y poˇcet z´apas˚ u v turnaji. [2 · 52 + 42 − 2 = 24] 5. Marek m´a sedm knih, o kter´e se zaj´ım´a Veronika, Veronika m´a deset knih, o kter´e se zaj´ım´a Marek. Urˇcete, kolika zp˚ usoby si Marek m˚ uˇze vymˇenit dvˇe sv´e knihy za dvˇe knihy od Veroniky. [ 72 · 10 = 945] 2 6. Urˇcete, kolika zp˚ usoby je moˇzno ze dvaceti osob vybrat deset, poˇzadujeme-li, aby mezi vybran´ ymi (a) nebyl pan A; 19 10
]
−
18 8
]
+
18 8
]
[ (b) nebyli z´aroveˇ n p´anov´e A, B; [
20 10
(c) byl aspoˇ n jeden z p´an˚ u A, B. [2 ·
18 9
7. Urˇcete poˇcet prvk˚ u tak, aby (a) poˇcet ˇctyˇrˇclenn´ ych kombinac´ı z nich vytvoˇren´ ych byl dvacetkr´at vˇetˇs´ı neˇz poˇcet dvouˇclenn´ ych kombinac´ı; [18] (b) pˇri zvˇetˇsen´ı poˇctu prvk˚ u o jeden se poˇcet tˇr´ıˇclenn´ ych kombinac´ı zvˇetˇsil o 21. [7] *8. Vyj´adˇrete kombinaˇcn´ımi ˇc´ısly, kolika zp˚ usoby m˚ uˇze m chlapc˚ u a n d´ıvek utvoˇrit taneˇcn´ı p´ar. n m [ m+n − − ] 2 2 2 *9. Na ˇcern´a pol´ıˇcka ˇsachovnice 8 × 8 m´ame rozm´ıstit 12 b´ıl´ ych a 12 ˇcern´ ych pˇeˇsc˚ u. Urˇcete, kolika zp˚ usoby to lze prov´est. 20 [ 32 · 12 ] 12
19
´ Ulohy k opakov´ an´ı I 1. Kolik pˇeticifern´ ych ˇc´ısel je moˇzno sestavit z ˇc´ıslic 0, 1, 3, 4, 7? Kolik z nich je sud´ ych? [96, sud´ ych 42] 2. Kolik ˇsesticifern´ ych ˇc´ısel je moˇzno sestavit z cifer 1, 2, 3, 4, 5, 6, maj´ı-li ˇc´ısla (a) zaˇc´ınat cifrou 4; [120] (b) ciframi 4 nebo 5? [240] 3. Zmenˇs´ıme-li poˇcet prvk˚ u o dva, zmenˇs´ı se poˇcet permutac´ı dvacetkr´at. Urˇcete p˚ uvodn´ı poˇcet prvk˚ u. [5] 4. Zvˇetˇs´ı-li se poˇcet prvk˚ u o dva, zvˇetˇs´ı se poˇcet permutac´ı 42kr´at. Urˇcete p˚ uvodn´ı poˇcet prvk˚ u. [5] 5. Kolik nejv´ yˇse ˇctyˇrcifern´ ych ˇc´ısel je moˇzno sestavit z cifer 0, 2, 4, 6? [49] 6. Kolik r˚ uzn´ ych sign´al˚ u je moˇzno utvoˇrit z pˇeti prapork˚ u r˚ uzn´ ych barev, jsou-li (a) tˇri praporky postaveny vedle sebe; [60] (b) dva praporky postaveny vedle sebe; [20] 20
(c) v˚ ubec vˇsech sign´al˚ u? [325] 7. Kolika zp˚ usoby m˚ uˇze b´ yt odmˇenˇeno 1., 2., 3. cenou 13 u ´ˇcastn´ık˚ u sportovn´ı soutˇeˇze? [1 716] 8. Kolik prvk˚ u d´a 32 220 variac´ı druh´e tˇr´ıdy? [180] 9. Kolik m´ame d´ano prvk˚ u, jestliˇze variac´ı tˇret´ı tˇr´ıdy z nich utvoˇren´ ych je pˇetkr´at v´ıc neˇz variac´ı druh´e tˇr´ıdy? [7] 10. Kolika pˇr´ımkami m˚ uˇzeme spojit 10 bod˚ u, jestliˇze tˇri z nich leˇz´ı na jedn´e pˇr´ımce? [43] ˇ adn´e dalˇs´ı tˇri neleˇz´ı 11. Je d´ano 12 bod˚ u v rovinˇe, z nichˇz 5 leˇz´ı na jedn´e pˇr´ımce. Z´ na jedn´e pˇr´ımce. Kolik pˇr´ımek je tˇemito body urˇceno? [57] 12. V rovinˇe je 10 bod˚ u obecnˇe poloˇzen´ ych. (a) Kolik kruˇznic lze jimi urˇcit? [120] (b) Kolik kruˇznic je urˇceno, leˇz´ı-li 6 bod˚ u na jedn´e kruˇznici? [101] 13. Je d´ano 10 r˚ uzn´ ych bod˚ u v prostoru, z nichˇz ˇz´adn´e tˇri neleˇz´ı na jedn´e pˇr´ımce a ˇz´adn´e ˇctyˇri v jedn´e rovinˇe. (a) Kolik rovin lze jimi urˇcit? [120] (b) Kolik rovin lze jimi urˇcit, leˇz´ı-li 4 body v jedn´e rovinˇe? [117]
21
14. V prostoru je 12 bod˚ u obecnˇe poloˇzen´ ych. (a) Kolik ˇctyˇrstˇen˚ u lze z tˇechto bod˚ u jako vrchol˚ u vytvoˇrit? [495] (b) Kolik ˇctyˇrstˇen˚ u vytvoˇr´ıme, leˇz´ı-li 6 bod˚ u v jedn´e rovinˇe? [480] 15. V kolika bodech se prot´ın´a 9 pˇr´ımek, z nichˇz 4 jsou navz´ajem rovnobˇeˇzn´e? [30] 16. Zvˇetˇs´ı-li se poˇcet prvk˚ u o 1, zv´ yˇs´ı se poˇcet kombinac´ı tˇret´ı tˇr´ıdy o 21. Kolik je d´ano prvk˚ u? [7] 17. Ve tˇr´ıdˇe je 18 chlapc˚ u a 14 d´ıvek. Kolika zp˚ usoby se mohou zvolit do tˇr´ıdn´ı samospr´avy 3 z´astupci, maj´ı-li to b´ yt (a) sam´ı chlapci; [816] (b) sam´e d´ıvky; [364] (c) dva chlapci a jedna d´ıvka? [2 142] 18. Uˇcitel m´a 20 geometrick´ ych a 30 aritmetick´ ych pˇr´ıklad˚ u.Na u ´lohu m´a vybrat 1 geometrick´ y a 2 aritmetick´e. Kolik je moˇznost´ı r˚ uzn´ ych u ´loh? [8 700] 19. Na maturitn´ım veˇc´ırku je 24 chlapc˚ u a 15 d´ıvek. Kolik r˚ uzn´ ych p´ar˚ u mohou vytvoˇrit? [360] 20. Kolik je tˇreba vz´ıt prvk˚ u, aby z nich bylo moˇzno utvoˇrit 1 444 kombinac´ı 3. tˇr´ıdy, kter´e obsahuj´ı aspoˇ n jeden ze dvou pevnˇe zvolen´ ych prvk˚ u? [40]
22
21. Kolik je tˇreba vz´ıt prvk˚ u, aby poˇcet variac´ı 2. tˇr´ıdy z nich utvoˇren´ ych k poˇctu variac´ı 3. tˇr´ıdy bez opakov´an´ı byl v pomˇeru 1 : 20? [x = 22] 22. Kolik je tˇreba vz´ıt prvk˚ u, aby poˇcet variac´ı 3. tˇr´ıdy z nich utvoˇren´ y bez opakov´an´ı byl pr´avˇe tak velk´ y jako poˇcet kombinac´ı 3. tˇr´ıdy zvˇetˇsen´ y o pˇetin´asobn´ y poˇcet prvk˚ u? [x = 4] 23. Kolik je tˇreba vz´ıt prvk˚ u, aby se sedmin´asobn´ y poˇcet kombinac´ı 2. tˇr´ıdy rovnal poˇctu kombinac´ı 3. tˇr´ıdy?
3 2
[x = 16] 24. Urˇcete, kolika zp˚ usoby je moˇzno seˇradit u startovac´ı ˇc´ary osm z´avodn´ıch automobil˚ u do dvou ˇrad po ˇctyˇrech vozech, jestliˇze (a) v kaˇzd´e ˇradˇe z´aleˇz´ı na poˇrad´ı; [
8 4
4!4!]
(b) na poˇrad´ı v ˇrad´ach nez´aleˇz´ı. [
8 4
]
25. Urˇcete, kolika zp˚ usoby lze na ˇsachovnici 8 × 8 postavit pˇet r˚ uzn´ ych figur tak, aby dvˇe st´aly na ˇcern´ ych a tˇri na b´ıl´ ych pol´ıch. [
32 2
32 3
· 5!]
26. Urˇcete, kolika zp˚ usoby lze pˇrem´ıstit p´ısmena slova BEROUNKA tak, aby nˇejak´a skupina po sobˇe jdouc´ıch p´ısmen utvoˇrila (a) slovo BERAN; [4!] (b) slova NERO, KUBA v libovoln´em poˇrad´ı; [2] (c) slova BUK, NORA v libovoln´em poˇrad´ı. [3!]
23
27. Na maturitn´ım veˇc´ırku je 15 hoch˚ u a 12 dˇevˇcat. Urˇcete, kolika zp˚ usoby z nich lze vybrat ˇctyˇri taneˇcn´ı p´ary. [
12 4
15 4
· V4 (15) =
· V4 (12)]
28. V kart´ezsk´e souˇradnicov´e soustavˇe jsou d´any pˇr´ımky: x = 1, x = 2, x = 3, x = 4, x = 5, y = 2, y = 4, y = 6, y = 8. Urˇcete, kolik je v takto vznikl´e s´ıti rovnobˇeˇzn´ık˚ u. N´ avod: kaˇzd´ y rovnobˇeˇzn´ık je urˇcen dvˇema dvojicemi rovnobˇeˇzek. [
5 2
4 2
]
29. Urˇcete, v kolika bodech se prot´ın´a 12 pˇr´ımek v rovinˇe, z nichˇz 5 je rovnobˇeˇzn´ ych a ˇz´adn´e tˇri neproch´azej´ı t´ ymˇz bodem. 12 2
[
−
5 2
]
30. Je d´an rovnostrann´ y troj´ uheln´ık a na kaˇzd´e jeho stranˇe je d´ano n (n ≥ 3) vnitˇrn´ıch bod˚ u. Urˇcete poˇcet vˇsech troj´ uheln´ık˚ u (a) s vrcholy v dan´ ych bodech; [
3n 3
−3
n 3
]
(b) s vrcholy v dan´ ych bodech a na r˚ uzn´ ych stran´ach dan´eho troj´ uheln´ıku. [n3 ] 31. Urˇcete poˇcet vˇsech pˇrirozen´ ych ˇc´ısel menˇs´ıch neˇz 500, v jejichˇz dekadick´em z´apisu jsou pouze cifry 3, 5, 7, 9, kaˇzd´a nejv´ yˇse jednou. [V1 (4) + V2 (4) + V2 (3) = 22] 32. Urˇcete, kolika zp˚ usoby se kolem kulat´eho stolu m˚ uˇze posadit pˇet muˇz˚ u a pˇet ˇzen tak, aby ˇz´adn´e dvˇe ˇzeny nesedˇely vedle sebe. N´avod: Oˇc´ıslujeme-li jednotliv´a m´ısta, mohou muˇzi sedˇet bud’ na m´ıstech 1, 3, 5, 7, 9, nebo na m´ıstech 2, 4, 6, 8, 10. [2 · 5!5! = 28 800] 33. V prostoru je d´ano n bod˚ u, z nichˇz p leˇz´ı v t´eˇze rovinˇe, a kromˇe nich uˇz ˇz´adn´e ˇctyˇri body v jedn´e rovinˇe neleˇz´ı. Urˇcete: (a) poˇcet ˇctyˇrstˇen˚ u s vrcholy v dan´ ych bodech; [ 24
n 4
−
p 4
]
(b) poˇcet rovin, kter´e tyto body urˇcuj´ı. [
n 3
−
p 3
+ 1]
34. V kup´e ˇzelezniˇcn´ıho vag´onu jsou proti sobˇe dvˇe lavice po pˇeti m´ıstech. Z deseti cestuj´ıc´ıch si ˇctyˇri pˇrej´ı sedˇet ve smˇeru j´ızdy, tˇri proti smˇeru a zb´ yvaj´ıc´ım tˇrem to je lhostejn´e. Urˇcete, kolika zp˚ usoby se mohou rozsadit. [3 · 5!5! = 43 200] 35. Kolika zp˚ usoby lze ze 7 muˇz˚ u a 4 ˇzen vybrat ˇsestiˇclennou skupinu tak, aby v n´ı byly (a) pr´avˇe dvˇe ˇzeny; [
4 2
·
7 4
]
4 4
·
7 2
]
(b) aspoˇ n dvˇe ˇzeny? [
4 2
·
7 4
+
4 3
·
7 3
+
36. Urˇcete poˇcet vˇsech ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel s r˚ uzn´ ymi ˇc´ıslicemi, jejichˇz dekadick´ y z´apis je utvoˇren z ˇc´ıslic 0, 1, 2, 3, 5, 7. Kolik tˇechto ˇc´ısel konˇc´ı jedniˇckou? Kolik tˇechto ˇc´ısel je lich´ ych? [V4 (6) − V3 (5) = 300; jedniˇckou konˇc´ı V3 (5) − V2 (4) = 48 ˇc´ısel, lich´ ych je 4 · 48 = 192]
25
Kapitola 4 Permutace s opakov´ an´ım Definice. Permutace s opakov´ an´ım z n prvk˚ u je uspoˇr´adan´a k-tice sestaven´a z tˇechto prvk˚ u tak, ˇze kaˇzd´ y se v n´ı vyskytuje aspoˇ n jednou. Poˇcet permutac´ı s opakov´an´ım z n prvk˚ u, v nichˇz se jednotliv´e prvky opakuj´ı k1 , k2 , . . . , kn -kr´at je: P 0 (k1 , k2 , . . . , kn ) =
(k1 + k2 + . . . + kn )! k1 ! · k2 ! · . . . · kn !
1 . pˇ r´ıklad. Spoleˇcnost 10 manˇzelsk´ ych dvojic se chyst´a na proj´ıˇzd’ku lod’kami, a proto se rozdˇeluje na 5 skupin po ˇctyˇrech. Kolika zp˚ usoby se mohou rozdˇelit tak, aby v kaˇzd´e skupinˇe byli dva muˇzi a dvˇe ˇzeny? ˇ sen´ı. Muˇze lze rozdˇelit na dvojice 10!5 zp˚ Reˇ usoby (pˇrihl´ıˇz´ıme-li i k permutac´ım uvnitˇr (2!) ·5! 10! ˇ dvojic a permutac´ım samotn´ ych dvojic). Zeny lze rozdˇelit (2!) usoby (zde uˇz je d˚ uleˇzit´e 5 zp˚ poˇrad´ı dvojic). Celkem existuje
(10!)2 21 0·5!
zp˚ usob˚ u.
2 . pˇ r´ıklad. Kolika zp˚ usoby lze rozestavit v prvn´ı ˇradˇe ˇsachovnice tyto b´ıl´e figury: 2 konˇe, 2 stˇrelce, 2 vˇeˇze, 1 kr´ale a 1 d´amu? ˇ sen´ı. Zˇrejmˇe jde o urˇcen´ı poˇctu vˇsech permutac´ı 2 prvk˚ Reˇ u 1. druhu (koˇ n˚ u), 2 prvk˚ u 2. druhu (stˇrelc˚ u), 2 prvk˚ u 3. druhu (vˇeˇz´ı), 1 prvku 4. druhu (kr´ale) a 1 prvku 5. druhu (d´amy). Tedy podle vztahu pro v´ ypoˇcet poˇctu permutac´ı s opakov´an´ım plat´ı: P 0 (2, 2, 2, 1, 1) =
8! = 5 040 2!2!2!1!1!
3 . pˇ r´ıklad. Kolik anagram˚ u lze vytvoˇrit z p´ısmen slova MATEMATIKA? ˇ sen´ı. Kaˇzd´ Reˇ y anagram je zˇrejmˇe d´an nˇejakou permutac´ı 3 p´ısmen A, 2 p´ısmen M, 2 p´ısmen T, 1 p´ısmene E, 1 p´ısmene I a 1 p´ısmene K. Proto je hledan´ y poˇcet anagram˚ u roven 10! P 0 (3, 2, 2, 1, 1, 1) = = 151 200 3!(2!)2 (1!)3 26
1. Jistˇe jste poznali, ˇze v anagramech AABIIKKMNOORT resp. MINIKABAROTOK je zaˇsifrov´ano slovo KOMBINATORIKA. Urˇcete poˇcet vˇsech anagram˚ u, jeˇz lze ze slova KOMBINATORIKA utvoˇrit. 13! [ 2!2!2!2! ]
2. Urˇcete, kolik r˚ uzn´ ych slov lze z´ıskat pˇrem´ıstˇen´ım p´ısmen slova ABRAKADABRA. Urˇcete, v kolika z nich: [83 160] (a) ˇz´adn´a dvojice sousedn´ıch p´ısmen nen´ı tvoˇrena dvˇema p´ısmeny A; [3 780] (b) ˇz´adn´a pˇetice sousedn´ıch p´ısmen nen´ı tvoˇrena pˇeti p´ısmeny A. [81 900]] ˇ ıma po v´ıtˇezstv´ı nad pontsk´ 3. Pozn´ate zpr´avu Gaia Iulia Caesara zaslanou do R´ ym kr´alem Frankem, kter´a se skr´ yv´a v anagramu CDEIIIIINVVV? Kolika zp˚ usoby lze v n´ı pˇrem´ıstit p´ısmena? [Veni, vidi, vici (pˇriˇsel jsem, vidˇel jsem, zv´ıtˇezil jsem),
12! ] 3!5!
4. Urˇcete, kolika zp˚ usoby je moˇzno pˇrem´ıstit p´ısmena slova BATERKA tak, aby se souhl´asky a samohl´asky stˇr´ıdaly. N´ avod: Na zaˇc´atku i na konci mus´ım b´ yt souhl´aska. 3! ] [4! · 2!
5. Urˇcete poˇcet zp˚ usob˚ u, jimiˇz lze um´ıstit vˇsechny b´ıl´e ˇsachov´e figurky (kr´al, d´ama, 2 vˇeˇze, 2 jezdci, 2 stˇrelci, 8 pˇeˇs´ak˚ u) (a) na dvˇe pevnˇe zvolen´e ˇrady ˇsachovnice 8 × 8; 16! [ 8!2!2!2! ]
(b) na libovoln´e dvˇe ˇrady ˇsachovnice 8 × 8. [
8 16! ] 2 8!2!2!2!
6. Urˇcete poˇcet vˇsech pˇeticifern´ ych pˇrirozen´ ych ˇc´ısel, jeˇz lze sestavit z ˇc´ıslic 5 a 7, m´a-li v kaˇzd´em z nich b´ yt ˇc´ıslice 5 (a) pr´avˇe tˇrikr´at; 5! [ 3!2! = 10]
27
(b) nejv´ yˇse tˇrikr´at; 5! 4!
[1 +
+
5! 3!2!
5! 2!3!
+
= 26]
(c) aspoˇ n tˇrikr´at. 5! [ 3!2! +
5! 4!
+ 1 = 16]
7. Urˇcete poˇcet vˇsech ˇctyˇrcifern´ ych ˇc´ısel dˇeliteln´ ych dev´ıti, v jejichˇz dekadick´em z´apisu nejsou jin´e ˇc´ıslice neˇz 0, 1, 2, 5, 7. [54] 8. Urˇcete, kolik ˇctyˇrcifern´ ych ˇc´ısel lze sestavit z ˇc´ıslic ˇc´ısla 238 832.(V tˇechto ˇc´ıslech se kaˇzd´a ˇc´ıslice vyskytuje nejv´ yˇse tolikr´at, kolikr´at je v ˇc´ısle 238 832.) [3 ·
4! 2!
+3·
4! 2!2!
= 54]
9. Urˇcete poˇcet vˇsech deseticifern´ ych pˇrirozen´ ych ˇc´ısel, jejichˇz cifern´ y souˇcet je roven tˇrem. Kolik z nich je sud´ ych? [1 +
10! 8!
−
9! 7!
+
10! 3!7!
−
9! 3!6!
= 55; sud´ ych je 1 +
9! 8!
+
8! 6!2!
+
8! 7!
= 46]
10. Ze sedmi kuliˇcek, z nichˇz jsou ˇctyˇri modr´e (navz´ajem nerozliˇsiteln´e), jedna b´ıl´a, jedna ˇcerven´a a jedna zelen´a, m´ame vybrat a poloˇzit do ˇrady vedle sebe pˇet kuliˇcek. Kolika zp˚ usoby to lze prov´est? [3 ·
28
5! 4!
+3·
5! 3!
+
5! 2!
= 135]
Kapitola 5 Variace s opakov´ an´ım Definice. Variace k -t´ e tˇ r´ıdy z n prvk˚ u s opakov´ an´ım,kde n ≥ 1, jsou uspoˇr´adan´e k-tice tvoˇren´e z prvk˚ u dan´e n-prvkov´e mnoˇziny, pˇriˇcemˇz se kter´ ykoli prvek m˚ uˇze v k-tici libovolnˇe opakovat. Poˇcet variac´ı s opakov´an´ım Vk0 (n) = nk ˇ ri studenti jist´e vysok´e ˇskoly skl´adaj´ı zkouˇsku z matematiky. Kolik existuje 1 . pˇ r´ıklad. Ctyˇ zp˚ usob˚ u v´ ysledk˚ u pro tuto ˇctveˇrici? Poˇc´ıtejte s ˇctyˇrstupˇ novou klasifikac´ı. ˇ sen´ı. Kaˇzd´ Reˇ y student m˚ uˇze z´ıskat jednu ze 4 zn´amek, a proto existuje 44 , tj. 256 zp˚ usob˚ u hodnocen´ı. 2 . pˇ r´ıklad. Kolik r˚ uzn´ ych vrh˚ u m˚ uˇze nastat, h´az´ıme-li souˇcasnˇe dvˇema hrac´ımi kostkami? ˇ sen´ı. Na kaˇzd´e kostce je 6 ˇc´ısel, prvk˚ Reˇ u je tedy n = 6. Pˇri kaˇzd´em vrhu se utvoˇr´ı skupina o dvou prvc´ıch, tedy k = 2. Protoˇze se prvky ve skupinˇe mohou opakovat, jde o variace s opakov´an´ım. Dostaneme V20 (6) = 62 = 36. 3 . pˇ r´ıklad. Uvaˇzujme vˇsechna cel´a nez´aporn´a ˇc´ısla menˇs´ı neˇz 106 Urˇcete, kter´ ych ˇc´ısel je v´ıc: tˇech, kter´a ve sv´em z´apisu neobsahuj´ı ˇz´adnou cifru 9, nebo tˇech, v jejichˇz z´apise je aspoˇ n jednou cifra 9 pouˇzita? ˇ sen´ı. Oznaˇcme n1 poˇcet tˇech ˇc´ısel menˇs´ıch neˇz 106 , kter´a lze zapsat bez uˇzit´ı cifry Reˇ 9, n2 poˇcet takov´ ych ˇc´ısel, k jejichˇz z´apisu aspoˇ n jednou cifru 9 uˇzijeme; zˇrejmˇe plat´ı n1 + n2 = 106 . Snaˇzˇs´ı bude nejprve urˇcit ˇc´ıslo n1 : dopln´ıme-li m´enˇecifern´a ˇc´ısla pˇr´ısluˇsn´ ym poˇctem nul, je n1 rovno poˇctu ˇsesticifern´ ych z´apis˚ u, v nichˇz jsou uˇzity nˇekter´e z 9 cifer 0, 1, . . . , 8, v nichˇz z´aleˇz´ı na poˇrad´ı a kde se cifry mohou opakovat. Proto podle pravidla souˇcinu je n1 = 96 = 531 441 > 106 − 96 = n2 . 4 . pˇ r´ıklad. Kolika zp˚ usoby lze z u ´pln´eho souboru tzv. francouzsk´ ych karet, s nimiˇz se hraje bridˇz (52 karet jeˇz se dˇel´ı na 4 skupiny podle ”barev”), vybrat po jedn´e kartˇe kaˇzd´e barvy? Kolik je tˇechto v´ ybˇer˚ u, je-li nav´ıc poˇzadov´ano, aby mezi vybran´ ymi kartami nebyly ˇz´adn´e dvˇe stejn´eho ”typu”, tj. dvˇe esa, dvˇe des´ıtky atd.? 29
ˇ sen´ı. Dost´av´ame 4-variace s opakov´an´ım z 13 karet. Celkem je 134 , tj. 28 561 zp˚ Reˇ usob˚ u. Nemaj´ı-li se vyskytovat karty t´ehoˇz typu, jde o variace bez opakov´an´ı: V4 (13) = 17 160. 1. Urˇcete, kolik znaˇcek Morseovy abecedy lze utvoˇrit sestaven´ım teˇcek a ˇc´arek do skupin o jednom aˇz ˇctyˇrech prvc´ıch. [V10 (2) + V20 (2) + V30 (2) + V40 (2) = 30] 2. Urˇcete poˇcet vˇsech ˇctyˇrcifern´ ych ˇc´ısel dˇeliteln´ ych ˇctyˇrmi, v nichˇz se vyskytuj´ı pouze cifry 1, 2, 3, 4, 5. [5 · V20 (5) = 125] 3. Urˇcete poˇcet vˇsech pˇrirozen´ ych ˇc´ısel menˇs´ıch neˇz mili´on, kter´a lze zapsat(dekadicky) pouze pouˇzit´ım ˇc´ıslic 5, 8. [V60 (2) + V50 (2) + V40 (2) + V30 (2) + V20 (2) + V10 (2) = 126] 4. Urˇcete, kolika zp˚ usoby lze k r˚ uzn´ ych prvk˚ u rozm´ıstit do r pˇrihr´adek. [Vk0 (r) = rk ] 5. Jm´eno a pˇr´ıjmen´ı kaˇzd´eho obyvatele mˇesteˇcka s 1 500 obyvateli m˚ uˇze zaˇc´ınat jedn´ım ze 32 p´ısmen. Dokaˇzte, ˇze aspoˇ n dva obyvatel´e mˇesteˇcka maj´ı stejn´e inici´aly. [Poˇcet moˇzn´ ych inici´al je V20 (32) = 1 024] 6. Kufˇr´ık m´a heslov´ y z´amek, kter´ y se otevˇre, kdyˇz na kaˇzd´em z pˇeti kotouˇc˚ u nastav´ıme spr´avnou ˇc´ıslici; tˇechto ˇc´ıslic je na kaˇzd´em kotouˇci devˇet. Urˇcete nejvˇetˇs´ı moˇzn´ y poˇcet pokus˚ u, kter´e je nutno prov´est, chceme-li kufˇr´ık otevˇr´ıt, jestliˇze jsme zapomnˇeli heslo. [V50 (9) = 95 = 59 049] 7. Kolika zp˚ usoby lze zvolit pˇetip´ısmenn´e heslo trezoru, m˚ uˇze-li b´ yt na kter´ekoli m´ıstˇe libovoln´e p´ısmeno abecedy (z 26 p´ısmen) [V50 (26) = 265 ] 8. Na panelu je k ˇz´arovek, z nichˇz kaˇzd´a m˚ uˇze sv´ıtit zelenˇe, ˇzlutˇe nebo ˇcervenˇe. Urˇcete, kolik r˚ uzn´ ych stav˚ u m˚ uˇze panel signalizovat. [3k ] 30
9. Kr´al Artuˇs pos´ıl´a 6 spˇeˇsn´ ych zpr´av sv´ ym ryt´ıˇr˚ um. Kaˇzd´ y ze tˇr´ı pˇripraven´ ych posl˚ u m˚ uˇze doruˇcit libovolnou ze zpr´av. Kolika zp˚ usoby m˚ uˇze kr´al Artuˇs rozdˇelit dopisy mezi kur´ yry? [36 ] *10. Urˇcete poˇcet vˇsech ˇsesticifern´ ych pˇrirozen´ ych ˇc´ısel, jejichˇz cifern´ y souˇcet je ˇc´ıslo sud´e. N´ avod: Prvn´ıch pˇet ˇc´ıslic je libovoln´ ych (jen na 1. m´ıstˇe nesm´ı b´ yt nula) a pro ˇsest´e je pˇet moˇznost´ı. [9 · 104 · 5 = 450 000]
31
Kapitola 6 Kombinace s opakov´ an´ım Definice. k-ˇclenn´a kombinace s opakov´an´ım z n prvk˚ u, kde n ≥ 1, je neuspoˇr´adan´a k-tice sestaven´a z tˇechto prvk˚ u tak, ˇze kaˇzd´ y se v n´ı vyskytuje nejv´ yˇse k-kr´at. Poˇcet K 0 (k, n) vˇsech k-ˇclenn´ ych kombinac´ı s opakov´an´ım z n prvk˚ u je n+k−1 0 K (k, n) = k 1 . pˇ r´ıklad. V s´aˇcku jsou ˇcerven´e, modr´e a zelen´e kuliˇcky; kuliˇcky t´eˇze barvy jsou nerozliˇsiteln´e. Urˇcete, kolika zp˚ usoby lze vybrat 5 kuliˇcek, jestliˇze v s´aˇcku je a) aspoˇ n pˇet kuliˇcek od kaˇzd´e barvy; b) pˇet ˇcerven´ ych, ˇctyˇri modr´e a ˇctyˇri zelen´e. ˇ sen´ı. V pˇetici kuliˇcek, kter´e vyb´ır´ame, nez´aleˇz´ı na poˇrad´ı a barvy kuliˇcek se v n´ı mohou Reˇ opakovat. Jde tedy o pˇetiˇclenn´e kombinace s opakov´an´ım ze tˇr´ı prvk˚ u. a) V tomto pˇr´ıpadˇe je moˇzno utvoˇrit vˇsechny moˇzn´e pˇetice ze tˇr´ı barev, nebot’ kuliˇcek od kaˇzd´e barvy je dostateˇcn´e mnoˇzstv´ı, tj. pˇet. Poˇcet zp˚ usob˚ u v´ ybˇeru je tedy K 0 (5, 3) = 7 = 21. 5 b) V tomto pˇr´ıpadˇe nelze vybrat pˇet modr´ ych ani pˇet zelen´ ych kuliˇcek; protoˇze vˇsak vˇsechny ostatn´ı v´ ybˇery uskuteˇcnit lze, je poˇcet zp˚ usob˚ u v´ ybˇeru K 0 (5, 3) − 2 = 19. 2 . pˇ r´ıklad. Mezi 6 dˇet´ı rozdˇelujeme 15 (stejn´ ych) tenisov´ ych m´ıˇck˚ u. a) Urˇcete poˇcet n1 vˇsech moˇzn´ ych rozdˇelen´ı. b) Urˇcete poˇcet n2 vˇsech rozdˇelen´ı, pˇri kter´ ych kaˇzd´e d´ıtˇe dostane aspoˇ n jeden m´ıˇcek. ˇ sen´ı. Povaˇzujeme-li vˇsechny m´ıˇcky za nerozliˇsiteln´e, budeme pokl´adat za r˚ Reˇ uzn´a takov´a dvˇe rozdˇelen´ı, pˇri nichˇz nˇekter´e d´ıtˇe dostane r˚ uzn´ y poˇcet m´ıˇck˚ u. Kaˇzd´e rozdˇelen´ı zaˇsifrujeme pomoc´ı posloupnosti jedniˇcek a nul tak, ˇze nap´ıˇseme tolik jedniˇcek, kolik m´ıˇck˚ u d´ame 1. d´ıtˇeti, oddˇel´ıme nulou, zap´ıˇseme tolik jedniˇcek, kolik m´ıˇck˚ u obdrˇz´ı 2. d´ıtˇe atd. – t´ım vytvoˇr´ıme uspoˇr´adanou 20-tici sloˇzenou z 15 jedniˇcek a 5 nul; takov´ ychto posloupnost´ı 20 0 0 existuje P (15, 5), tzn. n1 = P (15, 5) = 5 . Pro urˇcen´ı poˇctu n2 ”spravedlivˇejˇs´ıch” rozdˇelen´ı – tedy takov´ ych rozdˇelen´ı, kdy ˇz´adn´e d´ıtˇe nevyjde u ´plnˇe napr´azdno – pouˇzijeme 32
tento obrat: rozd´ame nejprve kaˇzd´emu d´ıtˇeti po jednom m´ıˇcku, zbyl´ ych 9 pak uˇz lze mezi dˇeti rozdˇelovat bez omezen´ı; snadnou u ´vahou z ˇ c a ´ sti a) tedy zjist´ ıme, ˇze to lze prov´est 14 0 0 P (9, 5) zp˚ usoby. Je tedy n2 = P (9, 5) = 5 . 3 . pˇ r´ıklad. Kolika zp˚ usoby si mohou tˇri osoby rozdˇelit 7 stejn´ ych hruˇsek a 5 stejn´ ych jablek, aniˇz by je kr´ajely? ˇ sen´ı. Nalezneme nejprve poˇcet vˇsech rozdˇelen´ı hruˇsek mezi 3 osoby; stejnˇe jako Reˇ 9 0 v pˇredchoz´ım pˇr´ıpadˇe zjist´ ıme, ˇ z e jich je P (7, 2) = . Podobnˇe lze jablka mezi tyto 2 7 0 osoby rozdˇ u ovoce elit7P (5, 2) = 2 . Podle pravidla souˇcinu je moˇzn´e rozdˇelen´ı obou druh˚ 9 prov´est 2 · 2 = 756 zp˚ usoby. 1. Urˇcete poˇcet kv´adr˚ u, jejichˇz velikosti hran jsou pˇrirozen´a ˇc´ısla nejv´ yˇse rovn´a deseti. Kolik je v tomto poˇctu krychl´ı? [K 0 (3, 10) =
12 3
, krychl´ı je 10]
2. V novinov´em st´anku je ke koupi deset druh˚ u pohled˚ u, pˇriˇcemˇz kaˇzd´ y druh je k dispozici v pades´ati exempl´aˇr´ıch. Urˇcete, kolika zp˚ usoby lze zakoupit (a) 15 pohled˚ u; [K 0 (15, 10) =
24 15
]
(b) 51 pohled˚ u; [K 0 (51, 10) − 10] (c) 8 r˚ uzn´ ych pohled˚ u. [K(8, 10) =
10 8
= 45]
3. Urˇcete poˇcet vˇsech troj´ uheln´ık˚ u, z nichˇz ˇz´adn´e dva nejsou shodn´e a jejichˇz kaˇzd´a strana m´a velikost vyj´adˇrenou jedn´ım z ˇc´ısel 4, 5, 6, 7. [K 0 (3, 4) =
6 3
= 20]
4. Ze vˇsech b´ıl´ ych ˇsachov´ ych figurek bez kr´ale a d´amy vybereme (a) trojici, [K 0 (3, 4) − 3 = 17] (b) dvojici. [K 0 (2, 4) =
33
5 2
= 10]
5. V sadˇe 32 karet je kaˇzd´a z n´asleduj´ıc´ıch karet ˇctyˇrikr´at: sedmiˇcka, osmiˇcka, dev´ıtka, des´ıtka, spodek, svrˇsek, kr´al a eso. Karty t´eˇze hodnoty jsou pˇritom rozliˇseny tˇemito ”barvami” ˇcerven´a, zelen´a, ˇzaludy, kule. Urˇcete, kolika zp˚ usoby je moˇzno vybrat ˇctyˇri karty, jestliˇze se (a) rozliˇsuj´ı pouze ”barvy” jednotliv´ ych karet; [K 0 (4, 4) =
7 4
]
11 4
]
(b) rozliˇsuj´ı pouze hodnoty jednotliv´ ych karet. [K 0 (4, 8) =
6. Apolloniovou u ´lohou se rozum´ı u ´loha sestrojit kruˇznici, kter´a m´a tˇri z tˇechto vlastnost´ı: proch´az´ı dan´ ym bodem, dot´ yk´a se dan´e pˇr´ımky, dot´ yk´a se dan´e kruˇznice. (Oznaˇc´ıme-li tyto vlastnosti po ˇradˇe p´ısmeny B, p, k m˚ uˇzeme kaˇzdou Apolloniovu u ´lohu zapsat pomoc´ı trojice z tˇechto p´ısmen; tak napˇr. u ´loha Bkk znaˇc´ı u ´lohu sestrojit kruˇznici proch´azej´ıc´ı dan´ ym bodem a dot´ ykaj´ıc´ı se dvou dan´ ych kruˇznic.) Urˇcete poˇcet vˇsech Apolloniov´ ych u ´loh. [K 0 (3, 3) =
5 3
= 10]
7. Kolik r˚ uzn´ ych neuspoˇr´adan´ ych trojic mohou d´at poˇcty ok na jednotliv´ ych kostk´ach pˇri vrhu tˇremi kostkami? (Jde o obvyklou kostku s jedn´ım aˇz ˇsesti oky na jednotliv´ ych stˇen´ach.) [K 0 (3, 6) =
8 3
= 56]
8. Klenotn´ık vyb´ır´a do prstenu tˇri drahokamy; k dispozici m´a tˇri rub´ıny, dva smaragdy a pˇet saf´ır˚ u. Kolika zp˚ usoby m˚ uˇze tento v´ ybˇer prov´est, povaˇzujeme-li kameny t´ehoˇz druhu za stejn´e? [K 0 (3, 3) − 1 =
5 3
− 1 = 9]
9. Urˇcete poˇcet vˇsech neuspoˇr´adan´ ych trojic vrh˚ u 3 kostkami. [
6+3−1 3
=
8 3
= 56]
*10. Urˇcete poˇcet vˇsech poˇrad´ı m jedniˇcek a n nul, v nichˇz ˇz´adn´e dvˇe jedniˇcky nestoj´ı vedle sebe. [
34
n+1 m
]
´ Ulohy k opakov´ an´ı II 1. Do v´ ytahu vstoupilo 6 osob, d˚ um m´a 8 pater; kolika zp˚ usoby mohou cestuj´ıc´ı vystupovat (a) celkovˇe; [86 ] (b) vystupuje-li v kaˇzd´em patˇre nejv´ yˇse jeden. [8 · 7 · 6 · 5 · 4 · 3 = 20 160] 2. Urˇcete, kolika zp˚ usoby lze pˇrem´ıstit p´ısmena slova Mississippi; kolik z nich nezaˇc´ın´a p´ısmenem M? 11! , p´ısmenem M jich nezaˇc´ın´a [ 4!2!2!
11! 4!2!2!
−
10! 4!2!2!
=
10!10 ] 4!2!2!
3. V samoobsluze maj´ı ˇctyˇri druhy k´avy, kaˇzd´ y po pades´ati gramech. Urˇcete, kolika zp˚ usoby lze koupit 250 gram˚ u k´avy, jestliˇze (a) bal´ıˇck˚ u kaˇzd´eho druhu maj´ı dostateˇcn´ y poˇcet; [K 0 (5, 4) =
8 5
]
(b) od dvou druh˚ u maj´ı deset bal´ıˇck˚ u a od zb´ yvaj´ıc´ıch dvou pouze po ˇctyˇrech bal´ıˇcc´ıch. [K 0 (5, 4) − 2] 4. Urˇcete poˇcet zp˚ usob˚ u, jak lze vˇsechny b´ıl´e ˇsachov´e figurky (a) rozdˇelit na 2 pevnˇe zvolen´e ˇrady; 16! [ 8!2!2!2! ]
(b) rozdˇelit na 2 libovoln´e ˇrady. [
35
8 2
·
16! ] 8!2!2!2!
5. Pro kolik prvk˚ u je poˇcet variac´ı 3. tˇr´ıdy bez opakov´an´ı k poˇctu variac´ı t´eˇze tˇr´ıdy s opakov´an´ım v pomˇeru 21 : 32? [8] 6. Urˇcete, kolika zp˚ usoby si mohou tˇri osoby rozdˇelit ˇctyˇri stejn´a jablka a ˇsest stejn´ ych hruˇsek. N´ avod: Rozdˇelen´ı jablek a hruˇsek jsou na sobˇe nez´avisl´a, d´ale pak viz pˇredchoz´ı pˇr´ıklad. [K 0 (4, 3) · K 0 (6, 3) =
6 4
·
8 6
= 420]
7. Urˇcete poˇcet vˇsech troj´ uheln´ık˚ u, z nichˇz ˇz´adn´e dva nejsou shodn´e a jejichˇz kaˇzd´a strana m´a jednu z velikost´ı dan´ ych ˇc´ısly 4, 5, 6, 7, 8, 9. [K 0 (3, 6) − 3 = 53] 8. Urˇcete, kolika zp˚ usoby lze rozdat 18 knih tˇrem ˇz´ak˚ um A, B, C tak, aby A a B mˇeli dohromady dvakr´at v´ıce knih neˇz C. N´ avod: Vyberte 6 knih pro C a zb´ yvaj´ıc´ıch 12 rozdˇelte mezi A a B. [
18 6
· 212 ]
9. Knihovna m´a pˇet reg´al˚ u, do kaˇzd´eho se vejde 20 knih. Urˇcete, kolika zp˚ usoby lze do knihovny um´ıstit 20 knih. N´ avod: Myslete si, ˇze reg´aly jsou um´ıstˇeny vedle sebe a kaˇzd´e dva sousedn´ı jsou oddˇeleny stejn´ ym pˇredmˇetem. ] [ 24! 4! 10. Urˇcete, kolika zp˚ usoby si mohou tˇri osoby rozdˇelit osm stejn´ ych jablek. N´ avod: Kaˇzd´e rozdˇelen´ı osmi jablek mezi tˇri osoby A, B, C lze zaˇsifrovat pomoc´ı neuspoˇr´adan´e osmice z tˇechto p´ısmen; napˇr. AAABBBBC znaˇc´ı pˇr´ıdˇel tˇr´ı jablek osobˇe A, ˇctyˇr jablek osobˇe B a jednoho jablka osobˇe C. [K 0 (8, 3) =
10 8
= 45]
11. Kolik prvk˚ u d´a o 441 kombinac´ı s opakov´an´ım v´ıc neˇz bez opakov´an´ı ve 3. tˇr´ıdˇe? [21]
36
12. Urˇcete, kolik ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel lze sestavit z ˇc´ıslic ˇc´ısla 238 831. (v tˇechto ˇc´ıslech se kaˇzd´a cifra vyskytuje nejv´ yˇse tolikr´at, kolikr´at se vyskytuje v dan´em ˇc´ısle 238 831.) [4! + 6 ·
4! 2!
+
4! 2!2!
= 102]
13. Urˇcete kolika zp˚ usoby lze na ˇcern´a pol´ıˇcka ˇsachovnice 8 × 8 rozm´ıstit 12 b´ıl´ ych (nerozliˇsiteln´ ych) a 12 ˇcern´ ych (nerozliˇsiteln´ ych) kostek tak, aby toto rozm´ıstˇen´ı bylo symetrick´e podle stˇredu ˇsachovnice. N´ avod: Na ˇcern´a pol´ıˇcka zvolen´e poloviny ˇsachovnice rozm´ıst´ıme 6 b´ıl´ ych a 6 ˇcern´ ych kostek a dalˇs´ı 4 nerozliˇsiteln´e pˇredmˇety, ˇc´ımˇz je postaven´ı zb´ yvaj´ıc´ıch ˇcern´ ych a b´ıl´ ych kostek urˇceno. 16! ] [ 6!6!4!
14. Urˇcete poˇcet vˇsech ˇreˇsen´ı rovnice x1 + x2 + . . . + xk = n, kde n ∈ N, v mnoˇzinˇe vˇsech cel´ ych nez´aporn´ ych ˇc´ısel. [ n+k−1 ] n 15. Urˇcete, kolika zp˚ usoby lze z pades´atihal´eˇrov´ ych a korunov´ ych minc´ı zaplatit ˇc´astku a) 6 Kˇc, b) 2 Kˇc, jsou-li oba druhy minc´ı k dispozici v dostateˇcn´em mnoˇzstv´ı. N´ avod: Kaˇzdou ˇc´astku lze zaˇsifrovat pomoc´ı p´ısmen k (korunov´e mince) a p (pades´atihal´eˇrov´e mince); napˇr. ˇctyˇrem korunov´ ym a ˇctyˇrem pades´atihal´eˇrov´ ym minc´ım, odpov´ıd´a z´apis kkkkpp. [a)K 0 (6, 2) = 7; b)K 0 (2, 2) = 3] 16. Kolika zp˚ usoby lze rozdˇelit 12 minc´ı stejn´e hodnoty do 5 r˚ uzn´ ych ob´alek tak, aby ˇz´adn´a z ob´alek nez˚ ustala pr´azdn´a? N´ avod: Nejprve vloˇzte do kaˇzd´e ob´alky jednu minci. [330] 17. Urˇcete kolika zp˚ usoby lze vˇsechny figurky ˇsachov´e hry (tj. od kaˇzd´e barvy 1 kr´ale, 1 d´amu, 2 vˇeˇze, 2 jezdce, 2 stˇrelce a 8 pˇeˇsc˚ u) rozm´ıstit na 64 pol´ıˇcek ˇsachovnice. N´ avod: Myslete si, ˇze na 64 pol´ı rozmist’ujete kromˇe 32 figurek jeˇstˇe 32 stejn´ ych pˇredmˇet˚ u, tˇreba minc´ı. 64! [ 32!(8!) 2 (2!)6 ]
18. Kolik n´ahrdeln´ık˚ u lze sestavit ze 7 kor´alk˚ u dvou velikost´ı: 5 menˇs´ıch a 2 vˇetˇs´ıch? N´ avod: Typy n´ahrdeln´ık˚ u se vz´ajemnˇe odliˇsuj´ı poˇctem mal´ ych kor´alk˚ u um´ıstˇen´ ych mezi dvˇema vˇetˇs´ımi. [3]
37
Kapitola 7 Dirichlet˚ uv princip Vˇ eta. Pˇri kaˇzd´em rozdˇelen´ı nk + 1 pˇredmˇet˚ u do k pˇrihr´ adek, kde k a n jsou pˇrirozen´a ˇc´ısla, existuje alespoˇ n jedna pˇrihr´adka obsahuj´ıc´ı alespoˇ n n + 1 pˇredmˇet˚ u. 1 . pˇ r´ıklad. Konference se z´ uˇcastnilo 40 deleg´at˚ u z 13 r˚ uzn´ ych zem´ı. Dokaˇzte, ˇze delegace z alespoˇ n jedn´e zemˇe mˇela v´ıce jak tˇri ˇcleny! ˇ sen´ı. Rozdˇel´ıme deleg´aty do skupin podle zem´ı, ze kter´ Reˇ ych poch´az´ı, tj. v kaˇzd´e skupinˇe jsou vˇsichni deleg´ati z jedn´e zemˇe. Jestliˇze je skupin 13 a deleg´at˚ u je v´ıce neˇz 3 · 13 = 39, mus´ı b´ yt aspoˇ n v jedn´e skupinˇe v´ıc jak tˇri deleg´ati. 2 . pˇ r´ıklad. Podle antropologie neexistuj´ı lid´e s vˇetˇs´ım poˇctem vlas˚ u neˇz 500 000. Dokaˇzte, ˇze v Praze existuj´ı alespoˇ n dva lid´e se stejn´ ym poˇctem vlas˚ u. ˇ sen´ı. Nejprve uv´aˇz´ıme, ˇze Praha m´a v´ıce neˇz mili´on obyvatel. Obyvatele Prahy rozdˇel´ıme Reˇ do skupin tak, ˇze do n-t´e skupiny d´ame vˇsechny obyvatele Prahy, kteˇr´ı maj´ı pr´avˇe n vlas˚ u (n = 0, 1, 2, . . . , 500 000). Podle tvrzen´ı antropolog˚ u kaˇzd´ y obyvatel Prahy spad´a do nˇekter´e z tˇechto skupin. Protoˇze je Praˇzan˚ u v´ıce jako skupin, aspoˇ n v jedn´e tedy mus´ı b´ yt v´ıce neˇz jeden Praˇzan, tj. existuj´ı alespoˇ n dva obyvatel´e Prahy se stejn´ ym poˇctem vlas˚ u. 3 . pˇ r´ıklad. Konference se z´ uˇcastnilo 70 deleg´at˚ u, kteˇr´ı hovoˇr´ı 11 r˚ uzn´ ymi jazyky. Jedn´ım jazykem hovoˇr´ı nejv´ yˇse 15 deleg´at˚ u. Organizaˇcn´ı v´ ybor rozhodl, ˇze za ofici´aln´ı bude povaˇzovat takov´ y jazyk, kter´ ym hovoˇr´ı nejm´enˇe 5 deleg´at˚ u. Dokaˇzte, ˇze na konferenci byly alespoˇ n 3 ofici´aln´ı jazyky. ˇ sen´ı. Jestliˇze deleg´at˚ Reˇ u je 70 a hovoˇr´ı 11 jazyky, jistˇe jedn´ım jazykem hovoˇr´ı nejm´enˇe 5 deleg´at˚ u. Tedy existuje jeden ofici´aln´ı jazyk, nazvˇeme ho tˇreba jazyk A. Jazykem A hovoˇr´ı nejv´ yˇse 15 deleg´at˚ u, tzn., ˇze ostatn´ımi 10 jazyky hovoˇr´ı aspoˇ n 55 deleg´at˚ u. Tedy mezi tˇemito jazyky se mus´ı naj´ıt jazyk (oznaˇcme jej napˇr´ıklad B ), kter´ ym hovoˇr´ı nejm´enˇe 5 deleg´at˚ u. To je druh´ y ofici´aln´ı jazyk. Jazykem B hovoˇr´ı nejv´ yˇse 15 deleg´at˚ u, tedy zb´ yvaj´ıc´ımi 9 jazyky hovoˇr´ı aspoˇ n 40 deleg´at˚ u. Opˇet podle Dirichletova principu je moˇzn´e mezi tˇemito 9 jazyky vybrat jeden ofici´aln´ı. Existenci ˇctyˇr ofici´aln´ıch jazyk˚ u nen´ı moˇzn´e dok´azat (protipˇr´ıkladem je napˇr´ıklad n´asleduj´ıc´ı situace: Tˇremi jazyky hovoˇr´ı po 15 deleg´atech, sedmi jazyky hovoˇr´ı po 3 deleg´atech a jedn´ım jazykem hovoˇr´ı 4 deleg´ati). 38
4 . pˇ r´ıklad. V zahradˇe tvaru obd´eln´ıku o rozmˇerech 20m×15m mus´ı b´ yt m´enˇe neˇz 26 strom˚ u, aby bylo zachov´ano pravidlo, ˇze vzd´alenost dvou strom˚ u nen´ı menˇs´ı neˇz 5m. Dokaˇzte! ˇ sen´ı. Pˇripust’me, ˇze by v zahradˇe bylo v´ıce neˇz 25 strom˚ Reˇ u. Rozdˇel´ıme zahradu na obd´eln´ıky o rozmˇerech 4m×3m. Takov´ ych obd´eln´ık˚ u se do naˇs´ı zahrady vejde pr´avˇe 25. Tedy podle Dirichletova principu existuje obd´eln´ık, ve kter´em budou alespoˇ n dva stromy. Jestliˇze u ´hlopˇr´ıˇcka obd´eln´ıku m´a d´elku 5m, vzd´alenost tˇechto strom˚ u je menˇs´ı neˇz 5m. 5 . pˇ r´ıklad. 17 vˇedc˚ u si navz´ajem dopisuje (kaˇzd´ y s kaˇzd´ ym), pˇritom v cel´e korespondenci se vyskytuj´ı pouze tˇri t´emata. Dokaˇzte, existuj´ı tˇri z nich, kteˇr´ı si mezi sebou dopisuj´ı na stejn´e t´ema. ˇ sen´ı. Vybereme jednoho z vˇedc˚ Reˇ u (libovolnˇe) a ostatn´ıch 16 rozdˇel´ıme do tˇr´ı skupin tak, ˇze do kaˇzd´e skupiny d´ame vˇsechny ty, kteˇr´ı si s t´ımto zvolen´ ym dopisuj´ı na jist´e t´ema. Podle Dirichletova principu aspoˇ n v jedn´e skupinˇe se jich najde ˇsest. Tedy m´ame ˇsest vˇedc˚ u, kteˇr´ı si se zvolen´ ym p´ıˇs´ı na stejn´e t´ema. Nazvˇeme toto t´ema t´ematem ˇc´ıslo 1. Jestliˇze si mezi tˇemito ˇsesti dva p´ıˇs´ı na t´ema ˇc´ıslo 1, pˇrid´ame k nim zvolen´eho a m´ame tˇri, kteˇr´ı si p´ıˇs´ı na t´ema ˇc´ıslo 1. V opaˇcn´em pˇr´ıpadˇe m´ame 6 vˇedc˚ u, kteˇr´ı si mezi sebou dopisuj´ı pouze na t´ema ˇc´ıslo 2 a t´ema ˇc´ıslo 3. Mezi tˇemito ˇsesti si zvol´ıme jednoho. Zb´ yvaj´ıc´ıch pˇet rozdˇel´ıme na dvˇe skupiny. Skupinu tˇech, kteˇr´ı si se zvolen´ ym p´ıˇs´ı na t´ema ˇc´ıslo 2 a skupinu tˇech, kteˇr´ı si s n´ım dopisuj´ı na t´ema ˇc´ıslo 3. Podle Dirichletova principu aspoˇ n v jedn´e skupinˇe se najdou tˇri. Tito tˇri si bud’ vˇsichni p´ıˇs´ı na stejn´e t´ema a ˇreˇsen´ı je hotov´e, nebo se najdou dva, kteˇr´ı si p´ıˇs´ı na stejn´e t´ema se zvolen´ ym. Potom m´ame znovu tˇri vˇedce, kteˇr´ı si dopisuj´ı na shodn´e t´ema. 1. Na vysokou ˇskolu pˇrijali do prvn´ıho roˇcn´ıku 120 posluchaˇc˚ u, kteˇr´ı maturovali na 84 stˇredn´ıch ˇskol´ach. Potom se v prvn´ım roˇcn´ıku najdou aspoˇ n dva posluchaˇci, kteˇr´ı se poznaj´ı ze stˇredn´ı ˇskoly. Dokaˇzte! 2. Nepoˇr´adn´ y student mˇel v z´asuvce ponoˇzky pˇeti barev (z kaˇzd´e barvy aspoˇ n dvˇe). Kolik nejm´enˇe kus˚ u ponoˇzek mus´ı potmˇe vybrat, aby si mohl b´ yt jist´ y, ˇze mezi nimi budou dvˇe od stejn´e barvy? 3. Soukrom´a knihovna m´a 1 100 svazk˚ u, pˇriˇcemˇz ˇz´adn´ y z nich nem´a v´ıce jak 1 000 stran. Dokaˇzte, ˇze v knihovnˇe existuj´ı alespoˇ n dvˇe knihy se stejn´ ym poˇctem stran. 4. Dokaˇzte, ˇze v sadˇe, jenˇz m´a tvar obd´eln´ıku o rozmˇerech 100m ×300m, mus´ı b´ yt m´enˇe neˇz 3 851 strom˚ u, jestliˇze vzd´alenost libovoln´ ych dvou mus´ı b´ yt vˇetˇs´ı neˇz 4m. 5. V ˇsachov´em turnaji, kter´eho se u ´ˇcastn´ı 6 hr´aˇc˚ u, se vˇzdy najde trojice hr´aˇc˚ u, kteˇr´ı mezi sebou hr´ali uˇz kaˇzd´ y s kaˇzd´ ym , nebo trojice, ve kter´e ˇz´adn´ y s ˇz´adn´ ym jeˇstˇe nehr´al. Dokaˇzte!
39
Kapitola 8 Princip inkluze a exkluze ´ cinn´ Uˇ ym prostˇredkem pˇri ˇreˇsen´ı ˇrady kombinatorick´ ych u ´loh je tzv. princip inkluze a exkluze (ˇcesky bychom mohli ˇr´ıci princip vyluˇcov´an´ı a zapojov´an´ı prvk˚ u). Pˇred jeho formulac´ı si uk´aˇzeme v ˇcem spoˇc´ıv´a jeho podstata. Bud’te M1 , M2 libovoln´e koneˇcn´e mnoˇziny, |M | mohutnost mnoˇziny M . Pak zˇrejmˇe plat´ı |M1 ∪ M2 | = |M1 | + |M2 | − |M1 ∩ M2 |. Pro tˇri mnoˇziny je zˇrejm´e, ˇze mohutnost jejich sjednocen´ı obecnˇe neobdrˇz´ıme, kdyˇz od souˇctu jejich mohutnost´ı odeˇcteme mohutnosti pr˚ unik˚ u vˇsech dvojic tˇechto mnoˇzin. Nˇekter´e prvky bychom totiˇz mohli odeˇc´ıst dvakr´at – a sice ty prvky, kter´e leˇz´ı v pr˚ uniku vˇsech tˇr´ı tˇechto mnoˇzin. Zˇrejmˇe tak plat´ı |M1 ∪ M2 ∪ M3 | = |M1 | + |M2 | + |M3 | − |M1 ∩ M2 | − |M1 ∩ M3 | − |M2 ∩ M3 | + |M1 ∪ M2 ∪ M3 |. Zobecnˇen´ım popsan´eho procesu obdrˇz´ıme n´asleduj´ıc´ı princip inkluze a exkluze. Vˇ eta (Princip inkluze a exkluze). Bud’ d´ ana koneˇcn´ a mnoˇzina M. Necht’ prvky mnoˇziny M mohou m´ıt vlastnosti α1 , α2 , . . . , αn . Symbolem M (αi1 , αi2 , . . . , αik , αj0 1 , αj0 2 , . . . , αj0 p ) oznaˇcme poˇcet vˇsech prvk˚ u mnoˇziny M, kter´e maj´ı vlastnosti αi1 , αi2 , . . . , αik a nemaj´ı ˇz´ adnou z vlastnost´ı αj1 , αj2 , . . . , αjp (bez ohledu na to, maj´ı-li nebo nemaj´ı vlastnosti, kter´e ve v´yˇctu αi1 , αi2 , . . . , αik , αj1 , αj2 , . . . , αjp nejsou uvedeny). Pak plat´ı M (α10 , α20 , . . . , αn0 ) = |M | −
n X i=1
−
X
M (αi ) +
X
M (αi , αj )−
i<j
M (αi , αj , αk ) + · · · + (−1)n M (αi , α2 , . . . , αn ).
i<j
1 . pˇ r´ıklad. Ve vˇedeckov´ yzkumn´em u ´stavu pracuje 67 lid´ı, 47 z nich ovl´ad´a angliˇctinu, 35 nˇemˇcinu a 23 zn´a oba z tˇechto jazyk˚ u. Kolik pracovn´ık˚ uu ´stavu neum´ı ani nˇemecky, ani anglicky? 40
ˇ sen´ı. Rozdˇelme kolektiv pracovn´ık˚ Reˇ uu ´stavu na ˇc´asti, kter´e nemaj´ı ˇz´adn´e spoleˇcn´e prvky. Do prvn´ı z nich budou patˇrit ti, kteˇr´ı znaj´ı pouze angliˇctinu, do druh´e vˇsichni, kteˇr´ı umˇej´ı jenom nˇemecky, do tˇret´ı ˇc´asti budou n´aleˇzet takov´ı, kteˇr´ı ovl´adaj´ı oba jazyky, a do ˇctvrt´e vˇsichni kteˇr´ı neznaj´ı ani jeden ani druh´ y jazyk. V´ıme, ˇze do tˇret´ı ˇc´asti patˇr´ı 23 lid´ı. Vzhledem k tomu, ˇze angliˇctinu zn´a 47 lid´ı, ovl´ad´a jenom angliˇctinu 47−23 = 24 pracovn´ık˚ u u ´stavu. Obdobnˇe jenom nˇemˇcinu ovl´ad´a 35−23 = 12 lid´ı. Odtud vypl´ yv´a, ˇze celkov´ y poˇcet pracovn´ık˚ u, kteˇr´ı ovl´adaj´ı aspoˇ n jeden z jazyk˚ u, je 23 + 24 + 12 = 59. V u ´stavu pracuje celkem 67 lid´ı, a tedy ve ˇctvrt´e ˇc´asti je 67 − 59 pracovn´ık˚ u. Jinak ˇreˇceno, 8 lid´ı neum´ı ani anglicky ani nˇemecky. Tento z´avˇer m˚ uˇzeme zapsat ve tvaru: 8 = 67 − (23 + 24 + 12). Ale 24 jsme z´ıskali odeˇcten´ım ˇc´ısla 23 od ˇc´ısla 47 a obdobnˇe ˇc´ıslo 12 odeˇcten´ım 23 od 35. Proto 8 = 67 − 23 − (47 − 23) − (35 − 23) = 67 − 47 − 35 + 23. A tady uˇz je vidˇet urˇcit´a z´akonitost: Od celkov´eho poˇctu pracovn´ık˚ u odeˇc´ıt´ame poˇcet ovl´adaj´ıc´ıch angliˇctinu a poˇcet ovl´adaj´ıc´ıch nˇemˇcinu. Pˇritom jsou vˇsak nˇekteˇr´ı pracovn´ıci ”odeˇc´ıt´ani” dvakr´at (pracovn´ıci, kteˇr´ı ovl´adaj´ı oba jazyky). Jestliˇze jejich poˇcet pˇriˇcteme, dostaneme poˇcet osob, kter´e neznaj´ı ani jeden z uveden´ ych jazyk˚ u. 2 . pˇ r´ıklad. Pˇredseda tˇr´ıdy podal tuto zpr´avu: ”Ve tˇr´ıdˇe je 45 ˇz´ak˚ u, z toho je 25 chlapc˚ u. 30 ˇz´ak˚ u m´a dobr´ y prospˇech, z nich je 16 chlapc˚ u. Sportu se vˇenuje 28 ˇz´ak˚ u, z toho 18 chlapc˚ u a 17 ˇz´ak˚ u, kteˇr´ı maj´ı dobr´ y prospˇech. 15 chlapc˚ u m´a dobr´ y prospˇech a souˇcasnˇe sportuje.” Za nˇekolik dn´ı si ho pozval tˇr´ıdn´ı uˇcitel (kter´ y jako naschv´al uˇc´ı matematiku) a sdˇelil mu, ˇze ve zpr´avˇe je chyba. Zkusme objasnit, jak na to pˇriˇsel. Zjist´ıme, kolik je d´ıvek, kter´e nesportuj´ı a pˇritom nemaj´ı dobr´ y prospˇech. Oznaˇcme α1 -pˇr´ısluˇsnost k muˇzsk´emu pohlav´ı, α2 -dobr´ y prospˇech, α3 -pˇestov´an´ı sportu. Urˇceme, ˇcemu je rovno N (α01 α02 α03 ).Podle podm´ınek u ´lohy je N (α1 ) = 25, N (α2 ) = 30, N (α3 ) = 28, N (α1 α2 ) = 16, N (α1 α3 ) = 18, N (α2 α3 ) = 17, N (α1 α2 α3 ) = 15. Podle principu inkluze a exkluze dost´av´ame N (α01 α02 α03 ) = 45 − 25 − 30 − 28 + 16 + 18 + 17 − 15 = −2 Ale poˇcet d´ıvek ve tˇr´ıdˇe pˇrece nem˚ uˇze b´ yt z´aporn´ y! Proto je urˇcitˇe v uveden´e zpr´avˇe vnitˇrn´ı rozpor, je nepravdiv´a. 3 . pˇ r´ıklad. Kolika zp˚ usoby m˚ uˇzeme posadit do ˇrady 3 Angliˇcany, 3 Francouze a 3 Turky tak, aby ˇza´dn´ı tˇri krajan´e nesedˇeli vedle sebe? 41
ˇ sen´ı. 9 lid´ı lze pˇresazovat 9! zp˚ Reˇ usoby. Najdˇeme, v kolika permutac´ıch sed´ı 3 Angliˇcan´e vedle sebe. Vˇsechny takov´e permutace dostaneme z jedn´e tak, ˇze pˇresazujeme mezi sebou Angliˇcany (3! zp˚ usob˚ u) a d´ale pˇremist’ujeme 6 Francouz˚ u a Turk˚ u a skupinu Angliˇcan˚ u jako celek (7! zp˚ usob˚ u). Celkem dost´av´ame 3!7! permutac´ı. Stejn´ y je poˇcet permutac´ı, kdy sed´ı vedle sebe 3 Turci, resp. 3 Francouzi. Ve (3!)2 5 permutac´ıch sed´ı vedle sebe i Angliˇcan´e i Francouzi, ve (3!)4 permutac´ıch jsou vedle sebe i Angliˇcan´e i Francouzi i Turci. Podle principu inkluze a exkluze doch´az´ıme k z´avˇeru: 9! − 3 · 3!7! + 3(3!)2 5! − (3!)4 = 283 824. 4 . pˇ r´ıklad. Kolik nez´aporn´ ych cel´ ych ˇc´ısel menˇs´ıch neˇz mili´on obsahuje kaˇzdou z cifer 1, 2, 3, 4? Kolik ˇc´ısel se skl´ad´a pouze z tˇechto cifer? ˇ sen´ı. Podle principu inkluze a exkluze zjist´ıme, ˇze vˇsechny cifry 1, 2, 3, 4 obsahuje 106 − Reˇ 4·96 +6·86 −4·76 +66 , tj. 23 160 ˇc´ısel. Pouze z cifer 1, 2, 3, 4 se skl´ad´a 4+42 +43 +44 +45 +46 = 47 −4 = 5 460 ˇc´ısel. 3 5 . pˇ r´ıklad. Na v´ ylet se vydalo 92 lid´ı. Obloˇzen´e chleby se sal´amem si vzalo 47 lid´ı, se s´ yrem 38 lid´ı, se ˇsunkou 42 lid´ı, se s´ yrem a se sal´amem 28 lid´ı, se sal´amem a ˇsunkou 31 lid´ı, se s´ yrem a se ˇsunkou 26 lid´ı. Vˇsechny tˇri druhy obloˇzen´ ych chleb˚ u si vzalo 25 lid´ı; nˇekolik osob vzalo s sebou m´ısto chleb˚ u piroˇzky. Kolik lid´ı si vzalo piroˇzky? ˇ sen´ı. Podle principu inkluze a exkluze si piroˇzky vzalo 25 lid´ı (92 − 47 − 38 − 42 + 28 + Reˇ 31 + 26 − 25).
42
Seznam pouˇ zit´ e literatury [1] E. Fuchs: Diskr´etn´ı matematika pro uˇcitele, Brno 2001 [2] N. J. Vilenkin: Kombinatorika, SNTL, Praha – Moskva 1977 [3] J. Neˇsetˇril: Kombinatorika, SPN, Praha 1975 [4] L. Bukovsk´ y, I. Kluv´anek: Dirichletov princ´ıp, Mlad´a fronta, Praha 1970 [5] E. Calda, V. Dupaˇc: Kombinatorika, pravdˇepodobnost, statistika, Prometheus, Praha 2003 [6] P. Benda a kolektiv: Sb´ırka maturitn´ıch pˇr´ıklad˚ u z matematiky, SPN, Praha 1971 [7] J. Herman a kolektiv: Metody ˇreˇsen´ı matematick´ych u ´loh II, Brno 1991 [8] E. Kriegelstein a kolektiv: Sb´ırka u ´loh z matematiky, SPN, Praha 1980
43
