BOOLEOVA ALGEBRA Definice: Necht’ je d´ana nepr´azdn´a mnoˇzina B, na n´ıˇz jsou zavedeny bin´arn´ı operace sˇc´ıt´an´ı a n´ asoben´ı a un´ arn´ı operace doplnˇek prvku z mnoˇziny B. Tyto operace budeme oznaˇcovat obvykl´ ym zp˚ usobem, tj. x + y, x · y nebo xy a x0 . Necht’ v mnoˇzinˇe B existuj´ı dva navz´ajem r˚ uzn´e prvky, kter´e oznaˇc´ıme 0, 1. Mnoˇzinu B spolu s tˇemito operacemi naz´ yv´ame Booleova algebra, jestliˇze pro kaˇzd´e prvky x, y, z ∈ B plat´ı: (1) x + 0 = x (2) x + x0 = 1 (3) x + y = y + x (4) x + (y + z) = (x + y) + z (5) x + (y · z) = (x + y) · (x + z) (6) x · 1 = x (7) x · x0 = 0 (8) x · y = y · x (9) x · (y · z) = (x · y) · z (10) x · (y + z) = (x · y) + (x · z) Oznaˇcen´ı (B, +, ·, 0 ). Pozn´ amka: Domluv´ıme se, ˇze operace n´asoben´ı bude m´ıt pˇrednost pˇred operac´ı sˇc´ıt´an´ı. V Booleovˇe algebˇre plat´ı princip duality. Vˇ eta: V Booleovˇe algebˇre (B, +, ·, 0 ) pro libovoln´e prvky x, y, z ∈ B plat´ı: (a) x + x = x (b) x · x = x (c) x + 1 = 1 (d) x · 0 = 0 (e) (x0 )0 = x (f) 10 = 0, 00 = 1 (g) (x + y)0 = x0 · y 0 (h) (x · y)0 = x0 + y 0 (i) x + xy = x (j) x(x + y) = x (k) x + x0 y = x + y (l) x(x0 + y) = xy (m) x + y = 0 ⇔ x = 0 ∧ y = 0 (n) x · y = 1 ⇔ x = 1 ∧ y = 1 (o) x = y ⇔ xy 0 + x0 y = 0 (p) x = y ⇔ (x + y 0 )(x0 + y) = 1 Vˇ eta: V Booleovˇe algebˇre (B, +, ·, 0 ) zavedeme bin´arn´ı relaci R takto: ∀ x, y ∈ B : x R y ⇔ xy 0 = 0. Potom relace R je reflexivn´ı, antisymetrick´a a tranzitivn´ı. Pozn´ amka: To znamen´a, ˇze relace R z pˇredchoz´ı vˇety je neostr´e line´arn´ı uspoˇr´ad´an´ı v mnoˇzinˇe B a budeme ji proto oznaˇcovat symbolem ≤“. ” Vˇ eta: V Booleovˇe algebˇre (B, +, ·, 0 ) s uspoˇr´ad´an´ım ≤“ pro libovoln´e prvky x, y ∈ B plat´ı: ” (a) x ≤ y ⇔ x + y = y (b) x ≤ y ⇔ xy = x (c) 0 ≤ x ∧ x ≤ 1 (d) x ≤ y ⇔ y 0 ≤ x0 Modely Booleovy algebry 1) Mnoˇzinov´a algebra (P (M ), ∪, ∩, 0 ), kde P (M ) je potenˇcn´ı mnoˇzina libovoln´e nepr´azdn´e mnoˇziny M , je modelem Booleovy algebry. 1
2) Mˇejme klasickou dvouhodnotovou logiku, symboly 0, 1 necht’ oznaˇcuj´ı pravdivostn´ı hodnoty nepravda a pravda. Potom algebra pravdivostn´ıch hodnot ({0, 1}, ∨, ∧, ¬) je modelem dvouprvkov´e Booleovy algebry. ´ Ulohy 1) Rekreanti A, B, C, D, E se rozhoduj´ı, zda podniknou cestu parn´ıkem. Sv´e rozhodnut´ı podmiˇ nuj´ı nˇekteˇr´ı t´ım, jak se rozhodnou dalˇs´ı z nich. Pan´ı B ˇr´ık´a, ˇze pojede, vyd´a-li se na cestu i jej´ı manˇzel A. P´ anov´e A a D rozhodnˇe pojedou, pojede-li t´eˇz vesel´ y p´an E. Pan´ı B a sleˇcna C se nemaj´ı r´ady, ani za nic nepojedou spoleˇcnˇe. Sleˇcna C a pan D naopak pojedou jen spolu nebo ˇz´adn´ y z nich. Zjistˇete, kdo nastoup´ı na parn´ık, v´ıte-li, ˇze alespoˇ n jeden z p´an˚ u D, E si cestu nenech´a uj´ıt. 2) Pˇri vyˇsetˇrov´an´ı kr´adeˇze bylo zjiˇstˇeno pˇet podezˇrel´ ych A, B, C, D, E. V dobˇe ˇcinu mohl b´ yt na m´ıstˇe C nebo D, ale nejv´ yˇse jeden z dvojice A, B a alespoˇ n jeden z dvojice A, C. Podezˇrel´ y E tam mohl b´ yt jen v pˇr´ıtomnosti D, ale pokud tam E byl, nechybˇel ani C. Lze vylouˇcit spolupr´aci B s D, zato B a C tvoˇr´ı nerozluˇcnou dvojici. Kdo z podezˇrel´ ych m´a alibi a jak´e jsou moˇznosti pro sloˇzen´ı party? 3) Mal´ıˇr m´a sedm kel´ımk˚ u s barvami. Chce nam´ıchat odst´ın barvy, kter´ y se nevyr´ab´ı. Pˇr´al by si, aby novˇe nam´ıchan´a barva obsahovala: - alespoˇ n jednu z barev D, E, - nejv´ yˇse jednu z barev A, B, - barvu C pr´avˇe tehdy, kdyˇz bude obsahovat barvu B, - pouˇzije-li barvu C, mus´ı pouˇz´ıt barvu F , - pouˇzije-li barvu D, nesm´ı pouˇz´ıt barvu A, - nepouˇzije-li barvu B, mus´ı pouˇz´ıt barvu G, - barvu F nesm´ı sm´ıchat s barvou G. Kolik nov´ ych barev a v jak´em sloˇzen´ı nam´ıch´a? 4) Fotograf m´a poˇr´ıdit reklamn´ı dn´ımky skupiny objekt˚ u, kter´e nelze pˇrem´ıstit. D´ıval se hled´ aˇckem fotoapar´atu a o v´ ysledc´ıch referoval objednavateli: - zachyt´ım-li objekt A, nezachyt´ım objekt B, - kdyˇz nebude na sn´ımku objekt D, bude na nˇem objekt C i E, - na kaˇzd´em sn´ımku s objektem C bude objekt A, - z objekt˚ u C, D se vˇzdy podaˇr´ı zachytit alespoˇ n jeden, - zachyt´ım-li objekt D, pak bude na sn´ımku i objekt B. Na kolika sn´ımc´ıch m˚ uˇze b´ yt objekt A alespoˇ n s jedn´ım dalˇs´ım objektem? Co lze odpovˇedˇet na stejnou ot´ azku s objektem B? 5) Parta kamar´ad˚ u si domlouv´a v´ ylet do Krkonoˇs. Den, kter´ y navrhuje vedouc´ı A se nehod´ı vˇsem. Ze sourozenc˚ u C, E i B, F bude moci jet na v´ ylet vˇzdy jen jeden. D´ale bude chybˇet alespoˇ n jeden ze dvojice A, D a G, H. Naproti tomu je jist´e, ˇze pojede A nebo H, d´ale pak E nebo G a alespoˇ n jeden z dvojice D, F . Ze dvojice nadˇsen´ ych turist˚ u B, C bude sh´azet nejv´ yˇse jeden. Kdo se vyprav´ı na v´ ylet s vedouc´ım A? 6) Rozhodnˇete, kdo ze sedmi kamar´ad˚ u A, B, C, D, E, F , G p˚ ujde do kina, jestliˇze maj´ı b´ yt splnˇeny n´ asleduj´ıc´ı podm´ınky: Ze dvojice A, B p˚ ujde alespoˇ n jeden, pr´avˇe kdyˇz p˚ ujdou oba z dvojice C, D. Bud’ alespoˇ n jeden ze dvojice E, F nepˇrijde nebo nepˇrijde ani jeden z dvojice A, G. Pˇrijde-li ze dvojice B, C nejv´ yˇse jeden, pak pˇrijde alespoˇ n jeden z dvojice E, D. E nepˇrijde bez F . Ze dvojice F , G pˇrijdou bud’ oba nebo ani jeden. 7) Rozhodnˇete, zda z pˇredpokladu, ˇze plat´ı (¬A ∧ ¬B) ⇒ ¬D a (A ∨ C) ⇒ ¬B a (¬A ∨ ¬D) ⇒ ¬(B ∧ C) a A ∨ B ∨ C ∨ D, plyne z´avˇer u ´sudku: a) A ∨ C b) ¬B ⇒ C c) C ⇒ ¬D d) A ↔ D e) ¬B ⇒ (A ∨ C) 8) Rozhodnˇete, zda z pˇredpokladu, ˇze plat´ı A ⇒ (¬B∧¬D) a B ⇒ (¬C ∧¬E) a C ⇒ ¬E a (A∧C) ⇒ ¬D a ¬A ⇒ B, plyne z´avˇer u ´sudku: 2
a) B ⇒ D b) (¬A ∧ ¬B) ⇒ (E ∨ C)
ZEBRY 1) V ulici stoj´ı vedle sebe pˇet domk˚ u, kaˇzd´ y jin´e barvy. Zjistˇete, v jak´em poˇrad´ı domky stoj´ı, kter´ y muˇz a kter´a ˇzena v nich bydl´ı, jak´e zv´ıˇre chovaj´ı a jak´e auto vlastn´ı, v´ıte-li: 1. Adam bydl´ı v ˇcerven´em domku. 2. Leoˇs m´a psa. 3. Milan bydl´ı v prvn´ım domku zleva. 4. Jiˇrina bydl´ı ve ˇzlut´em domku. 5. Iveta m´a sousedy, kteˇr´ı chovaj´ı rybiˇcky. 6. Milan bydl´ı vedle modr´eho domku. 7. Berta m´a koˇcku. 8. Eva jezd´ı v autˇe Fiat. 9. Tom´aˇs vlastn´ı auto Seat. 10. Karel se oˇzenil s Luci´ı. 11. Jiˇrina m´a sousedy, kteˇr´ı chovaj´ı konˇe. 12. V zelen´em domku maj´ı Mazdu. 13. Zelen´ y domek je hned nalevo od b´ıl´eho. ˇ 14. Skodu vlastn´ı v prostˇredn´ım domku. 15. Nˇekdo vlastn´ı auto Renault. 16. V jednom domku chovaj´ı ˇzelvu. 2) V jednom pˇr´ıstavu vedle sebe stoj´ı pˇet lod´ı. ˇ 1. Reck´ a lod’ vyplouv´a v 6 hodin a veze k´avu. 2. Prostˇredn´ı lod’ m´a ˇcern´ y kom´ın. ’ 3. Anglick´a lod vyplouv´a v 9 hodin. 4. Francouzsk´a lod’ je nalevo od lodi vezouc´ı k´avu a m´a modr´ y kom´ın. 5. Napravo od lodi vezouc´ı kakao je lod’ pluj´ıc´ı do Marseille. 6. Brazilsk´a lod’ pluje do Manily. 7. Vedle lodi vezouc´ı r´ yˇzi je lod’ se zelen´ ym kom´ınem. ’ 8. Lod do Janova vyplouv´a v 5 hodin. ˇ 9. Spanˇ elsk´a lod’ vyplouv´a v 7 hodin a je napravo od lodi pluj´ıc´ı do Marseille. 10. Do Hamburku pluje lod’ s ˇcerven´ ym kom´ınem. 11. Vedle lodi vyplouvaj´ıc´ı v 7 hodin je lod’ s b´ıl´ ym kom´ınem. 12. Lod’ kotv´ıc´ı na kraji veze obil´ı. 13. Lod’ s ˇcern´ ym kom´ınem vyplouv´a v 8 hodin. 14. Lod’ vezouc´ı obil´ı kotv´ı vedle lodi vezouc´ı r´ yˇzi. 15. Do Hamburku vyplouv´a lod’ v 6 hodin. Kter´a lod’ pluje do Port Saidu a kter´a veze ˇcaj? 3) Na tenisov´em dvorci sed´ı vedle sebe pˇet chlapc˚ u se sv´ ymi d´ıvkami a sleduj´ı hru. Kaˇzd´a d´ıvka drˇz´ı v ruce kytiˇcku kvˇetin, kterou j´ı koupil jej´ı chlapec. 1. Fialky koupil mechanik. 2. Prodavaˇc sed´ı vedle chlapce, kter´ y m´a r´ad fotbal. 3. Optik m´a r´ad odb´ıjenou. 4. Vl´ad’a si ol´ıbil h´azenou. 5. Chlapec v prostˇredn´ım p´aru je optik. 6. Zuzana tvrd´ı, ˇze jej´ı Jirka m´a nejradˇeji tenis. 7. Miloˇs koupil astry. 8. R˚ uˇze pˇrinesl milovn´ık hokeje. 9. Boˇzena sed´ı se sv´ ym chlapcem na prav´em kraji. 10. Vedle Boˇzeny sed´ı Ivana. 3
11. Tenista daroval kytiˇcku fialek. 12. Pavel sed´ı napravo od chlapce, kter´ y koupil narcisy. 13. Karel studuje na vysok´e ˇskole. ˇ c chod´ı s Boˇzenou. 14. Ridiˇ 15. Pavel m´a nejradˇeji fotbal. 16. Napravo od Karla sed´ı chlapec se Zuzanou. 17. D´ıvka s kytic´ı narcis˚ u je napravo od Marie. Kdo koupil Jiˇriny? Kdo chod´ı s Alenou? 4) Na houb´ach se seˇslo pˇet houbaˇr˚ u. Byli r˚ uznˇe staˇr´ı a r˚ uznˇe obut´ı. Jejich n´alez byl r˚ uzn´ y a houby d´ avali do r˚ uzn´ ych n´adob. K dispozici m´ame tyto u ´daje: 1. Houbaˇr o 6 let mladˇs´ı neˇz houbaˇr v botask´ach byl nejmladˇs´ı a nasb´ıral sam´e muchom˚ urky. 2. Houbaˇr v botask´ach si bral taˇsku zbyteˇcnˇe. 3. Kadeˇr´abek, kter´ y je o 12 let starˇs´ı neˇz nejmladˇs´ı, si vzal sand´aly. 4. Pln´ y koˇs´ık prav´ ych hˇrib˚ u naˇsel houbaˇr, kter´ y byl starˇs´ı neˇz Star´ y. 5. Houbaˇr, kter´ y je pr´avˇe o tolik let mladˇs´ı neˇz Kadeˇr´abek, jako je mladˇs´ı nejmladˇs´ı houbaˇr od houbaˇre v botask´ach, se jmenuje Dolejˇs´ı. 6. Pohorky nemˇel houbaˇr jm´enem Star´ y. 7. Nov´ak ˇsel na houby v polobotk´ach a nen´ı o 33 let starˇs´ı neˇz nejmladˇs´ı. 8. Jeden houbaˇr, kter´ y je o 20 let starˇs´ı neˇz houbaˇr v botask´ach, si nesl na houby pytel. 9. Dolejˇs´ı m´a tolikr´at tolik let, o kolik je nejmladˇs´ı mladˇs´ı neˇz houbaˇr v botask´ach. 10. Houbaˇr Star´ y nen´ı nejmladˇs´ı. 11. Houbaˇr, kter´ y je o 21 let mladˇs´ı neˇz nejstarˇs´ı, ˇsel p˚ uvodnˇe na ostruˇziny - m´a tedy kbel´ık. 12. Nˇemec nenaˇsel ˇzampiony. 13. Houbaˇr, kter´ y nemˇel pohorky ani sand´aly, sb´ıral do igelitov´eho s´aˇcku. 14. Smˇes hub naˇsel houbaˇr v gum´ak´ach. Urˇcete jm´eno kaˇzd´eho houbaˇre, jeho vˇek, obuv a do ˇceho d´aval houby, pokud nˇejak´e naˇsel. ´ ´R ˇ´ ULOHY O POCTIVC´ ICH A LHA ICH Ostrov poctivc˚ u a padouch˚ u Existuje velk´e mnoˇzstv´ı h´adanek o ostrovˇe, na nˇemˇz jedni jeho obyvatel´e, naz´ yvan´ı poctivci, vˇzdy mluv´ı pravdu, a ostatn´ı, naz´ yvan´ı padouchy, vˇzdy lˇzou. Pˇredpokl´ad´a se, ˇze kaˇzd´ y obyvatel ostrova je bud’ poctivec, nebo padouch. 1) Kl´abos´ı tˇri obyvatel´e A, B a C. Jde kolem cizinec a zept´a se A: Jste padouch nebo poctivec?“ A ” odpov´ı, ale nezˇretelnˇe, takˇze cizinec nerozezn´a, co ˇrekl. Cizinec se proto zept´a B: Co ˇr´ıkal A?“ B odpov´ı: ” A ˇr´ıkal, ˇze je padouch.“ V tom okamˇziku C ˇrekne: Nevˇeˇrte B, ten lˇze!“ Co jsou B a C? ” ” 2) Cizinec se zept´a A: Kolik je mezi v´ami poctivc˚ u?“ A odpov´ı nezˇretelnˇe. Cizinec se tedy zept´ a B: ” Co ˇr´ıkal A?“ B odpov´ı: A ˇr´ıkal, ˇze je mezi n´ami jedin´ y poctivec.“ Nato ˇrekne C: Nevˇeˇrte B, ten lˇze!“ Co ” ” ” jsou B a C? 3) V t´ehle h´adance vystupuj´ı jenom dva, A a B, kaˇzd´ y z nich je poctivec nebo padouch. A prohl´ as´ı: Aspoˇ n jeden z n´as je padouch.“ Co jsou A a B? ” 4) Zase m´ame tˇri, A, B a C, a kaˇzd´ y je bud’ poctivec, nebo padouch. A ˇrekne: Vˇsichni jsme padouˇsi.“ ” B ˇrekne: Pr´avˇe jeden z n´as je poctivec.“ Co jsou A, B a C? ” 5) A ˇrekne: J´a jsem padouch, ale B ne.“ Co jsou A a B? ” Poctivci, padouˇ si a norm´ aln´ı lidi Zaj´ımav´e jsou i h´adanky, v nichˇz se vyskytuj´ı tˇri typy lid´ı - poctivci, kteˇr´ı vˇzdy mluv´ı pravdu, padouˇsi, kteˇr´ı vˇzdy lˇzou, a norm´aln´ı lidi, kteˇr´ı nˇekdy mluv´ı pravdu a nˇekdy lˇzou.
4
1) M´ame tˇri lidi, A, B a C, jeden z nich je poctivec, druh´ y padouch a tˇret´ı norm´aln´ı (ale ne nutnˇe v tomto poˇrad´ı). A ˇrekne: J´a jsem norm´aln´ı.“ B ˇrekne: To je pravda.“ C ˇrekne: J´a nejsem norm´ aln´ı.“ Co ” ” ” jsou A, B a C? 2) M´ame dva lidi, A a B, z nichˇz kaˇzd´ y je poctivec, padouch nebo norm´aln´ı ˇclovˇek. A ˇrekne: poctivec.“ B ˇrekne: A nen´ı poctivec.“ Co jsou A a B? ” 3) M´ame dva lidi, A a B, z nichˇz kaˇzd´ y je poctivec, padouch nebo norm´aln´ı ˇclovˇek. A ˇrekne: poctivec.“ B ˇrekne: A je padouch.“ Co jsou A a B? ”
B je ” B je ”
KOMBINATORIKA Z´ akladn´ı pojmy Permutace z n prvk˚ u 1) Kolik ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel lze sestavit z cifer a) 1, 2, 3, 4 b) 0, 1, 2, 3 nesm´ı-li se ˇz´adn´a cifra opakovat? 2) Na sch˚ uzi m´a promluvit 5 ˇreˇcn´ık˚ u A, B, C, D, E (kaˇzd´ y pr´avˇe jednou). a) Urˇcete poˇcet vˇsech moˇzn´ ych poˇrad´ı jejich vystoupen´ı. b) Urˇcete poˇcet vˇsech moˇzn´ ych poˇrad´ı jejich vystoupen´ı, m´a-li ˇreˇcn´ık B promluvit bezprostˇrednˇe po A. c) Urˇcete poˇcet vˇsech moˇzn´ ych poˇrad´ı jejich vystoupen´ı, m´a-li ˇreˇcn´ık B promluvit aˇz pot´e, co promluvil ˇreˇcn´ık A. 3) Urˇcete poˇcet vˇsech sud´ ych pˇeticifern´ ych pˇrirozen´ ych ˇc´ısel vytvoˇren´ ych z cifer 1, 2, 3, 4, 5, nem˚ uˇze-li se v dan´em ˇc´ısle ˇz´adn´a cifra opakovat. 4) Kolika zp˚ usoby m˚ uˇzeme posadit ke kulat´emu stolu 5 muˇz˚ u a 5 ˇzen tak, aby ˇz´adn´e dvˇe osoby t´ehoˇz pohlav´ı nesedˇely vedle sebe? 5) Kolika zp˚ usoby lze postavit do ˇrady 4 Angliˇcany, 5 Francouz˚ u a 3 Turky, mus´ı-li osoby t´eˇze n´ arodnosti st´ at vedle sebe? Variace bez opakov´ an´ı 1) 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? 2) Urˇcete poˇcet vˇsech sud´ ych pˇrirozen´ ych ˇc´ısel sestaven´ ych z cifer 2, 3, 4, 5, 6, v nichˇz se kaˇzd´ a cifra vyskytuje nejv´ yˇse jednou. Kombinace bez opakov´ an´ı 1) V rovinˇe je d´ano 6 r˚ uzn´ ych bod˚ u, z nichˇz ˇz´adn´e 3 neleˇz´ı v jedn´e pˇr´ımce. Kolik pˇr´ımek tyto body urˇcuj´ı? 2) Ze skupiny 7 chlapc˚ u a 4 d´ıvek je tˇreba vybrat ˇsestiˇclenn´e volejbalov´e druˇzstvo, v nˇemˇz mus´ı b´ yt alespoˇ n dvˇe d´ıvky. Kolika zp˚ usoby to lze uˇcinit? 3) Na taneˇcn´ı z´abavˇe se seˇsla skupina 12 chlapc˚ u a 15 d´ıvek. Urˇcete, kolika zp˚ usoby z nich lze vybrat 4 p´ ary pro tanec. 4) Kolika zp˚ usoby je moˇzn´e z ˇc´ısel 1, 2, . . . , 100 vybrat tˇri r˚ uzn´a ˇc´ısla tak, aby jedno z nich bylo aritmetick´ ym pr˚ umˇerem ostatn´ıch dvou? 5) 5 d´ıvek a 3 chlapci si chtˇej´ı zahr´at volejbal. Kolika zp˚ usoby se mohou rozdˇelit do dvou druˇzstev po ˇctyˇrech tak, aby v kaˇzd´em druˇzstvu byl alespoˇ n jeden chlapec? 6) Kolika zp˚ usoby je moˇzn´e vybrat z pˇrirozen´ ych ˇc´ısel menˇs´ıch nebo rovn´ ych ˇc´ıslu 30 tˇri r˚ uzn´a ˇc´ısla tak, aby jejich souˇcet byl roven sud´emu ˇc´ıslu? 5
Variace s opakov´ an´ım 1) Urˇcete poˇcet vˇsech pˇrirozen´ ych pˇeticifern´ ych ˇc´ısel, kter´a lze sestavit z cifer 0, 1, 2, 3, 4, 5, 6, mohou-li se v sestaven´em ˇc´ısle cifry opakovat. 2) Uvaˇzujme vˇsechna cel´a nez´aporn´a ˇc´ısla menˇs´ı neˇz 106 . Urˇcete, kter´ ych je v´ıce, tˇech, kter´a ve sv´em z´ apisu neobsahuj´ı ˇz´adnou cifru 9, nebo tˇech, v jejichˇz z´apise je alespoˇ n jednou cifra 9 pouˇzita? 3) Kolik pˇrirozen´ ych ˇc´ısel menˇs´ıch neˇz 105 lze zapsat pouze pomoc´ı cifer 7 a 9? 4) Urˇcete poˇcet vˇsech ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel vytvoˇren´ ych z cifer 1, 2, 3, 4, 5, 6, kter´ a jsou dˇeliteln´a ˇctyˇrmi. 5) Urˇcete poˇcet vˇsech ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel vytvoˇren´ ych z cifer 0, 1, 2, 3, 4, 5, kter´ a jsou dˇeliteln´a ˇctyˇrmi. 6) Urˇcete poˇcet vˇsech ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel sestaven´ ych z cifer 0, 1, 2, 3, 4, 5, kter´a jsou menˇs´ı neˇz 3 000. Permutace s opakov´ an´ım 1) Kolik anagram˚ u lze vytvoˇrit z p´ısmen slova MATEMATIKA? 2) Urˇcete poˇcet vˇsech anagram˚ u, kter´e lze vytvoˇrit z p´ısmen slova PARABOLA, poˇzadujeme-li, aby se ve vytvoˇren´em anagramu pravidelnˇe stˇr´ıdaly samohl´asky a souhl´asky. 3) Urˇcete poˇcet vˇsech anagram˚ u, kter´e lze z´ıskat z p´ısmen slova ROKOKO, nesmˇej´ı-li v takov´em anagramu st´at vˇsechna tˇri p´ısmena O vedle sebe. 4) Urˇcete poˇcet vˇsech pˇrirozen´ ych ˇc´ısel vˇetˇs´ıch neˇz a) 7 · 105 , b) 4 · 105 , kter´a lze sestavit z cifer 2, 4, 7, m´ a-li se cifra 2 v kaˇzd´em z nich vyskytovat dvakr´at, cifra 4 jedenkr´at a cifra 7 tˇrikr´at. 5) Urˇcete poˇcet vˇsech anagram˚ u, kter´e lze vytvoˇrit z p´ısmen slova INGREDIENT. Kolik z nich zaˇc´ın´ ai konˇc´ı samohl´askou? 6) Uchazeˇc o pˇrijet´ı na vysokou ˇskolu mus´ı u ´spˇeˇsnˇe sloˇzit vˇsechny ˇctyˇri zkouˇsky. Za kaˇzdou u ´spˇeˇsnˇe vykonanou zkouˇsku z´ısk´a 2, 3 nebo 4 body. Pro pˇrijet´ı mus´ı dos´ahnout alespoˇ n 13 bod˚ u. Kolika zp˚ usoby m˚ uˇze sloˇzit zkouˇsky, aby byl pˇrijat? Kombinace s opakov´ an´ım 1) V pap´ırnictv´ı maj´ı 12 r˚ uzn´ ych pohled˚ u. Kolika zp˚ usoby m˚ uˇzeme nakoupit 8 pohlednic, kter´e hodl´ ame odeslat na r˚ uzn´e adresy, proto m˚ uˇze b´ yt nˇekter´ y druh pohlednic zakoupen ve v´ıce exempl´aˇr´ıch? 2) Mezi 6 dˇet´ı rozdˇelujeme 15 stejn´ ych m´ıˇck˚ u. a) Urˇcete poˇcet vˇsech moˇzn´ ych rozdˇelen´ı. b) Urˇcete poˇcet vˇsech rozdˇelen´ı, pˇri kter´ ych kaˇzd´e d´ıtˇe dostane alespoˇ n jeden m´ıˇcek. 3) 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? 4) V lah˚ udk´aˇrstv´ı maj´ı k´avu pˇeti r˚ uzn´ ych druh˚ u. Kolika zp˚ usoby je moˇzn´e prov´est n´akup 12 bal´ıˇck˚ u k´ avy? Kolika zp˚ usoby je to moˇzn´e, poˇzadujeme-li, aby v n´akupu bylo alespoˇ n po dvou bal´ıˇcc´ıch kaˇzd´eho druhu k´avy? 5) Kolika zp˚ usoby lze do 9 r˚ uzn´ ych pˇrihr´adek rozm´ıstit 7 b´ıl´ ych a 2 ˇcern´e koule a) nesm´ı-li ˇz´adn´a pˇrihr´adka z˚ ustat pr´azdn´a, b) mohou-li nˇekter´e pˇrihr´adky z˚ ustat pr´azdn´e. 6) Pro libovoln´e pevn´e n ∈ N urˇcete poˇcet vˇsech ˇreˇsen´ı rovnice x1 + x2 + · · · + xk = n a) v mnoˇzinˇe cel´ ych nez´aporn´ ych ˇc´ısel, b) v mnoˇzinˇe pˇrirozen´ ych ˇc´ısel. 7) Pro libovoln´e pevn´e n ∈ N urˇcete poˇcet vˇsech ˇreˇsen´ı rovnice x1 + x2 + · · · + xk ≤ n 6
a) v mnoˇzinˇe cel´ ych nez´aporn´ ych ˇc´ısel, b) v mnoˇzinˇe pˇrirozen´ ych ˇc´ısel. 8) Pro libovoln´e pevn´e n ∈ N urˇcete poˇcet vˇsech ˇreˇsen´ı rovnice x1 + x2 + · · · + xk < n a) v mnoˇzinˇe cel´ ych nez´aporn´ ych ˇc´ısel, b) v mnoˇzinˇe pˇrirozen´ ych ˇc´ısel. Dalˇ s´ı u ´ lohy 1) V kup´e je 10 m´ıst a 9 pasaˇz´er˚ u. Tˇri z nich chtˇej´ı sedˇet ve smˇeru j´ızdy, ostatn´ım ˇsesti, mezi nˇeˇz patˇr´ı i Venouˇsek s maminkou, je to jedno - aˇz na to, ˇze Venouˇsek chce sedˇet u okna a vedle maminky. Kolika zp˚ usoby se mohou cestuj´ıc´ı usadit, aby vˇsichni byli spokojeni? 2) Jak se zmˇen´ı v´ ysledek pˇredchoz´ı u ´lohy, pˇredpokl´ad´ame-li, ˇze v kup´e je a) o jednu osobu bez n´arok˚ u v´ıce (je tam tedy 10 cestuj´ıc´ıch), b) o dvˇe osoby bez n´arok˚ u m´enˇe (je tam tedy 7 cestuj´ıc´ıch)? 3) 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. 4) V kolika anagramech vytvoˇren´ ych z p´ısmen slova LOKOMOTIVA nestoj´ı ˇz´adn´a dvˇe p´ısmena O vedle sebe? Kolik z tˇechto anagram˚ u bude m´ıt souhl´asky v abecedn´ım poˇr´adku? 5) Ke kulat´emu stolu, u nˇejˇz je m + n ˇzidl´ı, m´ame rozesadit m muˇz˚ u a n ˇzen tak, aby ˇz´adn´ı dva muˇzi nesedˇeli vedle sebe. Kolika zp˚ usoby to lze uˇcinit? 6) Kolika zp˚ usoby lze z karetn´ı hry (po osmi kart´ach ˇctyˇr barev) vybrat ˇsest karet tak, aby mezi nimi byly karty ˇctyˇr barev? 7) Je d´ano rˇcen´ı OKO ZA OKO, ZUB ZA ZUB. a) Kolika zp˚ usoby z nˇej m˚ uˇzeme vybrat nˇekolik p´ısmen, nez´aleˇz´ı-li na jejich poˇrad´ı? b) Kolika zp˚ usoby z nˇej m˚ uˇzeme vybrat tˇri p´ısmena, nez´aleˇz´ı-li na jejich poˇrad´ı? c) Kolika zp˚ usoby z nˇej m˚ uˇzeme vybrat tˇri p´ısmena, pokud na jejich poˇrad´ı z´aleˇz´ı? 8)Kolika zp˚ usoby lze rozestavˇet p´ısmena slova KOLENA tak, aby v kaˇzd´em anagramu n´asledovaly samohl´asky v abecedn´ım poˇr´adku? 9) Stav´ıme do ˇrady 6 Angliˇcan˚ u, 7 Francouz˚ u a 10 Turk˚ u tak, aby kaˇzd´ y Angliˇcan st´al mezi Turkem a Francouzem a d´ale nikde nest´ali vedle sebe Francouz a Turek. Kolika zp˚ usoby to m˚ uˇzeme udˇelat? ˇ ste stejn´ 10) Reˇ yu ´kol pro pˇr´ıpad pˇeti Angliˇcan˚ u, sedmi Francouz˚ u a deseti Turk˚ u. 11) Kolika zp˚ usoby lze rozestavˇet p´ısmena v kouzeln´e formuli ABRAKA DABRA tak, aby ˇz´ adn´ a dvˇe p´ısmena A nest´ala vedle sebe? 12) Kolik anagram˚ u lze z´ıskat z p´ısmen slova TERAKOTA tak, aby a) se pravidelnˇe stˇr´ıdaly samohl´asky a souhl´asky, b) ˇz´adn´e dvˇe samohl´asky nest´aly vedle sebe? 13) Krotitel ˇselem chce pˇriv´est do man´eˇze cirkusu z´astup pˇeti lv˚ u a ˇctyˇr tygr˚ u, pˇriˇcemˇz nesmˇej´ı j´ıt ˇz´ adn´ı dva tygˇri bezprostˇrednˇe za sebou. Kolika zp˚ usoby m˚ uˇze ˇselmy seˇradit? 14) Na poliˇcce stoj´ı 14 knih. Kolika zp˚ usoby z nich m˚ uˇzeme vybrat ˇsest knih, z nichˇz ˇz´adn´e dvˇe nestoj´ı vedle sebe? 15) Kolika zp˚ usoby lze vybrat z karetn´ı hry (po osmi kart´ach ˇctyˇr barev) 8 karet tak, aby a) mezi nimi nebylo ˇz´adn´e eso, b) mezi vybran´ ymi kartami bylo pikov´e eso, c) mezi vybran´ ymi kartami bylo alespoˇ n jedno eso, d) mezi vybran´ ymi kartami byla alespoˇ n dvˇe esa, e) bylo vybr´ano po dvou kart´ach od kaˇzd´e barvy, f) vybran´e karty byly vˇsech ˇctyˇr barev, g) byly vybr´any karty pr´avˇe tˇr´ı r˚ uzn´ ych barev, h) byly vybr´any karty alespoˇ n tˇr´ı r˚ uzn´ ych barev. 7
16) Kolika zp˚ usoby je moˇzn´e rozdˇelit 8 chlapc˚ u a 4 d´ıvky na dvˇe ˇsestiˇclenn´a volejbalov´a druˇzstva tak, aby v kaˇzd´em druˇzstvu bylo alespoˇ n jedno dˇevˇce? 17) Kolika zp˚ usoby lze vybrat 4 p´ısmena ze slova BARBAR, a) nepˇrihl´ıˇz´ıme-li k jejich poˇrad´ı, b) bereme-li v u ´vahu i jejich poˇrad´ı? 18) Kolik anagram˚ u lze vytvoˇrit z p´ısmen slova ABECEDA tak, aby v kaˇzd´em anagramu souhl´ asky n´ asledovaly v abecedn´ım poˇr´adku? 19) Kolik anagram˚ u lze vytvoˇrit z p´ısmen slova BATOLE tak, aby v kaˇzd´em anagramu jak souhl´ asky tak samohl´asky n´asledovaly v abecedn´ım poˇr´adku? 20) Kolik anagram˚ u lze vytvoˇrit z p´ısmen slova STUDNA tak, aby v kaˇzd´em anagramu mezi dvˇema samohl´askami st´aly dvˇe souhl´asky? ´ Ulohy o cifern´ ych z´ apisech 1)Urˇcete poˇcet vˇsech ˇsesticifern´ ych pˇrirozen´ ych ˇc´ısel, kter´a jsou sestavena ze tˇr´ı sud´ ych a tˇr´ı lich´ ych cifer. 2) Urˇcete, kolik r˚ uzn´ ych deseticifern´ ych pˇrirozen´ ych ˇc´ısel lze zapsat uˇzit´ım cifer 1, 2, 3 za pˇredpokladu, ˇze cifra 3 bude uˇzita v kaˇzd´em ˇc´ısle pr´avˇe dvakr´at. Kolik z tˇechto ˇc´ısel je dˇeliteln´ ych dev´ıti? 3) Kolik ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel lze sestavit z cifer ˇc´ısla 123 124? 4) Urˇcete poˇcet vˇsech ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel, kter´a maj´ı cifern´ y souˇcet 4. 5) Urˇcete souˇcet vˇsech ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel, kter´a jsou vytvoˇrena z cifer 1, 2, 3, 4. Rozliˇste dva pˇr´ıpady: a) vˇsechny cifry kaˇzd´eho ˇc´ısla jsou r˚ uzn´e, b) cifry se v libovoln´em z uvaˇzovan´ ych ˇc´ısel mohou opakovat. 6) Urˇcete souˇcet vˇsech pˇeticifern´ ych pˇrirozen´ ych ˇc´ısel sestaven´ ych z cifer 0, 1, 2, 3, 4, jestliˇze se v ˇz´ adn´em ˇc´ısle ˇz´adn´a cifra neopakuje. 7) Urˇcete poˇcet vˇsech ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel, k jejichˇz z´apisu je uˇzito pr´avˇe dvou r˚ uzn´ ych cifer. 8) Urˇcete poˇcet vˇsech pˇeticifern´ ych pˇrirozen´ ych ˇc´ısel, kter´a obsahuj´ı pr´avˇe tˇri sud´e cifry. 9) Urˇcete poˇcet vˇsech 2n-cifern´ ych pˇrirozen´ ych ˇc´ısel sloˇzen´ ych z n sud´ ych a n lich´ ych cifer. 10) Kolik lich´ ych pˇrirozen´ ych ˇc´ısel lze sestavit z cifer ˇc´ısla 3 694, lze-li kaˇzd´e cifry uˇz´ıt nejv´ yˇse jednou? 11) Kolik existuje ˇsesticifern´ ych pˇrirozen´ ych ˇc´ısel, kter´a maj´ı sud´ y cifern´ y souˇcet? 12) Kolik existuje ˇsesticifern´ ych pˇrirozen´ ych ˇc´ısel, jejichˇz cifern´ y souˇcet je dˇeliteln´ y deseti? 13) Uvaˇzujme vˇsechna osmicifern´a pˇrirozen´a ˇc´ısla zapsan´a pomoc´ı cifer 1, 2, 3, 4, v jejichˇz z´apise je kaˇzd´ a z cifer 3 a 4 uˇzita pr´avˇe dvakr´at. a) Kolik je vˇsech tˇechto ˇc´ısel? b) Kolik z nich je dˇeliteln´ ych ˇctyˇrmi? c) Kolik z nich je dˇeliteln´ ych tˇremi? 14) Kolik ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel lze sestavit z cifer ˇc´ısla 123 123? 15) Kolik pˇeticifern´ ych pˇrirozen´ ych ˇc´ısel lze sestavit z cifer ˇc´ısla 12 334 444? 16) Kolik ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel lze sestavit z cifer ˇc´ısla 3 332 210? 17) Kolik pˇeticifern´ ych pˇrirozen´ ych ˇc´ısel lze sestavit z cifer ˇc´ısla 11 223 334, poˇzadujeme-li nav´ıc, aby tˇri cifry 3 nen´asledovaly bezprostˇrednˇe za sebou? 18) Urˇcete poˇcet vˇsech ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel s cifern´ ym souˇctem 5. 19) Urˇcete poˇcet vˇsech ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel sestaven´ ych z cifer 0, 1, 2, 3, 4, kter´a jsou dˇeliteln´ a dev´ıti, mohou-li se v tˇechto ˇc´ıslech cifry opakovat. 8
20) Urˇcete souˇcet vˇsech trojcifern´ ych pˇrirozen´ ych ˇc´ısel, kter´a jsou vytvoˇrena z cifer 1, 2, 3, 4, 5, 6, kde: a) vˇsechny cifry kaˇzd´eho ˇc´ısla jsou r˚ uzn´e, b) cifry se v libovoln´em z uvaˇzovan´ ych ˇc´ısel mohou opakovat. 21) Urˇcete souˇcet vˇsech ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel, kter´a z´ısk´ame vˇsemi moˇzn´ ymi z´amˇenami poˇrad´ı cifer ˇc´ısel: a) 1 225, b) 1 333, c) 1 144. 22) Urˇcete souˇcet vˇsech ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel, kter´a jsou vytvoˇrena z cifer 0, 1, 2, 3, 4, 5 v tˇechto dvou pˇr´ıpadech: a) vˇsechny cifry kaˇzd´eho ˇc´ısla jsou r˚ uzn´e, b) cifry se v libovoln´em z uvaˇzovan´ ych ˇc´ısel mohou opakovat. 23) Urˇcete souˇcet vˇsech sud´ ych ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel sestaven´ ych z cifer 0, 1, 2, 3, 4, 5, mohou-li se v tˇechto ˇc´ıslech cifry opakovat. 24) Urˇcete poˇcet vˇsech pˇeticifern´ ych pˇrirozen´ ych ˇc´ısel sestaven´ ych z pr´avˇe dvou r˚ uzn´ ych cifer. 25) Urˇcete poˇcet vˇsech sud´ ych ˇctyˇrcifern´ ych pˇrirozen´ ych ˇc´ısel sestaven´ ych z pr´avˇe dvou r˚ uzn´ ych cifer. Rozdˇ elov´ an´ı do pˇ rihr´ adek 1) Mezi tˇri nejlepˇs´ı ˇreˇsitele matematick´e olympi´ady je tˇreba rozdˇelit kniˇzn´ı odmˇeny - 6 r˚ uzn´ ych knih. Kolika zp˚ usoby je to moˇzn´e udˇelat, m´a-li v´ıtˇez obdrˇzet 3 knihy, druh´ y v poˇrad´ı 2 knihy a tˇret´ı jednu knihu? 2) Turnaje v judu se u ´ˇcastn´ı 16 soupeˇr˚ u. a) Kolika zp˚ usoby z nich lze vylosovat dvojice soupeˇr˚ u pro prvn´ı kolo turnaje? b) Urˇcete poˇcet vˇsech moˇzn´ ych v´ ysledk˚ u prvn´ıho kola turnaje. 3) Urˇcete poˇcet rozdˇelen´ı pˇeti fotografi´ı do ob´alek, kdy ve dvou ob´alk´ach m´a b´ yt po dvou fotografi´ıch a v jedn´e ob´alce jedna fotografie. 4) Spoleˇcnost deseti manˇzelsk´ ych p´ar˚ u se chyst´a na proj´ıˇzd’ku na lod’k´ach, a proto se rozdˇeluj´ı na 5 skupin po ˇctyˇrech osob´ach. a) Kolika zp˚ usoby se mohou rozdˇelit tak, aby na kaˇzd´e lod’ce byli dva muˇzi a dvˇe ˇzeny? b) V kolika z tˇechto pˇr´ıpad˚ u bude jist´ y pan X na lod’ce se svou ˇzenou? c) V kolika z tˇechto pˇr´ıpad˚ u budou jist´ı dva p´anov´e X, Y na lod’ce se sv´ ymi ˇzenami? 5) Kolika zp˚ usoby lze rozdat 52 karet (po 13 kart´ach ˇctyˇr r˚ uzn´ ych barev) ˇctyˇrem hr´aˇc˚ um tak, aby kaˇzd´ y dostal po tˇrech kart´ach tˇr´ı r˚ uzn´ ych barev a 4 karty ˇctvrt´e barvy? 6) Kolika zp˚ usoby lze sestavit z 24 r˚ uzn´ ych p´ısmen 6 ˇctyˇrp´ısmenkov´ ych slov“, uˇzijeme-li kaˇzd´e p´ısmeno ” pr´ avˇe jednou? 7) Pˇri karetn´ı hˇre preferans dost´av´a kaˇzd´ y ze tˇr´ı hr´aˇc˚ u po 10 kart´ach ze 32 karet a dvˇe karty z˚ ust´ avaj´ı. Urˇcete poˇcet vˇsech moˇznost´ı pro rozd´an´ı karet. 8) Hraj´ı-li 3 hr´aˇci karetn´ı hru mari´aˇs, rozd´av´a se 32 karet tak, ˇze prvn´ı hr´aˇc dostane 12 karet, ostatn´ı dva po 10 kart´ach. Pˇred zaˇc´atkem hry prvn´ı hr´aˇc 2 karty odkl´ad´a, takˇze hru zaˇc´ınaj´ı vˇsichni s 10 kartami. a) Kolika zp˚ usoby je moˇzn´e rozdat karty? b) Kolik je vˇsech moˇznost´ı pro rozdˇelen´ı karet pˇred zaˇc´atkem hry? 9) Kolika zp˚ usoby lze rozdˇelit 30 lid´ı na 3 stejnˇe poˇcetn´e skupiny? Kolika zp˚ usoby je moˇzn´e je rozdˇelit na 10 tˇr´ıˇclenn´ ych skupin? 10) kolika zp˚ usoby lze rozdˇelit 3n r˚ uzn´ ych knih mezi 3 osoby tak, aby vˇsechny osoby dostaly t´ yˇz poˇcet knih? 11) Je d´ano n(n+1) r˚ uzn´ ych pˇredmˇet˚ u, kter´e rozdˇelujeme do n skupin S1 , S2 , . . . , Sn tak, ˇze ve skupinˇe 2 Si je pr´avˇe i pˇredmˇet˚ u, i = 1, 2, . . . , n, poˇrad´ı pˇredmˇet˚ u ve skupin´ach nen´ı podstatn´e. Urˇcete poˇcet vˇsech moˇzn´ ych rozdˇelen´ı, a) je-li poˇrad´ı skupin podstatn´e, b) pokud na poˇrad´ı skupin nez´aleˇz´ı. 9
12) Urˇcete poˇcet vˇsech rozdˇelen´ı n r˚ uzn´ ych knih do k bal´ıˇck˚ u, jestliˇze poˇrad´ı bal´ıˇck˚ u nen´ı podstatn´e a plat´ı-li a) n = 10, k = 5, v kaˇzd´em bal´ıˇcku jsou 2 knihy, b) n = 9, k = 3, v kaˇzd´em bal´ıˇcku jsou 3 knihy, c) n = 9, k = 5, ve 4 bal´ıˇcc´ıch je po 2 knih´ach a v jednom je jedna kniha.
10
