Typick´e pˇr´ıklady pro z´apoˇctov´e p´ısemky DiM 470-2301 (Kov´aˇr, Kov´aˇrov´a, Kubesa) (verze: January 6, 2022) 1
4 V´ ybˇ ery s opakov´ an´ım
4.1. Kolik existuje r˚uzn´ych registraˇcn´ıch znaˇcek automobil˚u v Severomoravsk´em kraji? (registraˇcn´ı znaˇcka je tvaru ?T? ????, kde ? jsou ˇc´ıslice).
Znaˇcka obsahuje uspoˇr´adan´ych ˇsest ˇc´ıslic 0 aˇz 9 s moˇznost´ı opakov´an´ı. V∗(10,6) = 106.
4.2. Na ˇcerpac´ı stanici je v ˇradˇe 12 stoˇz´ar˚u a 12 vlajek, 3 modr´e, 2 zelen´e, 4 ˇcerven´e a 3 ˇzlut´e. Kolika r˚uzn´ymi zp˚usoby lze tyto vlajky um´ıstit na stoˇz´ary? Je moˇzn´e, aby kaˇzd´y den v pr˚ubˇehu 700 let bylo zavˇeˇsen´ı jin´e neˇz dny ostatn´ı?
Jedn´a se o uspoˇr´adan´y v´ybˇer 12 vlajek ze 4 r˚uzn´ych barev, pˇriˇcemˇz poˇcet opakov´an´ı je pˇredeps´an. Poˇcet takov´ych v´ybˇer˚u je poˇcet permutac´ı s opakov´an´ım.
P∗(3,2,4,3) = (3 + 2 + 4 + 3)!
3!2!4!3! = 12!
4!(3!)22! = 12·11·10·9·8·7·6·5
6·6·2 = 11·10·9·8·7·5 = 277 200.
D´ale v´ıme, ˇze 277200/365 .
= 759, a tedy by byla moˇzn´a r˚uzn´a zavˇeˇsen´ı kaˇzd´y den po dobu 700 let.
Dokonce zapoˇc´ıt´ame-li pˇrestupn´e roky, m˚uˇzeme ˇr´ıci ˇze rok m´a m´enˇe neˇz 365,25 dne (ne kaˇzd´e 4 roky je pˇrestupn´y rok). Potom 277200/365,25 >758, a tedy by byla moˇzn´a r˚uzn´a zavˇeˇsen´ı kaˇzd´y den po dobu delˇs´ı neˇz 700 let.
4.3. Kolik existuje takov´ych anagram˚u slov KUALA LUMPUR (vˇcetnˇe mezery), kter´e obsahuj´ı dvˇe slova?
Slova obsahuj´ı 1 mezeru, 2A, 1K, 2L 1M, 1P, 1R a 3U. Jedn´a se o uspoˇr´adan´y v´ybˇer dvan´acti p´ısmen s pˇredepsan´ym poˇctem opakov´an´ı – permutace s opakov´an´ım. Vˇsech anagram˚u je
P∗(1,2,1,2,1,1,1,3) = 12!
(2!)2(3!) = 12·11·10·9·8·7·6·5·4·3·2·1
24 = 12·11·10·9·7·6·5·4·2 = 19 958 400.
Mezeru na zaˇc´atku obsahuje P∗(2,1,2,1,1,1,3) = 11!
(2!)2(3!) = 11·10·9·8·7·6·5·4·3·2·1
24 = 11·10·9·7·6·5·4·2 = 1663200 z nich a na konci tak´e 1 663 200. Existuje celkem 19958400−2·1663200 = 16 632 000 moˇznost´ı.
4.4. Kolika zp˚usoby m˚uˇzeme vybrat ˇctyˇri pol´ıˇcka na klasick´e ˇsachovnici tak, aby ˇz´adn´a dvˇe vybran´a pol´ıˇcka neleˇzela v t´emˇze sloupci?
Ulohu budeme ˇ´ reˇsit jako sloˇzen´y v´ybˇer.
(i) Nejprve najdeme poˇcet vˇsech moˇznost´ı, jak vybrat ˇctyˇri sloupce. Jedn´a se neuspoˇr´adan´y v´ybˇer 4 sloupc˚u z 8. C(8,4) =(8
4
)= 84·7·3·6·2·5 = 2·7·5 = 70.
(ii) V kaˇzd´em ze ˇctyˇr vybran´ych sloupc˚u nyn´ı m˚uˇzeme zvolit jedno pol´ıˇcko libovolnˇe. Nyn´ı z´avis´ı, ve kter´em sloupci pol´ıˇcka vyb´ır´ame, proto se jedn´a o uspoˇr´adan´y v´ybˇer s opakov´an´ım.V∗(8,4) = 84, nebo ˇ
ctyˇri nez´avisl´e v´ybˇeryC(8,1)4=(8
1
)4
= 84 = 4096.
Celkem m´ame 70·4096 = 286 720 moˇznost´ı.
4.5. Kolika zp˚usoby m˚uˇzete napsat jeden´act jako souˇcet (a) pˇeti nez´aporn´ych cel´ych ˇc´ısel;
(b) ˇctyˇr kladn´ych cel´ych ˇc´ısel.
Pˇredpokl´ad´ame, ˇze rozliˇsujeme poˇrad´ı sˇc´ıtanc˚u, tj. napˇr´ıklad 3 + 1 + 4 + 0 + 3 = 11 a4 + 1 + 0 + 3 + 3 = 11 jsou r˚uzn´e souˇcty.
Poˇc´ıt´ame, jako rozdˇelen´ı jeden´acti jedniˇcek do pˇeti/ˇctyˇr pˇrihr´adek (pˇrihr´adky odpov´ıdaj´ı sˇc´ıtanc˚um) s moˇznost´ı opakov´an´ı.
(a) C∗(5,11) =(11+5−1
5−1
)=(15
4
)= 15·1424·13·12 = 15·7·13 = 1365 moˇznost´ı.
Typick´e pˇr´ıklady pro z´apoˇctov´e p´ısemky DiM 470-2301 (Kov´aˇr, Kov´aˇrov´a, Kubesa) (verze: January 6, 2022) 2 (b) nejprve pˇridˇel´ıme do kaˇzd´e pˇrihr´adky jednu jedniˇcku, aby byly nepr´azdn´e (celkem ˇctyˇri jedniˇcky) a
d´ale rozdˇelujeme 7 jedniˇcek:C∗(4,7) =(7+4−1
4−1
)=(10
3
)= 103··92·8 = 10·3·4 = 120 moˇznost´ı.
4.6. V n´apojov´em automatu se prod´avaj´ı tˇri druhy n´apoj˚u: Cola, Fanta a Sprite. Bˇehem pˇrest´avky bylo prod´ano ˇsest n´apoj˚u. Kolik je r˚uzn´ych moˇznost´ı, kter´e n´apoje byly prod´any?
Poˇc´ıt´ame jako neuspoˇr´adan´e v´ybˇery s opakov´an´ım – kombinace s opakov´an´ım.C∗(3,6) =(6+3−1
3−1
)=(8
2
)=
8·7 2 = 28.
4.7. Kolik existuje vˇsech zobrazen´ı 3-prvkov´e mnoˇziny do 5-prvkov´e?
Pro kaˇzd´y ze tˇr´ı prvk˚u vyb´ır´am obraz mezi 5 prvky s moˇznost´ı opakov´an´ı. Jedn´a se o uspoˇr´adan´y v´ybˇer s opakov´an´ım. V∗(5,3) = 53 = 125.
4.8. Chceme vedle sebe do ˇrady postavit 5 d´ıvek a 7 chlapc˚u, pˇriˇcemˇz nesm´ı vedle sebe st´at 2 d´ıvky (st´ale mezi sebou ˇstˇebetaj´ı. Kolik m´ame moˇznost´ı?
Nejdˇr´ıve um´ıst´ıme do ˇrady 7 chlapc˚u tj. P(7) = 7! moˇznost´ı. Pak d´ıvky mus´ıme
”nacpat“ do osmi mezer mezi chlapci v ˇradˇe (vˇcetnˇe kraj˚u).
Do kaˇzd´e mezery m˚uˇze pˇrij´ıt nejv´yˇse jedna d´ıvka, jedn´a se o v´ybˇer pˇeti mezer z osmi moˇznost´ı. Osoby rozliˇsujeme, proto je v´ybˇer uspoˇr´adan´y bez opakov´an´ı. M´ame V(8,5) = (8−8!5)! moˇznost´ı rozm´ıstˇen´ı d´ıvek v mezer´ach. Celkov´y poˇcet moˇznost´ı je protoP(7)·V(8,5) = 7!8!3! = 7!·8·7·6·5·4 = 5040·56·120 = 33 868 800.
4.9. V sen´atu USA je 100 sen´ator˚u, pˇriˇcemˇz vˇzdy dva jsou ze stejn´eho st´atu Unie (USA m´a 50 st´at˚u).
Kolika zp˚usoby je moˇzn´e sestavit 4 ˇclenn´y v´ybor pro ochranu hospod´aˇrsk´e soutˇeˇze, kde mus´ı b´yti alespoˇn jedna dvojice sen´ator˚u z t´ehoˇz st´atu?
M´ame C(50,1) = 50 moˇznost´ı, jak vybrat jednu dvojici sen´ator˚u z jednoho st´atu Unie. Pro kaˇzdou takto vybranou dvojici existujeC(98,2) =(98
2
)moˇznost´ı, jak ji doplnit na ˇctyˇrˇclenn´y v´ybor. Jenˇze v´ybory, kter´e obsahuj´ı dvˇe dvojice ze dvou st´at˚u ((50
2
) moˇznost´ı), jsou zde zapoˇc´ıt´any vˇzdy dvakr´at. Celkov´y poˇcet je 50(98
2
)−(50
2
)= 50·49·97−25·49 = 237650−1225 = 236 425.
Jin´e ˇreˇsen´ı:
Je-li ve v´yboru pr´avˇe jedna dvojice z nˇejak´eho st´atu, tak tˇret´ıho ˇclena vybereme z 98 moˇznost´ı a ˇctvrt´eho z 96 moˇznost´ı. Nerozliˇsujeme poˇrad´ı tˇret´ıho a ˇctvrt´eho ˇclena a m´ame celkemC(50,1)C(98,1)C(96,1)·12 = 50·982·96 moˇznost´ı. Jsou-li ve v´yboru dvˇe dvojice ze dvou st´at˚u, jedn´a se o (50
2
) moˇznost´ı. Celkem m´ame 50·982·96 +(50
2
)= 50·49·96 + 25·49 = 235200 + 1225 = 236 425 moˇznost´ı.
Jin´e ˇreˇsen´ı:
V´ypoˇcet rozdˇel´ıme na dvˇe disjunktn´ı moˇznosti: 1) dva sen´atoˇri z jednoho st´atu a dalˇs´ı dva z r˚uzn´ych st´at˚u a 2) dvˇe dvojice sen´ator˚u ze stejn´ych st´at˚u.
Poˇcet v´ybˇer˚u prvn´ı moˇznosti spoˇc´ıt´ame jako sloˇzen´y v´ybˇer, kde nejprve st´at, ze kter´eho budou v komisi oba sen´atoˇri pak vybereme dva zb´yvaj´ıc´ı st´aty a nakonec z kaˇzd´eho vybran´eho st´atu vybereme jednoho ze dvou sen´ator˚u. Poˇcty jednotliv´ych podv´ybˇer˚u n´asob´ıme dle kombinatorick´eho pravidla souˇcinu. Dosta- neme C(50,1)C(49,2)C(2,1)C(2,1) =(50
1
)·(49
2
)·(2
1
)·(2
1
).
Poˇcet v´ybˇer˚u druh´e moˇznosti spoˇc´ıt´ame snadnˇeji, staˇc´ı vybrat dva st´aty, ze kter´ych budou v komisi oba sen´atoˇri. Poˇcet takov´ych v´ybˇer˚u jeC(50,2) =(50
2
).
Nakonec podle kombinatorick´eho pravidla souˇctu poˇcty obou disjunktn´ıch moˇznost´ı seˇcteme a dosta- neme (50
1
)·(49
2
)·(2
1
)·(2
1
)+(50
2
)= 50·492·48·2·2 +502·49 = 50·49·96 + 25·49 = 236 425.
4.10. Maty´aˇs m´a 7 b´ıl´ych dres˚u s ˇc´ısly 2,4,7,22,68,77 a 88. Tˇri z nich chce obarvit na ˇcerveno, dva na modro a dva chce nechat b´ıl´e. Kolika r˚uzn´ymi zp˚usoby to m˚uˇze prov´est?
Vybere ze sedmi dres˚u zcela libovolnˇe tˇri a ty obarv´ı ˇcervenˇe ((7
3
) moˇznost´ı). Ze zb´yvaj´ıc´ıch 4 dres˚u pak vybere libovoln´e dva ((4
2
) moˇznost´ı), kter´e obarv´ı modˇre a zbyl´e dva nech´a b´ıl´e. Celkovˇe tedy m´ame (7
3
)(4
2
)= 7·66·5 ·6 = 210 moˇznost´ı.
Jin´e ˇreˇsen´ı:
Seˇrad´ı si dresy dle ˇc´ısel od nejmenˇs´ıho po nejvˇetˇs´ı. Kaˇzd´e obarven´ı m˚uˇzeme charakterizovat
”slovem“ nebot’
obsahuje 3 ˇc, 2 m a 2 b. Napˇr´ıklad slovo
”bˇcˇcmbmˇc“, ˇr´ık´a, ˇze dvojka je b´ıl´a, ˇctyˇrka ˇcerven´a, sedmiˇcka
Typick´e pˇr´ıklady pro z´apoˇctov´e p´ısemky DiM 470-2301 (Kov´aˇr, Kov´aˇrov´a, Kubesa) (verze: January 6, 2022) 3 ˇ
cerven´a, dvacetdvojka modr´a, ˇsedes´atosmiˇcka b´ıl´a, sedmdes´atsedmiˇcka modr´a a osmdes´atosmiˇcka ˇcerven´a.
Tedy r˚uzn´ych obarven´ı je tolik, kolik je anagram˚u pˇredchoz´ıho slova. Proto m´ame P∗(3,2,2) = 3!2!2!7!
moˇznost´ı. Nyn´ı poˇcet moˇznost´ı jeP∗(3,2,2) = 7·62··52·4 = 210.
Vˇsimnˇete si, ˇze(7
3
)·(4
2
)= 3!4!7! ·2!2!4! = 3!2!2!7! .
4.11. Kolik je vˇsech ˇsesticifern´ych ˇc´ısel, kter´a jsou dˇeliteln´a pˇeti? ˇSesticifern´a ˇc´ısla samozˇrejmˇe nemohou zaˇc´ınat nulou.
C´ısla dˇˇ eliteln´a pˇetkou vˇzdy maj´ı posledn´ı cifru 0 nebo 5. S vyuˇzit´ım kombinatorick´eho pravidla souˇcinu dostaneme celkov´y poˇcet jako souˇcin tˇr´ı poˇct˚u podv´ybˇer˚u: prvn´ı cifry z 9 moˇznost´ı (ne 0), dalˇs´ı ˇctyˇri cifry z 10 moˇznost´ı a posledn´ı cifry ze dvou moˇznost´ı. V∗(9,1)V∗(10,4)V∗(2,1) = 9·104·2 = 180 000.
Jin´e ˇreˇsen´ı:
Uvˇedom´ıme si, ˇze se jedn´a o ˇsesticifern´a ˇc´ısla, kter´ych je 999999−100000 + 1. Dˇeliteln´e 5 je kaˇzd´e p´at´e, proto hledan´ych ˇc´ısel je (999999−100000 + 1)/5 = 900000/5 = 180000.
4.12. M´ame 8 stejn´ych kuliˇcek a ˇctyˇri r˚uzn´e barvy. Kaˇzdou kuliˇcku chceme natˇr´ıt pˇresnˇe jednou z tˇechto ˇ
ctyˇr barev. Kolik m´ame r˚uzn´ych moˇznost´ı?
Jedn´a se o neuspoˇr´adan´y v´ybˇer, kdy ze 4 barev vyb´ır´ame 8 kr´at. V´ybˇery se mohou opakovat, jedn´a se proto o kombinace s opakov´an´ım.C∗(4,8) =(8+4−1
4−1
)=(11
3
)= 165.
4.13. Mˇejme v´yraz (4x2−7y)9. Jak´y koeficient bude po umocnˇen´ı u ˇclenu x8y5? Z binomick´e vˇety (a+b)n =∑n
k=0
(n
k
)akbn−k plyne, ˇze pro ˇclen obsahuj´ıc´ıx8y5 = (x2)4y5 plat´ık = 4 a n−k= 9−4 = 5. Proto tento ˇclen po umocnˇen´ı dvojˇclenu (4x2+(−7y))9vypad´a n´asledovnˇe(9
4
)44x8(−7)5y5 a hledan´y koeficient tedy je(9
4
)44(−7)5= 126·256·(−16807) =−542126592.