12.01.2012
II KOLOKWIUM Z MATEMATYKI DYSKRETNEJ - ZESTAW 1
Zadanie 1. Wśród 150 studentów pierwszego roku informatyki po sześćdziesięciu studentów zapisało się
na lektorat z języka angielskiego, niemieckiego oraz francuskiego. Co więcej na każde dwa z
tych lektoratów zapisało się po dwudziestu studentów, a na wszystkie trzy - dziesięciu. Ilu
studentów zapisało się tylko na język francuski?
Zadanie 2. Mamy k programów i n ponumerowanych procesorów, z których każdy może być użyty do wy-
konania dowolnego programu. Obliczyć liczbę możliwych schematów obciążeń tych procesorów
przy wykonywaniu n programów zakładając, że
(a) nie interesuje nas, które programy trafią do którego procesora,
(b) każdy procesor otrzymał co najmniej jeden program i programy są rozróżnialne.
Zadanie 3. Znalez
ć rozwiązanie ogólne równania rekurencyjnego an = 3an-1 - 2an-2 + 2n.
Zadanie 4. Dany jest graf G o funkcji incydencji
¨(e1) = {v1, v1}, ¨(e2) = {v1, v2}, ¨(e3) = {v2, v3},
¨(e4) = {v3, v4}, ¨(e5) = {v4, v2}, ¨(e6) = {v1, v1}.
(a) Wykonaj rysunek grafu G.
(b) Wypisz macierz sÄ…siedztwa i incydencji grafu G.
(c) Podaj ciąg liczb wierzchołków wierzchołków kolejnych stopni grafu G.
(d) Wskaż pętle i wierzchołki izolowane w grafie G.
(e) Czy graf G jest spójny i prosty? Odpowiedz
uzasadnij.
Zadanie 5. Podaj i uzasadnij zależność rekurencyjną, jaką spełniają liczby Stirlinga II-go rodzaju.
12.01.2012
II KOLOKWIUM Z MATEMATYKI DYSKRETNEJ - ZESTAW 2
Zadanie 1. Mamy k programów i n procesorów, z których każdy może być użyty do wykonania dowolnego
programu. Obliczyć liczbę możliwych schematów obciążeń tych procesorów przy wykonywaniu
n programów zakładając, że
(a) nie interesuje nas, które programy trafią do którego procesora,
(b) procesory są ponumerowane i każdy procesor otrzymał co najmniej jeden program.
Zadanie 2. Wśród 150 studentów pierwszego roku informatyki po sześćdziesięciu studentów zapisało się
na lektorat z języka angielskiego, niemieckiego oraz francuskiego. Co więcej na każde dwa z
tych lektoratów zapisało się po dwudziestu studentów, a na wszystkie trzy - dziesięciu. Ilu
studentów zapisało się tylko na język francuski?
Zadanie 3. Podaj i uzasadnij zależność rekurencyjną, jaką spełniają liczby Stirlinga II-go rodzaju.
Zadanie 4. Znalez
ć rozwiązanie ogólne równania rekurencyjnego an = 3an-1 - 2an-2 + 2n.
Zadanie 5. Dany jest graf G o funkcji incydencji
¨(e1) = {v1, v1}, ¨(e2) = {v1, v2}, ¨(e3) = {v2, v3},
¨(e4) = {v3, v4}, ¨(e5) = {v4, v2}, ¨(e6) = {v1, v1}.
(a) Wykonaj rysunek grafu G.
(b) Wypisz macierz sÄ…siedztwa i incydencji grafu G.
(c) Podaj ciąg liczb wierzchołków kolejnych stopni grafu G.
(d) Wskaż pętle i wierzchołki izolowane w grafie G.
(e) Czy graf G jest spójny i prosty? Odpowiedz
uzasadnij.
12.01.2012
II KOLOKWIUM Z MATEMATYKI DYSKRETNEJ - ZESTAW 3
Zadanie 1. Wśród 200 studentów pierwszego roku informatyki po osiemdziesięciu studentów zapisało się
na lektorat z języka angielskiego, niemieckiego oraz francuskiego. Co więcej na każde dwa z
tych lektoratów zapisało się po trzydziestu studentów, a na wszystkie trzy - piętnastu. Ilu
studentów zapisało się tylko na język angielski?
Zadanie 2. Ile istnieje różnych rozmieszczeń n ponumerowanych kul w n ponumerowanych pudełkach, jeśli
(a) co najmniej jedno pudełko jest puste;
(b) dokładnie jedno pudełko jest puste.
Zadanie 3. Znalez
ć rozwiązanie równania rekurencyjnego
an = 4an-1 - 4an-2 + 4n, n > 1; a0 = 5, a1 = 16.
Å„Å‚ üÅ‚
òÅ‚
nżł
Zadanie 4. Udowodnić równość = 2n-1 - 1.
ół
2þÅ‚
Zadanie 5. Dany jest graf G o funkcji incydencji
¨(e1) = {a, b}, ¨(e2) = {b, c}, ¨(e3) = {c, d}, ¨(e4) = {d, f},
¨(e5) = {f, a}, ¨(e6) = {b, d}, ¨(e7) = {d, a}, ¨(e8) = {d, d}
(a) Wykonaj rysunek grafu G.
(b) Wypisz macierz sÄ…siedztwa i incydencji grafu G.
(c) Podaj ciąg liczb wierzchołków kolejnych stopni grafu G.
(d) Wskaż pętle i wierzchołki izolowane w grafie G.
(e) Czy graf G jest spójny i acykliczny? Odpowiedz
uzasadnij.
12.01.2012
II KOLOKWIUM Z MATEMATYKI DYSKRETNEJ - ZESTAW 4
Zadanie 1. Wśród 200 studentów pierwszego roku informatyki po osiemdziesięciu studentów zapisało się
na lektorat z języka angielskiego, niemieckiego oraz francuskiego. Co więcej na każde dwa z
tych lektoratów zapisało się po trzydziestu studentów, a na wszystkie trzy - piętnastu. Ilu
studentów zapisało się tylko na język angielski?
Å„Å‚ üÅ‚
òÅ‚
nżł
Zadanie 2. Udowodnić równość = 2n-1 - 1.
ół
2þÅ‚
Zadanie 3. Ile istnieje różnych rozmieszczeń n ponumerowanych kul w n ponumerowanych pudełkach, jeśli
(a) co najmniej jedno pudełko jest puste;
(b) dokładnie jedno pudełko jest puste.
Zadanie 4. Dany jest graf G o funkcji incydencji
¨(e1) = {a, b}, ¨(e2) = {b, c}, ¨(e3) = {c, d}, ¨(e4) = {d, e},
¨(e5)) = {e, f}, ¨(e6) = {f, a}, ¨(e7) = {f, b}, ¨(e8) = {b, d},
¨(e9) = {d, f}, ¨(e10) = {e, a} ¨(e11) = {a, c}, ¨(e12) = {c, e}
(a) Wykonaj rysunek grafu G.
(b) Wypisz macierz sÄ…siedztwa i incydencji grafu G.
(c) Podaj ciąg liczb wierzchołków kolejnych stopni grafu G.
(d) Wskaż pętle i wierzchołki izolowane w grafie G.
(e) Czy graf G jest spójny i acykliczny? Odpowiedz
uzasadnij.
Zadanie 5. Znalez
ć rozwiązanie równania rekurencyjnego
an = 4an-1 - 4an-2 + 4n, n > 1; a0 = 5, a1 = 16.
12.01.2012
II KOLOKWIUM Z MATEMATYKI DYSKRETNEJ - ZESTAW 5
Zadanie 1. Na ile sposobów można wybrać 10 piłek spośród nieograniczonej liczby piłek czerwonych,
niebieskich i zielonych, jeśli chcemy otrzymać
(a) co najmniej 5 czerwonych piłek?
(b) co najwyżej 5 czerwonych piłek?
Å„Å‚
ôÅ‚
ôÅ‚
òÅ‚
T0 = 4,
Zadanie 2. Przy pomocy czynnika sumacyjnego rozwiązać rekurencję
ôÅ‚
ôÅ‚ 1 1
ół
Tn = nTn-1 + n!, n 1,
2 2
Zadanie 3. Udowodnić, że jeżeli ciągi a i a spełniają jednorodne liniowe równanie rekurencyjne, to ciągi
n n
c1a + c2a , gdzie c1 i c2 są dowolnymi stałymi, też spełniają jednorodne liniowe równanie
n n
rekurencyjne.
Zadanie 4. Dany jest graf G o funkcji incydencji
¨(e1) = {v1, v2}, ¨(e2) = {v2, v1}, ¨(e3) = {v4, v3},
¨(e4) = {v3, v4}, ¨(e5) = {v4, v4}, ¨(e6) = {v1, v1}.
(a) Wykonaj rysunek grafu G.
(b) Wypisz macierz sÄ…siedztwa i incydencji grafu G.
(c) Podaj ciąg liczb wierzchołków kolejnych stopni grafu G.
(d) Wskaż pętle i wierzchołki izolowane w grafie G.
(e) Czy graf G jest spójny i prosty? Odpowiedz
uzasadnij.
Zadanie 5. Wśród 150 studentów pierwszego roku informatyki po pięćdziesięciu studentów zapisało się
na lektorat z języka angielskiego, niemieckiego oraz francuskiego. Angielskiego i francuskiego
uczy się piętnastu studentów, niemieckiego i francuskiego także piętnastu. Nikt nie uczy się
angielskiego i niemieckiego. Ilu studentów nie uczy się żadnego języka?
12.01.2012
II KOLOKWIUM Z MATEMATYKI DYSKRETNEJ - ZESTAW 6
Zadanie 1. Wśród 150 studentów pierwszego roku informatyki po pięćdziesięciu studentów zapisało się
na lektorat z języka angielskiego, niemieckiego oraz francuskiego. Angielskiego i francuskiego
uczy się piętnastu studentów, niemieckiego i francuskiego także piętnastu. Nikt nie uczy się
angielskiego i niemieckiego. Ilu studentów nie uczy się żadnego języka?
Zadanie 2. Na ile sposobów można wybrać 10 piłek spośród nieograniczonej liczby piłek czerwonych,
niebieskich i zielonych, jeśli chcemy otrzymać
(a) co najmniej 5 czerwonych piłek?
(b) co najwyżej 5 czerwonych piłek?
Å„Å‚
ôÅ‚
ôÅ‚
òÅ‚
T0 = 4,
Zadanie 3. Przy pomocy czynnika sumacyjnego rozwiązać rekurencję
ôÅ‚
ôÅ‚ 1 1
ół
Tn = nTn-1 + n!, n 1,
2 2
Zadanie 4. Dany jest graf G o funkcji incydencji
¨(e1) = {v1, v2}, ¨(e2) = {v2, v1}, ¨(e3) = {v4, v3},
¨(e4) = {v3, v4}, ¨(e5) = {v4, v4}, ¨(e6) = {v1, v1}.
(a) Wykonaj rysunek grafu G.
(b) Wypisz macierz sÄ…siedztwa i incydencji grafu G.
(c) Podaj ciąg liczb wierzchołków kolejnych stopni grafu G.
(d) Wskaż pętle i wierzchołki izolowane w grafie G.
(e) Czy graf G jest spójny i prosty? Odpowiedz
uzasadnij.
Zadanie 5. Udowodnić, że jeżeli ciągi a i a spełniają jednorodne liniowe równanie rekurencyjne, to ciągi
n n
c1a + c2a , gdzie c1 i c2 są dowolnymi stałymi, też spełniają jednorodne liniowe równanie
n n
rekurencyjne.
23.01.2012
II KOLOKWIUM Z MATEMATYKI DYSKRETNEJ - ZESTAW 7
Å„Å‚
ôÅ‚
ôÅ‚
òÅ‚
t0 = 3,
Zadanie 1. Przy pomocy czynnika sumacyjnego rozwiązać rekurencję
ôÅ‚
ôÅ‚
ół
3tn = ntn-1 + 2n!, n > 0.
Zadanie 2. Wśród 150 studentów pierwszego roku informatyki na język angielski zapisało się tyle samo
osób co na język niemiecki, a na język niemiecki tyle samo osób co na język francuski. Ponadto
45 osób zapisało się na angielski i niemiecki, 34 osoby na niemiecki i francuski oraz 38 osób na
francuski i angielski. Ilu studentów zapisało się na angielski, jeżeli wiadomo, że każdy student
zapisał sie na co najmniej jeden z tych języków i żaden student nie zapisał się na wszystkie
trzy.
Zadanie 3. Na ile sposobów można rozmieścić dziesięć identycznych piłek w trzech różnokolorowych pu-
dełkach jeśli czerwone pudełko może zawierać
(a) co najmniej 5 piłek,
(b) co najwyżej 4 piłki,
a pozostałe pudełka mogą zawierać dowolną liczbę piłek?
îÅ‚ Å‚Å‚
n - 1
1
ðÅ‚ ûÅ‚
Zadanie 4. Udowodnić równość = (n - 1)(n - 2).
2
n - 2
Zadanie 5. Dany jest graf
v4
e9
v5
(a) Podać macierz sąsiedztwa i ciąg liczb
wierzchołków kolejnych stopni.
e6
v6
e8 e10
(b) Czy w grafie istnieje droga Eulera? Od-
e5
powiedz
uzasadnij.
v7 e7
(c) Czy w grafie spełnione są założenia
e1 e4 v3
e3
twierdzenia, Diraca, Orego i o krawÄ™-
dziach? Odpowiedz
uzasadnij.
v2
e2
v1
23.01.2012
II KOLOKWIUM Z MATEMATYKI DYSKRETNEJ - ZESTAW 8
Zadanie 1. Szkoła ze 120 uczniami oferuje kursy judo i karate. Liczba uczniów chodzących tylko na kurs
judo jest dwa razy większa od liczby tych, którzy chodzą na karate (i być może na judo).
Uczniów nie uczęszczających na żaden kurs jest o 25 więcej niż tych co chodzą na oba kursy.
75 uczniów chodzi na co najmniej jeden kurs. Ilu uczniów uczęszcza na kurs judo, a ilu na kurs
karate?
Zadanie 2. Ile istnieje różnych rozmieszczeń n białych kul w n ponumerowanych pudełkach, jeśli
(a) żadne pudełko nie jest puste,
(b) co najmniej jedno pudełko jest puste.
Å„Å‚ üÅ‚
òÅ‚
n + 1żł n(n + 1)
Zadanie 3. Udowodnić równość = .
ół þÅ‚
2
n
Å„Å‚
ôÅ‚
ôÅ‚
òÅ‚
t0 = 5,
Zadanie 4. Przy pomocy czynnika sumacyjnego rozwiązać rekurencję
ôÅ‚
ôÅ‚
ół
2tn = ntn-1 + 3n!, n 1.
Zadanie 5. Dany jest graf
v7
e1
v6
e2 c) Podać macierz incydencji i ciąg liczb
wierzchołków kolejnych stopni.
e7
v1
e6
a) Czy w grafie istnieje droga Eulera? Od-
e8
powiedz
uzasadnij.
v5 e9
b) Czy w grafie spełnione są założenia
e3
v4
e10
twierdzenia, Diraca, Orego i o krawÄ™-
e5
dziach? Odpowiedz
uzasadnij.
v2
e4
v3