Egzamin z matematyki dyskretnej 21 czerwiec 2006
ImiÄ™:
Nazwisko:
Grupa: Numer Indeksu:
Uwagi: (a) Przyjmujemy, że piłki w tym samym kolorze są nierozróżnialne..................72..........................................
1. Czas rozwiÄ…zywania 90 minut.
2. Ewentualne wątpliwości związane z niejednoznacznością sformułowań w zadaniach należy umieścić obok udzielonych (b) Przyjmujemy, że piłki są ponumerowane od 1 do 10....................1024...................... ................................
odpowiedzi.
3. Dozwolone jest korzystanie z pomocy w formie własnoręcznych notatek i wydruków slajdów z wykładu. Nie wolno korzystać
Zad. 5. (10 pkt. 0.25/0/ 0.25) Wyznacz wybrane parametry następujących grafów:
z książek i urządzeń elektronicznych.
4. Zbiór liczb naturalnych nie zawiera zera: 0 " N.
5. Zapis "a | b" oznacza "a jest dzielnikiem b" czyli "b jest podzielne przez a". K3,3 K3,3  e K2,2,2
6. W trakcie egzaminu nie wolno opuszczać sali przed oddaniem pracy.
Ç(G) 2 2 3
7. Skala ocen jest opisana notacjÄ… (a/b/c) gdzie a  liczba pkt. za poprawnÄ… odp., b  liczba pkt. za brak odp., c  liczba pkt.
za błędną odp.
Ç'(G) 3 3 4
8. Za żadne z siedmiu zadań nie można uzyskać mniej niż 0 pkt.
9. Rozwiązania zadań 1 oraz 2(a)oraz 3(a) należy umieścić na odwrocie.
rad(G) 2 2 2
Zad. 1. (10 pkt. 10/0/0) Dany jest ciąg określony rekurencyjnie:
1 0 0
Ã(G)
1
a1 = 1 oraz an+1 = , dla n e" 1
1+ an
chl(G)a 12 10 12
1
Udowodnij, że an e" dla każdej liczby naturalnej n " N.
2 É(G) 2 2 3
Zad. 2. (10 pkt. 2/0/0) Dana jest relacja określona w zbiorze liczb naturalnych formułą
cir(G)b 6 6 6
xRy Ô! "p"N xy = p2.
obw(G)c 4 4 3
(a) Udowodnij, że R jest relacją typu równoważności.
(b) Ile klas abstrakcji ma ta relacja? ...............................". ................................ ................................ ................................
Zad. 6 (10 pkt.) Uporządkuj według niemalejącego tępa wzrostu następujące funkcje (tak, że
jeśli f występuje przed g, to zachodzi f = O(g)):
(c) Wyznacz [6]R )" {1,2,...,100} = ..6, 24, 54, 96.............................. ................ ................................ ...............
(d) Wyznacz min [23·34·45·56]R = .....2........................... ................................ ................................ ................................ 2
f1 (n)=(2006-1000 )n logn f2 (n)=2003nn f3 (n)=2001n+2006
n
2
(e) Wyznacz min [32·43·54·65]R =..........6......................................................................................................................
2004n
n
f4 (n)= f5 (n)=nlogn f6 (n)=n
2n
Zad. 3. (10 pkt. 2/0/0) Dany jest zbiór ciągów binarnych A = {0, 1, 01, 10, 11, 010, 100, 111,
0111}. Definiujemy relację porządku częściowego R ą" A2 w ten sposób, że aRb wtedy i tylko
5 6 3 2 1 4
wtedy gdy ciąg b zawiera podciąg a. Czyli np. 001R0101 ale nieprawda, że 110R0101).
(a) Narysuj diagram Hasse go tego porzÄ…dku.
Zad. 7 (10 pkt. 10/0/0) Wyznacz wszystkie rozwiązania poniższego układu kongruencji dla 0 d"
Wyznacz:
x d" 200.
(b) wszystkie elementy maksymalne w A względem R...............010, 100, 0111.............................. x a" 3 mod 4
x a" 2 mod 5
(c) wszystkie elementy minimalne w A względem R...................0, 1.............
x a" 3 mod 6
Przestroga. Zauważ, że NWD(4, 6) `" 1.
(d) najdłuższy łańcuch w A względem R......1, 11, 111, 0111..........................
Pierwiastki powyższego układu kongruencji:...........27, 87, 147......................................................
(e) najdłuższy antyłańcuch w A względem R........np. 11, 01, 10........................
Zad. 4. (10 pkt. 5/0/0) Danych jest 10 piłek: 3 białe, 2 żółte oraz 5 zielonych oraz trzy koszyki a
Długość marszruty chińskiego listonosza
biały, żółty i zielony. Na ile sposobów można umieścić piłki w koszykach tak, aby żadna b
Długość najdłuższego cyklu
piłka nie znalazła się w koszyku o tym samym kolorze co ona sama? c
Długość najkrótszego cyklu
RozwiÄ…zanie zad. 1:
Niech P(i) Ô! 1/2 d" ai d" 1
1/2 d" 1 d" 1 Ò! P(1)
Poozstaje udowodnić P(n) Ò! P(n + 1)
(1) P(n) Ò! an e" 1/2 Ô! 1/(1 + an) d" 2/3 Ò! 1/(1 + an) d" 1 Ô! an+1 d" 1
(2) P(n) Ò! an d" 1 Ô! 1/(1 + an) e" 1/2 Ô! an+1 e" 1/2
(3) Z (1) i (2) mamy P(n) Ò! [an+1 d" 1 '" an+1 e" 1/2], a zatem P(n) Ò! P(n + 1).
RozwiÄ…zanie zad. 2(a)
Należy wykazać zwrotność, symetryczność i przechodniość R.
(1) Zwrotność: xRx Ô! "p"N xx = p2. Wystarczy przyjąć p = x.
(2) Symetryczność: Z przemienności mnożenia wynika, że formuły "p"N xy = p2 oraz
"p"N yx = p2 są równoważne.
(3) Przechodniość: Załóżmy, że xRy oraz yRz. A zetem mamy takie całkowite liczby p i
q, że xy = p2 i yz = q2. Stąd xz = (pq / y)2. Liczba r = pq / y jest pierwiastkiem
kwadratowym liczby naturalnej xz, a zatem jest całkowita lub niewymierna. Jako
iloraz dwóch liczb całkowitych jest wymierna, a zatem jest całkowita.
Udowodniliśmy tym samym, że "r"N xz = r2
RozwiÄ…zanie zad. 3(a)