Matematyka Dyskretna - zadania
zad. 1.
Chcemy zdefiniować rekurencyjnie zbiór Z  wszystkich trójkątów równoramiennych ABC, gdzie
współrzędne wierzchołków będą liczbami całkowitymi, wierzchołek A zawsze będzie leżeć w początku
układu współrzędnych a wierzchołek B na Osi OX. Czy poniższa definicja jest poprawna? Jeżeli nie 
podaj poprawną.
a) A(0,0), B(2,0), C(1,1)"Z
b) Jeżeli B(a,0)"Z, to C(1/2a,b)"Z, gdzie: a"Z  zbiór liczb całkowitych, b"N  zbiór liczb
naturalnych
zad. 2.
Oto definicja rekurencyjna pewnego zbioru liczbowego B:
a) 8"B, 12"B
b) Jeżeli x"B i y"B, to x+y"B
Udowodnij, stosując indukcję strukturalną, że każdy element zbioru B jest wielokrotnością 4.
zad. 3.
Na płaszczyz
nie danych jest n okręgów. Jaka jest maksymalna liczba obszarów, na które dzielą one
płaszczyznę? Rozwiązać za pomocą odpowiedniej zależności rekurencyjnej.
zad. 4.
Ciąg (an) jest zdefiniowany rekurencyjnie w następujący sposób:
a0=0, a1=2, an=2an-1 + 3an-2 dla ne"2
Obliczyć wyraz a4 oraz podać wzór jawny na an (korzystając z odpowiedniego twierdzenia).
zad. 5.
Wykazać, że w drzewie binarnym T jest co najmniej -1
liści.
2h(T )+1
zad. 6.
Załóżmy, że hasło może być zbudowane z małych liter, cyfr i kropek, ale dwie kropki nie mogą stać obok
siebie. Jak wygenerować wszystkie hasła rekurencyjnie? Jak zdefiniować rekurencyjnie zbiór wszystkich
haseł.
zad. 7.
Palindrom to ciąg, który czytany w obu kierunkach wygląda tak samo. Chcemy zdefiniować zbiór P
ciągów binarnych, które są palindromami. Wyznacz poprawną definicje.
zad. 8.
Oprocentowanie lokat wynosi 7% w ciągu roku. Bank proponuje dwa sposobu gromadzenia kapitału.
" Na początku wpłacamy 1000 zł, odsetki doliczane są do kapitału na końcu każdego roku.
" Na koniec każdego roku wpłacamy 100 zł, odsetki też są doliczane do kapitału na końcu każdego
roku, (oczywiście na końcu roku bank nie doliczy odsetek od 100 zł, które właśnie wpłaciliśmy).
Ile zgromadzimy na każdej lokacie przez n lat? Proszę podać rozwiązanie rekurencyjne dla
każdej osobno. Na której lokacie zgromadzimy więcej przez 35 lat?
strona: 1 z 5
Matematyka Dyskretna - zadania
zad. 9.
Stosując odpowiedni algorytm, wyznaczyć najmniejsze wagi dróg od węzła 1 w diagrafie danym za
pomocą macierzy wag:
zad. 10.
Stosując odpowiedni algorytm, wyznaczyć najmniejsze wagi dróg od węzła 1 w diagrafie danym za
pomocą macierzy wag:
zad. 11.
Algorytm zachłanny kolorowania wierzchołków grafu polega na tym, że każdemu niepokolorowanemu
wierzchołkowi nadajemy kolor, o najmniejszym możliwym numerze (pamiętając oczywiście o zasadzie
kolorowania grafu). Stosując ten algorytm oraz metodę wszerz przeszukiwania wierzchołków grafu,
pokolorować wierzchołki grafu G, startując od wierzchołka a. Rozwiązanie podać w postaci listy:
wierzchołek  numer koloru. Graf G jest dany za pomocą macierzy sąsiedztwa:
zad. 12.
Pokolorować raf G dany za pomocą macierzy incydencji:
Podać jego liczbę chromatyczną.
strona: 2 z 5
Matematyka Dyskretna - zadania
zad. 13.
Sprawdz
, które z podanych grafów są planarne:
Dlaczego??(Uzasadnij)
zad. 14.
Jaka jest liczba chromatyczna danych grafów?
a) K5 , b) K5,6,3 c) P6 d) a: b,d,e,f d: a,c,g g: c,d,f
b: a,e,h e: a,b h:b,f
c: d,f,g f: a,c,g,h
Narysuj je i pokoloruj.
zad. 15.
Grupa złożona z 21 studentów chce utworzyć 7 zespołów roboczych w taki sposób by każdy student
należał dokładnie do 2 zespołów:
1) wykazać, że średnia liczebność zespołu roboczego będzie musiała wynosić 6
2) pokaż w jaki sposób można przypisać studentów do poszczególnych zespołów tak, by w
każdym zespole było dokładnie 6 studentów.
zad. 16.
Przypuśćmy że 73 kulki zostały rozmieszczone w 8 pudełkach:
1. wykaż, że jedno z pudełek zawiera dokładnie 10 kulek
2. wykaż, że jeśli 2 pudełka są puste, to jakieś pudełko zawiera co najmniej 13 kulek
zad. 17.
W grupie 150 osób każdy biega, pływa, lub skacze. Biegaczy jest 50, 45 pływaków, 40 skoczków, 27
osób zarówno pływa jaki 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?
zad. 18.
Na ile sposobów można rozdać n różnych nagród wśród czterech osób A, B, C, D tak, aby:
a) A dostała przynajmniej jedną nagrodę?
b) A lub B nie dostała nic?
c) zarówno A jak i B dostała przynajmniej jedną nagrodę?
d) przynajmniej jedna spośród A, B, C nic nie dostała?
e) każda z 4 osób coś dostała?
zad. 19.
W pewnym klubie jest 20 osób grających w szachy i 15 grających w brydża. Spośród nich 8 gra w obie te
gry. Ile osób jest w tym klubie.
strona: 3 z 5
Matematyka Dyskretna - zadania
zad. 20.
Ile liczb spośród 1,2,& ,106 jest podzielnych przez co najmniej jedną z liczb: 2, 3, 5?
zad. 21.
Pracownicy telekomunikacji maja do położenia 200m kabla. Zakładając, że monterzy muszę także
rozmieścić 12 studzienek (na przestrzeni 200m) uzasadnić, że jedna z odległości pomiędzy studzienkami
będzie wynosić co najmniej 16m.
zad. 22.
Permutację P=a1,a2& an nazywamy nieporządkiem jeśli ai `" i dla każdego i = 1,2,& n. Wypisać wszystkie
nieporządki dla n=1, 2, 3, 4.
zad. 23.
W pewnej populacji królików każda para zdolna do rozrodu rodzi co miesiąc dwie pary. W chwili  zero
jest jedna nowonarodzona para. Zakładając, że króliki są zdolne do rozmnażania po dwóch miesiącach od
narodzin, podaj w postaci rekurencyjnej liczbę par królików po n miesiącach. Oblicz, ile królików będzie
po 9 miesiącach. Korzystając z odpowiedniego twierdzenia, podaj wzór jawny.
zad. 24.
Znajdz
wzór jawny na n-ty wyraz ciągu określonego rekurencyjnie:
a0=3, a1=6, an=an-1 + 2an-2 dla n >1
zad. 25.
Podać zależność rekurencyjną na liczbę ciągów złożonych z liter a i b długości n, w których dwie litery a
nie występują obok siebie. Następnie podać wzór jawny.
zad. 26.
Znajdz
wzór jawny na n-ty wyraz ciągu określonego rekurencyjnie:
a0=2, a1=-1, an=-an-1 + 6an-2 dla n >1
zad. 27.
Znajdz
wzór jawny na n-ty wyraz ciągu określonego rekurencyjnie:
a0=1, a1=8, an=4an-1 - 4an-2 dla n >1
zad. 28.
Znajdz
wzór jawny na n-ty wyraz ciągu określonego rekurencyjnie:
a0=1, a1=4, an=an-2 dla n >1
zad. 29.
Znajdz
wzór jawny na n-ty wyraz ciągu określonego rekurencyjnie:
a0=1, a1=-3, an=-2an-1 +3an-2 dla n >1
zad. 30.
Czy następujące zdania są prawdziewe czy fałszywe?  Prawdziwe oznacza  prawdziwe we wszystkich
rozważanych przypadkach .
Wez
my pod uwagę dowolny graf.
a) Jeśli istnieje krawędz
z wierzchołka u do wierzchołka v, to istnieje krawędz
z v do u.
b) Jeśli istnieje krawędz
z wierzchołka u do wierzchołka v i istnieje krawędz
z wierzchołka v do
wierzchołka w, to istnieje krawęz
z u do w.
strona: 4 z 5
Matematyka Dyskretna - zadania
zad. 31.
Podaj przykład grafu z wierzchołkami x, y, z mającego wszystkiego trzy podane własności:
(i) istnieje cykl przechodzący przez wierzchołki xi y;
(ii) istnieje cykl przechodzący przez wierzchołki y i z;
(iii) nie ma cykli przechodzących przez x i z.
zad. 32.
Narusuj rysunek grafu G, gdzie V(G) = {x, y, z, w}, E(G)={a, b, c, d, f, g, h} oraz funkcja ł jest dana w
postaci tablicy:
e a b c d f g h
ł(e) {x, y} {x, y} {w, x} {w, y} {y, z} {y, z} {w, z}
zad. 33.
Są dwie sieci komputerowe S1, S2. Każdy komputer z sieci S1, liczącej 200 maszyn, jest podłączonych z
dokładnie 3 komputerami z S2, a każdy z sieci S2 jest połączony z dokładnie sześcioma komputerami z S1.
Czy wiadmo, ile komputerów jest w sieci S2?
zad. 34.
Dla grafu przedstawionego poniżej podaj ciąg wierzchołków najkrótszej drogi łączącej następujące pary
wierzchołków i podaj jej długość:
a) s i v
b) s i z
c) u i y
d) v i w
strona: 5 z 5