Matematyka dyskretna II Zbior zadań Bobiński.pdf

(265 KB) Pobierz
3931469 UNPDF
MatematykadyskretnaII
Zbiórzada«
GrzegorzBobi«ski
Wst¦p
Niniejszyzbiórzada«jestowocemprowadzonychprzezemniewlatach1999–
2002¢wicze«zprzedmiotu„MatematykaDyskretnaII”naIIrokuinforma-
tykinaWydzialeMatematykiiInformatykiUniwersytetuMikołajaKoper-
nikawToruniu.Stanowionuzupełnienieprzygotowanychprzezdr.Witolda
Kra±kiewiczanotatekzwykładuztegoprzedmiotu.Zadaniazamieszczonew
zbiorzepochodz¡znast¦puj¡cychpozycjipo±wi¦conychkombinatoryce:
1.VictorBryant,Aspectsofcombinatorics,Awide-rangingintroduction,
CambridgeUniversityPress,Cambridge,1993;
2.PeterCameron,Combinatorics:topis,techniques,algorithms,Cam-
bridgeUniversityPress,Cambridge,1994;
3.ZbigniewPalka,AndrzejRuci«ski,Wykładyzkombinatoryki,cz¦±¢1,
WydawnictwaNaukowo-Techniczne,Warszawa1998;
4.K.A.Pybnikob(red),Kombinatorny analiz,Zadaqiiupra ne-
ni ,Nauka,Glavna redakci fiziko-matematiqesko literatu-
ry,Moskva,1982.
Zbiórzawieratak»ezadaniazaproponowaneprzezdr.AndrzejaDaszkiewicza,
dr.WitoldaKra±kiewiczaorazmojegowłasnegoautorstwa.
1
Rozdział1
Zadania
1.1Podstawowepoj¦cia
1. Nailesposobówztalii52kartmo»nawybra¢10karttak,abybył
w±ródnichdokładniejedenas?
2. Nailesposobówztalii52kartmo»nawybra¢10karttak,abybył
w±ródnichconajmniejjedenas?
3. Nailesposobówztalii52kartmo»nawybra¢6karttak,abybyły
w±ródnichkartywszystkichkolorów?
4. Nailesposobówspo±ródnmał»e«stwmo»nawybra¢jedn¡kobiet¦i
jednegom¦»czyzn¦,którzynies¡mał»e«stwem?
5. Sadzamynosóbprzyokr¡głymstole.Dwarozsadzeniauwa»amyza
identyczne,je±liwobuprzypadkachka»dyczłowiekmatychsamychs¡sia-
dów.Ilejestmo»liwychsposobówrozsadzenia?
6. Nailesposobówmo»naposadzi¢przyokr¡głymstolenkobietin
m¦»czyzntak,aby»adnedwieosobytejsamejpłciniesiedziałyoboksiebie?
Dwarozsadzeniauwa»amyzaidentyczne,je±liwobuprzypadkachka»dy
człowiekmatychsamychs¡siadów.
7. Nailesposobówmo»narozmie±ci¢knierozró»nialnychkulwnponu-
merowanychszufladach,przyzało»eniu,»ewka»dejszufladziemo»eznale¹¢
si¦conajwy»ejjednakula?
8. Nailesposobówmo»narozmie±ci¢krozró»nialnychkulwnponume-
rowanychszufladach,przyzało»eniu,»ewka»dejszufladziemo»eznale¹¢si¦
conajwy»ejjednakula?
9. Ilejestpermutacjizbioru{1,...,n},wktórej»adnedwies¡siednie
liczbynies¡parzyste?
2
1.2Metodabijektywna
Konstruuj¡codpowiedniebijekcjeudowodni¢nast¦puj¡cerówno±ci.
(1)
k
n
k
=n
n−1
k−1
n
k
X
n
(2)
k
=n2 n−1
k=1
k 2 n
k
X
n
(3)
=n(n−1)2 n−2 +n2 n−1
k=1
k 2 n
k
n
n−k
=n 2 2n−2
n−1
X
(4)
k=1
n
l
n−l
k−l
n
k
X
k
(5)
=
2 k
l=0
m
l
n
k−l
m+n
k
X
k
(6)
=
l=0
n
2k
n
2k+1
X
= X
k0
(7)
k0
k
m
n+1
m+1
X
n
(8)
=
k=m
n
k
X
(9)
(m−1) n−k =m n
k=0
n+1
2
2
X
n
(10)
k 3 =
k=1
1.3Reguławł¡czaniaiwył¡czania
10. Ilejestliczbcałkowitychdodatnichniewi¦kszychni»10000podziel-
nychprzynajmniejprzezjedn¡zliczb2,3,5?
11. Ilejestcałkowitoliczbowychrozwi¡za«równania
x 1 +···+x 6 =30
spełniaj¡cychponi»szewarunki?
3
n
n
(a)0x i 10,i=1,...,6.
(b)−10x i 20,i=1,...,6.
(c)x 1 5,x 2 10,x 3 15,x 4 20,x i 0,i=1,...,6.
12. Nailesposobówztalii52kartmo»nawybra¢5karttak,abyotrzy-
ma¢conajmniejjednegoasa,conajmniejjednegokrólaiconajmniejjedn¡
dam¦?
13. Ilejestpermutacjizbioru{1,2,3,4,5,6,7,8,9,10},wktórychpierw-
szaliczbajestwi¦kszaod2,aostatniajestmniejszaod9?
14. Ilejestci¡gówdługo±cin,n3,zło»onychzcyfr0,1,...,9takich,
»eka»dazcyfr1,2,3wyst¦pujewka»dymzci¡gówconajmniejraz?
15. Ilejestmacierzyzero-jedynkowychowymiarachnnan,wktórych
conajmniejjedenwierszjestzerowy?
16. Jakiejestprawdopodobie«stwo,»eporozdaniukartdobryd»austa-
lonygraczw±ródotrzymanychkartb¦dziemiałczterykartytejsamejwyso-
ko±ci?
17. Obliczprawdopodobie«stwo,»erzucaj¡cdziesi¦¢razydwomakost-
kamidogryuzyskamywszystkiepary{i,i},gdziei=1,...,6.
18. Przyokr¡głymstolesadzamynmał»e«stw,naprzemiankobiet¦i
m¦»czyzn¦.Jakiejestprawdopodobie«stwo,»e»adnemał»e«stwonieb¦dzie
siedziałooboksiebie?
1.4Rekurencja
19. Znale¹¢jawnewzorydlaci¡gówspełniaj¡cychponi»szewarunkire-
kurencyjne.
(a)a n+2 =5a n+1 −6a n ,a 0 =2,a 1 =5.
(b)a n+2 =a n+1 −a n ,a 0 =0,a 1 =1.
(c)a n+3 =2a n+2 +a n+1 −2a n ,a 0 =0,a 1 =1,a 2 =9.
20. Znale¹¢jawnewzorydlaci¡gówspełniaj¡cychponi»szewarunkire-
kurencyjne.
(a)a n+1 −2a n =n 2 +n+2,a 0 =0.
(b)a n+2 +2a n+1 −3a n =1,a 0 =0,a 1 =1.
4

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin