Kategorie materiałów Ekonomia

Przedmiot: Matematyka Wróć do kategorii

Matematyka dyskretna - zadania

plik Pobierz Matematyka dyskretna - zadania.pdf

tabele w pliku do pobrania.

1. Indukcja matematyczna
Zadanie 1.1. Wykazac, ze

(...)


Zadanie 1.6. Pokazac indukcyjnie, ze kazdy n elementowy zbiór S posiada 2n podzbiorów (łacznie ze
zbiorem pustym i zbiorem S)
Zadanie 1.7. Wyznaczyc liczbe odcinków łaczacych n punktów na płaszczyznie, z których zadne trzy
nie sa współliniowe.
Zadanie 1.8. Udowodnic indukcyjnie, ze kazda kwote n ­ 4 zł mozna rozmienic na dwuzłotówki i
pieciozłotówki.
Zadanie 1.9. Jakie opłaty skarbowe mozemy uiscic majac tylko znaczki skarbowe o nominałach 3 zł
i 5 zł (znaczków mamy dowolnie duzo). Odpowiedz poprzec argumentem indukcyjnym.
Zadanie 1.10. Czekolada jest prostokatem złozonym z jednostkowych kwadracików. Zakładamy, ze
mozemy je łamac wzdłuz poziomych lub pionowych rowków, podobnie powstałe z przełamania kawałki
(które tez sa prostokatami). Zakładamy, ze w jednym ruchu dokonujemy jednego łamania tylko jednego
z kawałków czekolady. Ile ruchów potrzebujemy, aby podzielic czekolade na kwadraciki jednostkowe?
Trenujac na prawdziwej czekoladzie, dojsc do odpowiedzi, a otrzymany wynik udowodnic indukcyjnie.
Zadanie 1.11. * Oto prosta wersja gry NIM. Jest stos monet i n graczy. Kolejno zabieraja ze stosu
monety. W kazdym ruchu mozna zabrac 1, 2 lub 3 monety. Przegrywa ten, kto zabierze ostatnia
monete (ostatnie monety). Dla jakich n gre wygrywa gracz pierwszy, a dla jakich drugi? „Wygrywa
gre” oznacza, ze gracz ma strategie gwarantujaca wygrana, nawet przy bardzo dobrej grze przeciwnika.
Uwaga: w bardziej skomplikowanych wersjach tej gry stosów jest kilka.
1
2 POLITECHNIKA LUBELSKA – Informatyka I
2. Rekurencja I
Zadanie 2.1. Oblicz f(4), jesli f(0) = 1, f(1) = −1, a dla n ­ 1
(a) f(n + 1) = (f(n))2 + f(n − 1),
(b) f(n + 1) = 2f(n),
(c) f(n + 1) = 3f(n), gdy n jest parzyste i f(n + 1) = −3f(n), gdy n jest nieparzyste.
Zadanie 2.2. Podac rekurencyjna definicje ciagu (bn), w której bn jest wyrazone przy pomocy bn−1.
Prosze pamietac o warunkach poczatkowych.
(a) bn = 10n dla n ­ 0, (b) bn = 5 dla n ­ 1, (c) bn = −3n dla n ­ 0.
Zadanie 2.3. Zgadnac i udowodnic indukcyjnie wzor jawny na an, jezeli
(a) a1 = 3, a2 = −1, an = 2an−1 − an−2, dla n ­ 3.
(b) a0 = −2, an+1 = − 1
2an
, dla n ­ 0.
Ponadto w punkcie (a) wyznaczyc wzór jawny, korzystajac z odpowiedniego twierdzenia.
Zadanie 2.4. Udowodnic indukcyjnie, ze am ­ 2m dla wszystkich wyrazów ciagu (an), zdefiniowanego
rekurencyjnie:
a0 = 2, a1 = 3, an = an−1 + 2an−2, dla n ­ 2.
Nastepnie wysnaczyc wzór jawny, korzystajac z odpowiedniego twierdzenia.
Zadanie 2.5. Niech F(n) oznacza sume kwadratów pierwszych n liczb naturalnych. Podaj rekurencyjna
definicje F(n).
Zadanie 2.6. Dany jest ciag geometryczny o pierwszym wyrazie a i ilorazie q. Podaj rekurencyjna
definicje sumy n pierwszych wyrazów tego ciagu.
Zadanie 2.7. W pewnym miescie jeden człowiek zachorował na grype. Załózmy, ze kazda chora osoba
zaraza codziennie 4 zdrowe osoby. Ile bedzie chorych n dniach? Podaj rozwiazanie w postaci jawnej
i rekurencyjnej.
Zadanie 2.8. W pewnej populacji królików kazda para zdolna do rozrodu rodzi co miesiac dwie pary.
W chwili „zero” jest jedna nowonarodzona para. Zakładajac, ze króliki sa zdolne do rozmnazania po
trzech miesiacach od narodzin, podaj w postaci rekurencyjnej liczbe par królików po n miesiacach.
Zadanie 2.9. () Mamy gruby krazek sera i wykonujemy n (n ­ 0) ciec (róznym cieciom odpowiadaja
rózne płaszczyzny w przestrzeni) Chcemy otrzymac w ten sposób jak najwiecej kawałków sera.
a) Czy opłaca nam sie kroic równolegle ?
b) Na ile maksymalnie kawałków rozpadnie sie ser przy 4 cieciach ?
c) Wyznacz Pn – maksymalna liczbe kawałków sera, powstajacych po n cieciach.
3
3. Rekurencja II. Indukcja strukturalna.
Zadanie 3.1. Oprocentowanie lokat w banku wynosi 5% w skali roku. Bank proponuje dwa sposoby
gromadzenia kapitału:
1) Na poczatku wpłacamy 1000zł, odsetki doliczane sa do kapitału na koncu kazdego roku.
2) Na koniec kazdego roku wpłacamy po 100zł, odsetki tez sa doliczane do kapitału na koncu kazdego
roku (oczywiscie na koncu roku bank nie doliczy odsetek od 100zł, które własnie wpłacilismy).
Ile zgromadzimy pieniedzy na kazdej lokacie po n latach ? Prosze podac rozwiazanie rekurencyjne dla
kazdej osobno.
Na której lokacie zgromadzimy wiecej przez 30 lat ?
Zadanie 3.2. Podwójna wieza Hanoi składa sie z 2n krazków, po dwa krazki w kazdym z n rozmiarów.
Zasady przenoszenia takie jak na wykładzie: mamy trzy prety, nie mozna połozyc wiekszego krazka na
mniejszy. Ile ruchów trzeba co najmniej wykonac, by przeniesc wieze z jednego preta na drugi ?
Zadanie 3.3. Oto rekurencyjna definicja pewnego zbioru S.
1) ; 2 S, {1} 2 S, {2} 2 S, {3} 2 S.
2) Jezli A 2 S i B 2 S, to A [ B 2 S.
Jaki to zbiór ? Prosze wypisac wszystkie jego elementy.
Zadanie 3.4. Prosze podac definicje rekurencyjna zbioru A13 wszystkich liczb podzielnych przez 13.
Nastepnie udowodnic poprawnosc tej definicji, tzn.
a) pokazac indukcja strukturalna, ze wszystkie elementy Panstwa zbioru sa podzielne przez 13,
b) pokazac indukcyjnie, ze kazda liczba podzielna przez 13 nalezy do Panstwa zbioru.
Zadanie 3.5. Podaj definicje rekurencyjna zbioru liczb niepodzielnych przez 13.
Zadanie 3.6. Oto definicja rekurencyjna pewnego zbioru liczbowego A:
1) 9 2 A, 6 2 A.
2) Jesli x 2 A i y 2 A, to x + y 2 A.
Udowodnij, stosujac indukcje strukturalna, ze kazdy element A jest wielokrotnoscia 3.
Zadanie 3.7. Załózmy, ze hasło moze byc zbudowane z małych liter (24), cyfr (10) i kropek, ale dwie
kropki nie moga stac obok siebie. Jak wygenerowac wszystkie hasła długosci d rekurencyjnie ? Jak
zdefiniowac rekurencyjnie zbiór wszystkich haseł ?
Zadanie 3.8. Palindrom, to ciag, który czytany w obu kierunkach wyglada tak samo. Chcemy zdefiniowac
zbiór P ciagów binarnych, które sa palindromami. Czy ponizsza definicja jest poprawna ? Jezeli
nie – popraw ja.
1) (0) 2 P, (1) 2 P.
2) Jezeli a 2 P, to (0a0) 2 P i (1a1) 2 P.
(0a0) oznacza ciag a z doklejonymi zerami, analogicznie (1a1).
Zadanie 3.9. Chcemy zdefiniowac rekurencyjnie zbiór A wszystkich punktów kratowych płaszczyzny
(tzn. punktów o współrzednych całkowitych), dla których przynajmniej jedna współrzedna jest
parzysta. Czy ponizsza definicja jest poprawna ? Jezeli nie – podaj poprawna.
1) (0, 0), (0, 1), (1, 0) 2 A.
2) Jezeli (x, y) 2 A, to (x + 2, y + 2) 2 A i (x − 2, y − 2) 2 A.
Zadanie 3.10. Pokaz, stosujac indukcje strukturalna (i definicje rekurencyjna drzewa bin. z wykładu),
ze pełne drzewo binarne o wysokosci h ma ma przynajmniej 2h + 1 wierzchołków.
Zadanie 3.11. W pełnym drzewie binarnym liscmi nazywamy wszystkie wierzchołki, które nie maja
potomków. Zamiast tej definicji mozemy zastosowac definicje rekurencyjna zbioru lisci. Sprawdz, czy
ponizej zostało to dobrze zrobione. Jesli nie, popraw definicje rekurencyjna.
1) Drzewo o jednym wierzchołku nie ma lisci.
2) Jesli T1 i T2 sa pełnymi drzewami binarnymi, to zbiorem lisci drzewa T = T1 · T2 jest suma zbiorów
lisci T1 i T2.
Zadanie 3.12. Wpełnym drzewie binarnym wierzchołkami wewnetrznymi nazywamy wszystkie wierzchołki,
które maja potomków. Podaj rekurencyjna definicje zbioru wierzchołków wewnetrznych pełnego
drzewa binarnego.
Zadanie 3.13. Uzywajac indukcji strukturalnej pokaz, ze l(T), czyli liczba lisci w pełnym drzewie
binarnym T, jest o 1 wieksza niz liczba wewnetrznych wierzchołków T.
4 POLITECHNIKA LUBELSKA – Informatyka I
4. Prawa przeliczania
Zadanie 4.1. W konkursie startuje 20 skoczków. Ile jest mozliwosci zajecia trzech miejsc na podium ?
Zadanie 4.2. Rzucamy trzema kostkami do gry: zielona, czerwona i niebieska.
a) Ile róznych wyników mozemy otrzymac ?
b) W ilu wynikach wszystkie trzy liczby oczek sa rózne ?
c) W ilu wynikach nie uzyskamy tej samej liczby oczek na wszystkich trzech kostkach ?
Zadanie 4.3. Ile róznych haseł długosci d mozna wygenerowac, jezeli mamy do dyspozycji 24 litery
i 10 cyfr ?
Zadanie 4.4. Na ile sposobów mozna wybrac kolejno dwie karty z talii 52 kart tak, aby
a) pierwsza karta był as, a druga nie była dama,
b) pierwsza była karta koloru karo, a druga nie była dama ?
Zadanie 4.5. Ile haseł długosci nie wiekszej niz 7 mozna utworzyc z liter a, b, c ?
Zadanie 4.6. a) Ile jest palindromicznych liczb 5-cyfrowych ?
b) Ile jest parzystych liczb 5-cyfrowych ?
c) Ile jest parzystych, palindromicznych liczb 5-cyfrowych ?
d) Ile liczb 5-cyfrowych parzystych zawiera dokładnie jedna jedynke ?
e) Ile liczb 5-cyfrowych parzystych zawiera przynajmniej jedna jedynke ?
Zadanie 4.7. Ile liczb od 1 do 2005
a) dzieli sie przez 3 lub przez 4 ?
b) dzieli sie przez 10 lub przez 25 ?
c) nie dzieli sie ani przez 3 ani przez 4 ?
d) nie dzieli sie ani przez 10 ani przez 25 ?
Zadanie 4.8. Sa 3 rózne drogi z miasta A do miasta B, 2 rózne drogi z B do miasta C i 4 rózne drogi
z A do C. Na ile sposobów mozna dojechac (posrednio lub bezposrednio)
a) z A do C i z powrotem ?
b) z A do C i z powrotem, nie przejezdzajac zadnego odcinka trasy dwa razy ?
Zadanie 4.9. Wypisac wszystkie podzbiory zbioru {a, b, c, d} i odpowiadajace im ciagi binarne.
Zadanie 4.10. Wypisac wszystkie podzbiory 3-elementowe zbioru {1, 2, 3, 4, 5}, a przy kazdym z nich
wypisac ciagi długosci 3, zbudowane z wszystkich elementów danego podzbioru.
Zadanie 4.11. a) Narysowac wszystkie mozliwe rozmieszczenia 3 identycznych kulek w 3 róznych
kapeluszach.
b) Narysowac wszystkie mozliwe pokolorowania 3 identycznych kulek, jesli mamy kolory: czerwony,
zielony i niebieski.
c) Czy widac jakas zaleznosc (bijekcje ?) miedzy wynikiem a) i b) ?
5
5. Schematy wyboru
Zadanie 5.1. Ile mozna wykonac róznych trójkolorowych choragiewek uzywajac szesciu barw? Choragiewki
składaja sie z trzech poziomych pasków.
Zadanie 5.2. Ile jest liczb czterocyfrowych, w których nie powtarza sie zadna cyfra?
Zadanie 5.3. Ile mozna utworzyc liczb pieciocyfrowych z cyfr 4,5,6 ?
Zadanie 5.4. Na ile sposobów mozemy utworzyc 6-osobowa delegacje z grupy 10 studentek i 20
studentów, aby
a) pan było tyle samo, ile panów?
b) panów było wiecej niz pan?
Zadanie 5.5. Iloma sposobami mozna rozmiescic 5 osób na pieciu numerowanych krzesłach? A wokół
okragłego stołu, gdy krzesła nie sa numerowane?
Zadanie 5.6. Cztery kule białe, cztery czarne i cztery zielone numerujemy i układamy w szereg tak,
aby kazde trzy po sobie nastepujace kule były róznej barwy. Na ile sposobów mozna je ułozyc?
Zadanie 5.7. Rzucamy 10 razy kostka do gry. Ile jest mozliwych wyników, w których
a) nie ma zadnej czwórki?
b) jest przynajmniej jedna czwórka?
c) sa dokładnie dwie czwórki?
d) sa przynajmniej dwie czwórki?
Zadanie 5.8. W przedziale wagonu sa ustawione naprzeciw siebie dwie ławki majace po 5 numerowanych
miejsc. Na pierwszej ławce siedza 3 osoby oznaczone A, B, C, a na drugiej 2 osoby: D i E. Na ile
róznych sposobów moga usiasc pasazerowie tak, aby zawsze dwie osoby siedziały naprzeciw dwu osób?
Zadanie 5.9. Ile jest mozliwych wyników przy rzucie trzema identycznymi kostkami do gry?
Zadanie 5.10. Na ile sposobów mozna rozmiescic 12 jednakowych przedmiotów w 4 róznych pudełkach?
Zadanie 5.11. Ile jest ciagów binarnych długosci 15, w których cyfra 1 wystepuje dokładnie 3 razy?
Jaki jest zwiazek z poprzednim zadaniem?
Zadanie 5.12. Ile całkowitych nieujemnych rozwiazan ma równanie x1 + x2 + x3 + x4 = 12?
Narysowac odpowiednia krate.
Zadanie 5.13. Na ile sposobów mozna rozmiescic cztery identyczne pomarancze i szesc róznych jabłek
(kazde innego gatunku) w pieciu róznych skrzynkach?
Zadanie 5.14. Ile jest liczb czterocyfrowych, w których suma cyfr wynosi dokładnie 9?
Zadanie 5.15. Ile jest takich rozdan do brydza, w których:
a) gracz W ma wszystkie cztery asy?
b) kazdy z zawodników ma po jednym asie?
c) gracze W i E maja po dwa asy?
Zadanie 5.16. Ile liczb osmiocyfrowych mozemy utworzyc z cyfr liczby a) 21233353 b) 212333534?
Zadanie 5.17. Na ile sposobów moze jednoczesnie przywitac sie szesciu znajomych?
Zadanie 5.18. Na ile sposobów mozna podzielic 22-osobowa grupe studencka na trzy 4-osobowe i dwie
5-osobowe grupy, jesli
a) kazda grupa bedzie pracowac nad innym zadaniem,
b) wszystkie zespoły beda pracowac nad tym samym problemem?
Zadanie 5.19. Podac kombinatoryczne uzasadnienie wzoru
Xn
k=0

n
k

= 2n.
Zadanie 5.20. Iloma sposobami mozna połozyc 12 ksiazek na trzech półkach tak, by na pierwszej
półce znajdowało sie 6 ksiazek, na drugiej 4, a na trzeciej reszta?
Zadanie 5.21. Ile róznych wyrazów (majacych sens lub nie) mozna ułozyc z liter wyrazu MATEMATYKA
?
6 POLITECHNIKA LUBELSKA – Informatyka I
Zadanie 5.22. Szesc osób ma do dyspozycji 5 róznokolorowych kieliszków i 2 rózne gatunki win. Na
ile sposobów moga sie napic?
Zadanie 5.23. Ile mozna utworzyc liczb czterocyfrowych, w których na pierwszym i ostatnim miejscu
wystepuje ta sama cyfra, a cyfry w liczbie moga sie dowolnie powtarzac?
Zadanie 5.24. Ile jest liczb czterocyfrowych, w których jedynie 0 moze sie powtarzac?
Zadanie 5.25. Mamy do dyspozycji cztery rodzaje owoców: jabłka, gruszki, morele i pomarancze.
Tworzymy paczki po 5 owoców w kazdej. Ile róznych paczek mozemy otrzymac w ten sposób?
Zadanie 5.26. Iloma sposobami mozna rozdzielic 4 rózne nagrody miedzy trzech pracowników, jezeli
kazdy z nich ma otrzymac co najmniej jedna nagrode?
Zadanie 5.27. W ilu punktach przecina sie 10 prostych lezacych na płaszczyznie, jezeli cztery z nich
sa równoległe?
Zadanie 5.28. Ile jest dróg z lewego dolnego rogu szachownicy do prawego górnego, jesli mozemy sie
poruszac tylko w prawo i do góry?
Zadanie 5.29. Ile jest sposobów pomalowania 8 jednakowych kul piecioma kolorami?
Zadanie 5.30. Na ile sposobów dziesiec osób moze prowadzic równoczesnie piec rozmów telefonicznych?
Zadanie 5.31. Ile całkowitych nieujemnych rozwiazan ma równanie x1 + x2 + x3 = 10?
Zadanie 5.32. Ile jest najkrótszych dróg w kracie 5 × 4?
Zadanie 5.33. Podac kombinatoryczne uzasadnienie wzoru
Xk
s=0

n
s

m
k − s

=

m + n
k

.
Zadanie 5.34. Podac kombinatoryczne uzasadnienie wzoru
Xn
k=0

n
k

(m − 1)n−k = mn.
Zadanie 5.35. Podac kombinatoryczne uzasadnienie wzoru
Xl
k=0

n
k

m
l − k

=

n + m
l

.
Zadanie 5.36. () Podac kombinatoryczne uzasadnienie wzoru
Xn
k=1
k

n
k

= n2n−1.
Zadanie 5.37. () Podac kombinatoryczne uzasadnienie wzoru
Xn
k=1
k2

n
k
2
= n2

2n − 2
n − 1

.
7
6. Trzy podstawowe zasady
Zadanie 6.1. Ile jest liczb naturalnych od 1 do 100 niepodzielnych ani przez 2, ani przez 3, ani 5 ?
Zadanie 6.2. Stosujac zasade właczania i wyłaczania obliczyc ile jest liczb pierwszych mniejszych niz
100. Wskazówka: kazda liczba złozona mniejsza od n dzieli sie przez jakas liczbe pierwsza mniejsza niz p
n (dlaczego ?).
Zadanie 6.3. Bazujac na idei z poprzedniego zadania, wymyslic algorytm, wyznaczajacy wszystkie
liczby pierwsze z przedziału od 1 do n.
Zadanie 6.4. Wsród 30 pracowników, z których kazdy jest z matematyki (M), fizyki (F) lub biologii
(B), z M jest 15, z F – 12, tych, którzy nie pracuja na B – 15, pracowników M, którzy nie pracuja na
F – 12, ludzi z B, którzy nie sa na F - 11, a zatrudnionych jednoczesnie na B i M – 6. Ilu pracuje na
wszystkich trzech wydziałach jednoczesnie ?
Zadanie 6.5. W grupie 80 osób kazdy biega, pływa lub skacze. Biegaczy jest 50, 45 pływaków, 40
skoczków, 27 osób zarówno pływa jak i biega, 10 trenuje wszystkie 3 dyscypliny, a 32 osób na pewno
nie skacze, ale na pewno biega.
a) Ile uprawia samo bieganie? A samo pływanie ?
b) Ilu ludzi biega lub pływa ?
c) Ilu tylko skacze ?
Zadanie 6.6. Na ile sposobów mozna rozdac n róznych nagród wsród 4 osób A,B,C,D tak, aby
(a) A dostała przynajmniej jedna nagrode ?
(b) A lub B nie dostała nic ?
(c) Zarówno A jak i ...

Ciąg dalszy w pliku do pobrania.

Wkuwanko.pl jako podmiot świadczący usługę hostingu materiałów edukacyjnych nie ponosi odpowiedzialności za ich zawartość.

Aby zgłosić naruszenie prawa autorskiego napisz do nas.

ikona Pobierz ten dokument

Wróć do kategorii

wkuwanko.pl

Wasze komentarze: dodaj komentarz

  • Nie ma jeszcze komentarzy do tego materiału.

Materiały w kategorii Matematyka [119]

[ Misja ] [ Regulamin ] [ Kontakt ] [ Reklama ]   © wkuwanko.pl 2008-2017 właściciel serwisu SZLIFF

Partnerzy: matzoo.pl matmag.pl batmat.pl onlinefm.pl pisupisu.pl Matematyka radio online