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łaszczyź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 (a

n

) jest zdefiniowany rekurencyjnie w następujący sposób:

a

0

=0, a

1

=2, a

n

=2

an-1

+ 3

an-2

dla n

≥

2

Obliczyć wyraz a

4

oraz podać wzór jawny na a

n

(korzystając z odpowiedniego twierdzenia).

zad. 5.

Wykazać, że w drzewie binarnym T jest co najmniej

1

2

1

)

(

−

+

T

h

liści.

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.

Sprawdź, które z podanych grafów są planarne:

Dlaczego??(Uzasadnij)

zad. 14.

Jaka jest liczba chromatyczna danych grafów?

a) K

5 ,

b) K

5,6,3

c) P

6

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,…,10

6

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=a

1

,a

2

…a

n

nazywamy nieporządkiem jeśli a

i

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

Znajdź wzór jawny na n-ty wyraz ciągu określonego rekurencyjnie:
a

0

=3, a

1

=6, a

n

=a

n-1

+ 2a

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

Znajdź wzór jawny na n-ty wyraz ciągu określonego rekurencyjnie:
a

0

=2, a

1

=-1, a

n

=-a

n-1

+ 6a

n-2

dla n >1

zad. 27.

Znajdź wzór jawny na n-ty wyraz ciągu określonego rekurencyjnie:
a

0

=1, a

1

=8, a

n

=4a

n-1

- 4a

n-2

dla n >1

zad. 28.

Znajdź wzór jawny na n-ty wyraz ciągu określonego rekurencyjnie:
a

0

=1, a

1

=4, a

n

=a

n-2

dla n >1

zad. 29.

Znajdź wzór jawny na n-ty wyraz ciągu określonego rekurencyjnie:
a

0

=1, a

1

=-3, a

n

=-2a

n-1

+3a

n-2

dla n >1

zad. 30.

Czy następujące zdania są prawdziewe czy fałszywe? “Prawdziwe” oznacza “prawdziwe we wszystkich
rozważanych przypadkach”.
Weźmy pod uwagę dowolny graf.

a) Jeśli istnieje krawędź z wierzchołka u do wierzchołka v, to istnieje krawędź z v do u.
b) Jeśli istnieje krawędź z wierzchołka u do wierzchołka v i istnieje krawędź z wierzchołka v do
wierzchołka w, to istnieje krawęź 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 S

1

, S

2

. Każdy komputer z sieci S

1

, liczącej 200 maszyn, jest podłączonych z

dokładnie 3 komputerami z S

2

, a każdy z sieci S

2

jest połączony z dokładnie sześcioma komputerami z S

1

.

Czy wiadmo, ile komputerów jest w sieci S

2

?

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