Matematyka Dyskretna, Egzamin 2008 (1inf) u
dr W. Kraśkiewicza
Wstęp
Zadania podam razem z poleceniami, które zapisywać będę kursywą. Dodatkowo czasem kolorem
szarym dodam jakieś komentarze pomagające zrozumieć dlaczego jest tak, a nie inaczej ^^. Nie
gwarantuję także, że odpowiedzi są w 100% poprawne. Gdyby nie były  dajcie znać:
moriturius(at)gmail.com
Zadania
Zad. 1
Zdefiniuj NWD pary liczb całkowitych.
Przedstaw algorytm Euklidesa. Co możesz powiedzieć o efektywności algorytmu?
Definicja NWD to trochę jak masło maślane dlatego najpierw trzeba sobie zdefiniować pojęcia
pomocnicze:
Dzielnikiem liczby a nazywamy liczbÄ™ d wtedy i tylko wtedy, gdy a przy dzieleniu przez d daje
resztę równą 0.
Wspólnym dzielnikiem liczb a i b nazywamy liczbę d wtedy i tylko wtedy, gdy d jest dzielnikiem a
oraz d jest dzielnikiem b.
Skoro już mamy podstawowe definicje teraz łatwo będzie zdefiniować NWD:
NWD(a, b) to największy ze wspólnych dzielników liczb a oraz b.
* * *
Algorytm Euklidesa opiera się na spostrzeżeniu, że:
a , gdy b=0
NWDśą a , bźą=
{ }
NWDśąb , a mod bźą , gdy be"1
W praktyce przedstawia siÄ™ to tak:
1. Oblicz c jako resztÄ™ z dzielenia a przez b.
2. a := b
b := c
3. Jeśli b=0 to szukane NWD(a,b) = b. W przeciwnym wypadku przejdz
do punktu 1.
2Å"log2śą aƒÄ…bźą
Pesymistyczna złożoność tego algorytmu wynosi i efektywność taka może się
zdarzyć na przykład gdy chcemy obliczyć NWD dwóch kolejnych wyrazów ciągu Fibonacciego.
Jest to jednak bardzo szczególny przypadek i w ogólności algorytm ten daje wynik już po kilku
krokach.
Zad. 2
Zdefinjuj liczby pierwsze i uzasadnij, że jest ich nieskończenie wiele. Sformułuj zasadnicze
twierdzenie arytmetyki.
Liczba p jest liczbą pierwszą wtedy i tylko wtedy, gdy posiada dokładnie dwa dzielniki.
Czuję potrzebę zwórenia uwagi na różnicę między tą definicją, a tą, która podawana była w
szkolach. Nieprawdą jest, że liczba pierwsza to taka, która dzieli się przez 1 i przez siebie bo wtedy
1 byloby liczbą pierwszą, a normalnie nie jest (bo ma jeden dzielnik równy 1).
Dowód, że liczb pierwszych jest nieskończenie wiele:
Niech p1, p2, p3, ..., pn będą wszystkimi liczbami pierwszymi.
Stwórzmy liczbÄ™: p= p1Å"p2Å"p3Å"...Å"pnƒÄ…1
A
atwo zauważyć, że liczba p nie dzieli się, przez żadną z liczb pierwszych zatem nie jest to liczba
złożona.
Stad liczba p jest również liczbą pierwszą. I sprzeczność z twierdzeniem, że liczb pierwszych jest
skończenie wiele.
W dowodzie chodzi o to, że każda liczba złożona daje się podzielić przez jakąś liczbę pierwszą.
Widać to po rozkładzie liczby na czynniki. Tutaj konstruujemy nową liczbę ze wszystkich liczb
pierwszych (bo założyliśmy sobie że jest ich dokładnie n) i do iloczynu dodajemy 1. W ten sposób
stworzyliśmy liczbę, która przy podzieleniu przez jakąkolwiek liczbę pierwszą (p1,...,pn) da
resztę 1. Stąd wnioskujemy, że jak p nie dzili się przez żadną liczbę pierwszą to też jest liczbą
pierwszą i tutaj mamy sprzeczność bo podobno p1,...,pn to były wszystkie, a tu wyszło, że jest
jeszcze jedna ;)
Zasadnicze twierdzenie arytmetyki
Dla dowolnych całkowitych a, b, c jeśli a|bc oraz NWD(a,b)=1 to a|c.
Twiedzenie jest raczej oczywiste. Jeśli a|bc to znaczy, że musi dzielić co najmniej jedną z liczb b, c.
Jeśli NWD(a,b)=1 to znaczy, że a nie dzieli b. Dlatego musi dzielić c.
Zad 3.
Sformułuj i udowodnij Chińskie Twierdzenie o Resztach.
Znajdz
wszystkie x dla których:
xa"5 śąmod 7źą
xa"10 śąmod 25źą
m1,m2,... , mn
Chińskie Twierdzenie o Resztach mówi, że dla dowolnych całkowitych dodatnich
y1, y2,... , yn układ kongruencji
parami względnie pierwszych oraz dowolnych całkowitych
xa" y1śąmod m1źą
xa" y2śąmod m2źą
î"
xa" yn śąmod mnźą
x ")#1, m1Å"m2Å"...Å"mn*#
ma dokładnie jedno rozwiązanie .
Dowodu się nie podejmę ;) Przejdę od razu do rozwiązania kongruencji. Najpierw trzeba zbadać
czy moduły (tutaj 7 i 25) są względnie pierwsze (jeśli zadanie jest z razem z CTR to pewnie będą
one względnie pierwsze). Tu 7 jest liczbą pierwszą więc tym bardziej jest względnie peirwsza z 25.
Mnożymy teraz kazdą kongruencję wszystkimi trzema stronami przez iloczyn pozostałych
modułów. Więc:
25Å"xa"5Å"25 śąmod 7Å"25źą 25xa"125 śąmod 35źą
=
{ } { }
7Å"xa"10Å"7 śąmod 7Å"25źą 7xa"70śąmod 35źą
W ten sposób otrzymaliśmy uklad kongruencji, z takimi samymi modułami. Teraz można odjąc
drugie od pierwszego i wten sposób otrzymamy kongruencję:
18xa"55śąmod 35źą
Dla ułatwienia rozwiązania tej kongruencji warto policzyć sobie resztę z dzielenia 55 przez 35.
Wynosi ona 20 zatem:
18xa"20 śąmod 35źą
Teraz wystarczy już tylko sprawdzić dla jakich x liczba 18x daje przy dzieleniu przez 35 resztę 20.
Co prawda są na to skomplikowane wzory, ale łatwiej po prostu dodać do siebie kilka razy 18 i
śą18Å"2źą mod 35=36 mod 35=1
posprawdzać. Tak więc startujemy od x=2 czyli: zatem nie jest to
liczba, o którą chodzi. Teraz x=3: 54 mod 35=19 - też klapa. Dalej sprawdzamy 72 i 90. Okazuje
siÄ™ że 90=35Å"2ƒÄ…20 zatem dokladnie to o co nam chodziÅ‚o. Ale warto pamiÄ™tać, że szukamy x ;)
Nasz x wynosi 5. A
atwo go też wyliczyć: 90/18=5 .
Znalez
liśmy jedno rozwiązanie kongruencji ale mamy znalez
ć wszystkie. Na szczęście wiemy, że
wszystkie pozostałe rozwiązania różnią się od tego dokładnie o 35 (moduł). Zatem ostateczny zapis
rozwiÄ…zania wyglÄ…da tak:
x=5ƒÄ…35Å"k , gdzie k "$!
Zad. 4
Sformułuj zasadę włączeń i wyłączeń. Ile jest naturalnych rozwiązań równania:
x1ƒÄ… x2ƒÄ…x3ƒÄ…x ƒÄ…x5=40 0d"xid"9, i=1, 2, ... , 5
spełniających nierówność ?
4
Zasada włączeń i wyłączeń:
A1, A2,... , An będą dowolnymi zbiorami zaś
i , j , k"{1, 2,... , n}
Niech . Wówczas:
n
#"A1*" A2*" A3*"...*" An#"= #"Ai#"- #"Ai)" Aj#"ƒÄ… #"Ai)"A )"Ak#"-...ƒÄ…
" " "
j
i=1 i , j : i"Ä… j i , j , k :i"Ä… j"Ä…k
ƒÄ…śą-1źąn-1Å"
#"A1)"A2)"...)"An#"
x1ƒÄ… x2ƒÄ…x3ƒÄ…x ƒÄ…x5=40 0d"xid"9, i=1,2, ... , 5
Rozwiązanie równania dla :
4
A={śąx1, x2, x3, x4, x5źą: x1ƒÄ…x2ƒÄ…x3ƒÄ…x4ƒÄ…x5=40}
Niech . A
atwo zauważyć, że istnieje bijekcjja
pomiędzy elementami zbioru A oraz drogami w prostokącie o wymiarach 4x40. Stąd:
44! 44 ! 41Å"42Å"43Å"44=41Å"7Å"43Å"11=135751
44
#"A#"= = = =
śą źą
40!śą 44-40źą! 40!Å"4! 2Å"3Å"4
4
Jest to ilość wszystkich rozwiązań. Teraz musimy wyrzucić rozwiązania nie spełniające naszych
0d"xid"9, i=1, 2,... ,5
założeń (czyli ). W tym celu tworzymy sobie nowe zbiory które będą
zawierały tylko złe rozwiązania:
Ai={śą x1, x2, x3, x4, x5źą: x1ƒÄ… x2ƒÄ…x3ƒÄ… x4ƒÄ… x5=40 oraz xie"10}
Niech dla i=1, 2, ... , 5 .
y1=x1,... , yi-1= xi -1 , yi=xi-10, yiƒÄ…1=xiƒÄ…1 ,... , y5= x5
Zastosujmy podstawienie: oraz
Ai '={śą y1, y2, y3, y4, y5źą: y1ƒÄ… y2ƒÄ… y3ƒÄ… y4ƒÄ… y5=30 oraz xie"10}
zdefiniujmy zbiór: .
Ai Ai '
A
atwo zauważyć, że podstawienie to zadaje bijekcję pomiędzy oraz . Stąd:
34! 31Å"32Å"33Å"34
34
#"Ai#"= = = =31Å"8Å"11Å"17=46376
śą źą
30 !Å"śą34-30źą! 2Å"3Å"4
4
xie"10
W powyższym kroku chodzi o to żeby obliczyć ile jest złych rozwiązań takich, że . Na
szczęście ograniczenie dla każdego x jest takie samo więc nie trzeba robić osobnych zbiorów dla
xi
każdego .
Aby obliczyć ilość elementów w tym zbiorze zauwazamy, że rozwiązań równania
x1ƒÄ… x2ƒÄ…x3ƒÄ…x ƒÄ…x5=40 x2e"10
gdy na przykład jest tyle samo co rozwiązań
4
y1ƒÄ… y2ƒÄ… y3ƒÄ… y4ƒÄ… y5=30
. Dzieki temu możemy znów użyć wzoru na ilość dróg w prostokącie.
Teraz abyśmy mogli skorzystać ze wzoru włączeń i wyłączeń potrzebna jest jeszcze ilość
Ai
elementów we wszystkich możliwych przekrojach zbiorów . Postępujemy podobnie
Aij xi x
zakładając że dla elementy z oraz będą większe od 10. Stąd otrzymujemy zbiór:
j
Aij={śą x1, x2, x3, x4, x5źą: x1ƒÄ… x2ƒÄ…x3ƒÄ… x4ƒÄ…x5=40 oraz xie"10i x e"10}
a ten z kolei jest równoliczny
j
ze zbiorem:
Aij '={śą y1, y2, y3, y y5źą: y1ƒÄ… y2ƒÄ… y3ƒÄ… y4ƒÄ… y5=20 }
.
4,
24
#"Ai)"A #"= =7Å"11Å"23Å"6=10626
Zatem: j .
śą źą
4
14
#"Ai)"A )"Ak#"= =1001
Postępując analogicznie dochodzimy do tego, że: j oraz
śą źą
4
4
#"Ai)"A )"Ak)"Al#"= =1
xie"10
j . Nietrudno zauważyć, że gdy wszystkie to ich minimalna
śą źą
4
#"Ai)"A )"Ak)"Al)" Am#"=0
suma będzie 50 zatem liczność zbioru: .
j
Teraz możemy już zastosować wzór włączeń i wyłączeń:
Ilość rozwiązań wynosi:
5
#"A#"-śą #"Ai#"- #"Ai)"A #"ƒÄ… #"Ai)"A )"Ak#"- #"Ai)" A )" Ak)" Al#"źą=
" " " "
j j j
i =1 i"Ä… jd"5 i"Ä… j"Ä… kd"5 i"Ä… j "Ä…k"Ä…ld"5
.
=135751-śą5Å"46376-10Å"10626ƒÄ…10Å"1001-5Å"1źą=126
Zad. 5
an
Niech oznacza liczbę ciągów ternarnych (tj. o wartościach 0, 1 lub 2) długości n, w których
każde dwa symbole niezerowe są przedzielone co najmniej jednym zerem. Znajdz
wzór rekurencyjny
a10
oraz zwarty dla ciągu an " . Czemu jest równe .
śą źą
n=0
Najpierw trzeba sobie przeanalizować opis. Zdanie o przedzieleniu co najmniej jednym zerem jest
dośc kluczowe dla tego ciągu gdyż mówi to, że co najmniej na co drugim miejscu stoją zera.
Prawidłowe ciągi wyglądają więc tak: 102001 lub 010200.
a0
W tej chwili warto pomysleć nad początkowymi wyrazami. Jako że zawsze budzi emocje 
a1
zacznijmy od . Ile jest ciągów długości 1? To raczej proste pytanie  dokładnie 3 (0, 1 oraz 2).
a2=5 a3=11
Przydadzą się jeszcze z dwa wyrazy: oraz . Można je policzyć zwyczajnie
wypisujÄ…c je sobie na kartce.
Teraz trzeba się zastanowić co możemy dostawić na końcu ciągu długości n tak aby powstał ciąg o
długości n+1 spełniający podane warunki.
Jeśli ciąg kończy się na 0 to nie ma problemu  można dostawić 0, 1 lub 2. W innym przypadku,
gdy ciąg kończy się na 1 lub 2, można dostawic tylko jedno  0.
an-1 . Dlaczego?
Warto zauważyć, że w ciągów długości n które mają 0 na końcu jest dokładnie
Ano dlatego, że do każdego wyrazu możemy dopisać sobie bezkarnie 0. Teraz zobaczmy ile jest
ciągów z wyrazami różnymi od 0 na końcu. Wiemy, że do ciągu kończącego się na 0 możemy
dopisać cokolwiek (0, 1 lub 2). Ciągi do których dopisaliśmy 0 już sobie policzyliśmy. Pytanie
powstaje więc ile jest takich ciągów długości n-1 do których można dopisać 1 lub 2. Jest ich
dokładnie tyle ile jest ciągów z zerami na końcu o długości n-2 (wyjaśnione na początku akapitu).
2Å"an-2 nowych ciÄ…gów.
Zatem jeśli i dopiszemy do każdego 1 lub 2 to otrzymamy
Jak się okazuje  policzyliśmy już wszystkie. Stąd wzór rekurencyjny wygląda tak:
an=an-1ƒÄ…2Å"an-2
a1=3, a2=5 a3=11
Warto teraz sprawdzić czy dla danych początkowych wyraz .
a3=a2ƒÄ…2Å"a1=5ƒÄ…2Å"3=5ƒÄ…6=11
O! Nawet wyszło ;)
No to najtrudniejsze za nami. Teraz trzeba znalez
ć wzór zwarty. Wykorzystamy oczywiście
znaleziony wzór rekurencyjny. Najpierw wykonajmy małe przeindeksowanie. Przesuńmy n o 2. Tak
anƒÄ…2 anƒÄ…2=anƒÄ…1ƒÄ…2Å"an .
aby wyraz był wyznaczony w zależności od poprzednich:
Teraz zapiszmy równanie charakterystyczne dla tego wzoru. Najprościej mówiąc  należy przenieść
wszystkie wyrazy na jedną stronę, zamienić indeksy dolne na potęgi oraz a na jakąkolwiek literkę.
Na wykładzie przyjęło się używać t. Na końcu trzeba podzielić przez i otrzymamy w tym
tn
przypadku równanie kwadratowe: .
t2-t-2=0
t1=-1, t2=2
Wyznaczamy miejsca zerowe tego równania: . Następnie trzeba już zapamiętać, że
wzór zwarty (w przypadku gdy mamy dwa pierwiastki) jest zawsze postaci: an=c1Å"tnƒÄ…c2Å"tn .
1 2
W naszym przypadku bÄ™dzie to an=c1Å"śą-1źąnƒÄ…c2Å"2n . Teraz już pozostaÅ‚o jedynie wyznaczyć staÅ‚e
c1 , c2
. Robi się to podstawiając do wzoru wartości początkowe wzoru rekurencyjnego i
rozwiązując powstały w ten sposób układ równań:
3=-c1ƒÄ…2c2
4
c1=-1 , c2=
. Nie są to może liczby piękne
{ }
5=c1ƒÄ…4c2 Po rozwiÄ…zaniu otrzymujemy: 3 3
i nie sprawiają wrażenia działających dla naszego wzoru ale trzeba się przekonoać. Ostatecznie nasz
4Å"2
n
an=-1Å"śą-1źąnƒÄ…
wzór miałby postać: .
3 3
1Å"śą-1źą ƒÄ… 4Å"2 = 1 32
3 3
a3=- ƒÄ… =33=11
Po podstawieniu n=3 otrzymujemy: . Zatem okazuje siÄ™,
3 3 3 3 3
że wzór jest poprawny mimo tego, że nie wygląda ;)
a0
Na sam koniec pozostaje kwestia wyrazu . Teraz jednak skoro mamy wzór zwarty nie ma
1ƒÄ… 4 3
a0=- = =1
problemu z jego wyznaczeniem: . Można też dobrać ten wyraz tak aby
3 3 3
zgadzał się z wzorem rekurencyjnym, ale i tak wyjdzie to samo ;) Wniosek z tego taki, że ciągów
ternarnych o długości 0 jest dokładnie... 1...
Zad. 6
Jest to dość złożone wyjaśnieniowo zadanie i nie chce mi się go aktualnie pisać zatem może póz
niej
dorzuce w dodatkowym pliku ;)
Zad. 7
Zdefiniuj pojęcie wielomianu wieżowego (szachowego) i oblicz ten wielomian dla szachownicy:
X X X
X X X
X X
Definicja:
rB
Niech B będzie szachownicą oraz będzie oznaczać ilość rozstawień i wzajemnie nie
i
atakujących się wież na polach dozwolonych szachownicy B ( zakładamy, że rB=1 ).
0
rB śątźą
Wielomian generujący dla ciągu śąriBźąi=1,2, ... nazywamy wielomianem wieżowym B.
"
rB śątźą= riBÅ"ti
"
i=0
Obliczenie podanego wielomianu zajmuje troche miejsca i byłoby bardzo niewygodne pisanie tego
na komputerze więc wrzucę to rozwiązanie w osobnym pliku jako dokument ze skanami i moimi
komentarzami oczywiście ;)