Zbior.pdf

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.

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-

merowanychszuﬂadach,przyzało»eniu,»ewka»dejszuﬂadziemo»eznale¹¢

si¦conajwy»ejjednakula?

8. Nailesposobówmo»narozmie±ci¢krozró»nialnychkulwnponume-

rowanychszuﬂadach,przyzało»eniu,»ewka»dejszuﬂadziemo»eznale¹¢si¦

conajwy»ejjednakula?

9. Ilejestpermutacjizbioru{1,...,n},wktórej»adnedwies¡siednie

liczbynies¡parzyste?

1.2Metodabijektywna

Konstruuj¡codpowiedniebijekcjeudowodni¢nast¦puj¡cerówno±ci.

(1)

n−1

k−1

(2)

=n2 n−1

k=1

k 2 n

(3)

=n(n−1)2 n−2 +n2 n−1

k=1

k 2 n

n−k

=n 2 2n−2

n−1

(4)

k=1

n−l

k−l

(5)

2 k

l=0

k−l

m+n

(6)

l=0

2k+1

= X

(7)

n+1

m+1

(8)

k=m

(9)

(m−1) n−k =m n

k=0

n+1

(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?

(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.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: