Zbiór zadań z matematyki dyskretnej 9788362773220 [PDF]

Zitiervorschau

Zbiór zadań z matematyki dyskretnej

Uniwersytet Marii Curie-Skłodowskiej Wydział Matematyki, Fizyki i Informatyki Instytut Informatyki

Zbiór zadań z matematyki dyskretnej

Andrzej Krajka

Lublin 2012

Instytut Informatyki UMCS Lublin 2012 Andrzej Krajka

Zbiór zadań z matematyki dyskretnej Recenzent: Ryszard Smarzewski Opracowanie techniczne: Marcin Denkowski Projekt okładki: Agnieszka Kuśmierska

Praca współfinansowana ze środków Unii Europejskiej w ramach Europejskiego Funduszu Społecznego

Publikacja bezpłatna dostępna on-line na stronach Instytutu Informatyki UMCS: informatyka.umcs.lublin.pl.

Wydawca Uniwersytet Marii Curie-Skłodowskiej w Lublinie Instytut Informatyki pl. Marii Curie-Skłodowskiej 1, 20-031 Lublin Redaktor serii: prof. dr hab. Paweł Mikołajczak www: informatyka.umcs.lublin.pl email: [email protected]

Druk FIGARO Group Sp. z o.o. z siedzibą w Rykach ul. Warszawska 10 08-500 Ryki www: www.figaro.pl

ISBN: 978-83-62773-22-0

Spis treści

Łącznie 350 zadań z matematyki dyskretnej

1

Wstęp

1

1 Indukcja (35)

3

2 Wstęp do rekurencji, metoda repertuaru (22)

15

3 Sumy i ich obliczanie, metoda czynnika sumacyjnego (36)

23

4 Funkcje całkowitoliczbowe (25)

37

5 Teoria liczb (84)

45

6 Kombinatoryka (53)

63

7 Funkcje tworzące (35)

77

8 Wstęp do analizy algorytmów (15)

91

9 Grafy (27)

103

10 Zadania przekrojowe (18)

119

Rozwiązania Rozdział Rozdział Rozdział Rozdział Rozdział Rozdział Rozdział Rozdział

1. 2. 3. 4. 5. 6. 7. 8.

Indukcja . . . . . . . . . . . . . . . . . . . . . . . . . Wstęp do rekurencji, metoda repertuaru . . . . . . . Sumy i ich obliczanie, metoda czynnika sumacyjnego Funkcje całkowitoliczbowe . . . . . . . . . . . . . . . Teoria liczb . . . . . . . . . . . . . . . . . . . . . . . Kombinatoryka . . . . . . . . . . . . . . . . . . . . . Funkcje tworzące . . . . . . . . . . . . . . . . . . . . Wstęp do analizy algorytmów . . . . . . . . . . . . .

. . . . . . . .

125 125 137 147 172 181 191 202 213

vi

SPIS TREŚCI Rozdział 9. Grafy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 Rozdział 10. Zadania przekrojowe . . . . . . . . . . . . . . . . . . . 223

Bibliografia

235

Wstęp Niniejszy zbiór zadań powstał w oparciu o materiały, które przygotowywałem do zajęć z Matematyki Dyskretnej na kierunku Informatyka Uniwersytetu im. Marii Curie-Skłodowskiej w Lublinie. Wykłady do tych zajęć zostały opublikowane w [12], zbiór zadań stanowi uzupełnienie tych wykładów. Treść i układ zadań ściśle odpowiada układowi wykładów w [12], jednak w kilku miejscach przekroczyłem ramy teoretyczne zakreślone w skrypcie [12]. Bardzo rozbudowany został rozdział dotyczący indukcji matematycznej. Materiał ten powinien być opanowany przez studentów w gimnazjum lub liceum. W moim zamyśle pierwszy rozdział jest przypomnieniem i nawiązaniem do znanych faktów teoretycznych. W rozdziale 5 dotyczącym teorii liczb, w stosunku do [12], rozwinąłem teorię rozwiązywania układu kongruencji. Myślę, że pozwoli to czytelnikowi lepiej zrozumieć znaczenie kongruencji w teorii liczb. W rozdziale 7 dotyczącym funkcji tworzących dodatkowo opisałem problemy związane z wielomianami wieżowymi. Ta metoda wydawała mi się bardziej intuicyjna i obrazowa przy opisywaniu idei funkcji tworzących niż rozważanie wykładniczych czy trygonometrycznych funkcji tworzących, co jeszcze dodatkowo wymagałoby wprowadzenia silniejszego aparatu matematycznego. Chociaż bardzo polecam studiowanie zbioru zadań łącznie z podręcznikiem [12], to jednak aby częściowo uniezależnić zbiór od podręcznika rozpoczynam poszczególne rozdziały bardzo krótkim przypomnieniem podstawowych faktów teoretycznych. Prawie wszystkie (poza kilkoma oczywistymi) zadania rozwiązane zostały w ostatnim rozdziale. Zadania trudniejsze oznaczone są gwiazdką. Wszystkie programy w tekście opisane są w ”pseudokodzie,” który jest zrozumiały dla każdego, kto ma choć odrobinę praktyki programistycznej. Mam nadzieję, że zbiór ten będzie pomocny zarówno dla studentów jak i wykładowców prowadzących zajęcia z Matematyki Dyskretnej.

Rozdział 1 Indukcja (35)

4

Indukcja 1o Zasada indukcji matematycznej Niech S(n), n ∈ N , będzie stwierdzeniem logicznym (to znaczy takim, o którym możemy powiedzieć, że jest prawdziwe lub fałszywe). Jeżeli 1. S(ko ) jest prawdziwe, 2. dla każdej liczby naturalnej k ≥ ko : z prawdziwości S(k) wynika prawdziwość zdania S(k + 1), to zdanie S(n) jest prawdziwe dla wszystkich liczb naturalnych n ∈ N , n ≥ ko . Krok 1 nazywamy krokiem początkowym, a krok 2 krokiem indukcyjnym. Indukcja matematyczna może nie tylko dotyczyć całego zbioru liczb naturalnych, ale jego podzbioru (nawet skończonego) lub nadzbioru (np. liczb wymiernych). Jednak wszystkie te zbiory są skończone lub przeliczalne, a więc mogą być ustawione w ciąg. Przykład 1.1. Udowodnij nierówność S(n) :

√ 1 1 1 1 + √ + √ + . . . + √ > n, n ≥ 2. n 2 3

1. Nierówność dla najmniejszego n, dla którego ma być prawdziwa teza S(n), to znaczy ko = 2, sprawdzamy bezpośrednio: 1 1+ √ = 2

√

1+1 √ 2+1 √ > √ = 2. 2 2

2. Załóżmy teraz, że teza zachodzi dla pewnego k (S(k)). Wówczas dla k + 1 otrzymujemy 1 1 1 1 1 + √ + √ + ... + √ + √ k+1 2 3 k

z zał. indukcyjnego √ 1 > k+ √ k+1 p k(k + 1) + 1 √ = k+1 k+1 √ > k+1 √ = k + 1,

co dowodzi S(k + 1), a więc na mocy zasady indukcji S(n) jest prawdziwe dla wszystkich naturalnych n ≥ 2. Przykład 1.2. Udowodnij, że dla dowolnej liczby naturalnej n > 0, liczba 2n 32n − 1 jest podzielna przez 17. 1. n = 1. Liczba 21 32 − 1 = 2 · 9 − 1 = 17 jest podzielna przez 17.

5

Indukcja 2. Załóżmy, że dla pewnego n > 0 oraz pewnej liczby naturalnej k mamy = 17k. Wtedy 2n+1 32(n+1) − 1 = 18 · 2n 32n − 1 = 18 · (2n 32n − 1) + 18 − 1 = 18 · 17k + 17 jest również liczbą podzielną przez 17. Stąd wnioskujemy tezę. 2n 32n − 1

Przykład 1.3. Udowodnij nierówność Bernoulliego: S(n) :

(1 + x1 )(1 + x2 ) . . . (1 + xn ) ≥ 1 + x1 + x2 + . . . + xn , n ≥ 1,

gdzie x1 , x2 , . . . xn są to liczby rzeczywiste tego samego znaku większe od −1. Teraz indukcja matematyczna nie dotyczy zbioru liczb naturalnych, ale przeliczalnego podzbioru liczb rzeczywistych, ciągu liczb rzeczywistych. Wtedy 1. Sprawdzamy tezę dla najmnniejeszego indeksu, tzn. ko = 1. Mamy S(1) :

1 + x1 ≥ 1 + x1 .

2. Załóżmy teraz, że teza jest prawdziwa dla pewnego k ≥ 1. Wtedy, dla k+1: (1 + x1 )(1 + x2 ) . . . (1 + xk )(1 + xk+1 )

z zał. ind. ≥ (1 + x1 + . . . + xk )(1 + xk+1 ) =

1 + x1 + . . . + xk + xk+1

+xk+1 (x1 + x2 + . . . + xk ) ≥

1 + x1 + . . . + xk + xk+1 ,

co dowodzi S(k+1), tak więc z zasady indukcji matematycznej S(n) zachodzi dla n ≥ 1. Przykład 1.4. Udowodnij, że dla wszystkich liczb naturalnych n, m ∈ N zachodzi: S(n, m) :

X

j(3j+1)i =

1≤i≤n,1≤j≤m

n(n + 1)m(m + 1)2 , n, m ≥ 1, n, m ∈ N . 2

Tutaj mamy dwuwymiarowy ciąg indeksów. 1. Sprawdzamy prawdziwość S(1, 1). Mamy 1 · (3 · 1 + 1) · 1 = 4 =

1 · 2 · 1 · 22 , 2

zatem S(1, 1) zachodzi. 2. Wykażemy najpierw, że dla wszystkich naturalnych n ≥ 1: T (n) :

1 + 2 + 3 + ...n =

n(n + 1) . 2

6

Indukcja Rzeczywiście 1 =

1·2 2

więc T (1) zachodzi. Załóżmy T (k) wtedy

1 + 2 + . . . + k + (k + 1) =

(k + 1)(k + 2) k(k + 1) + (k + 1) = , 2 2

więc T (k + 1) też zachodzi co dowodzi T (n) dla dowolnego n ≥ 1. 3. Z prawdziwości S(n, k) dowiodę prawdziwość S(n, k + 1), dla wszystkich k, n ≥ 1. Rzeczywiście X

j(3j + 1)i =

X

j(3j + 1)i +

= =

j(3j + 1)i

1≤i≤n,j=k+1

1≤i≤n,1≤j≤k

1≤i≤n,1≤j≤k+1

X

n X n(n + 1)k(k + 1)2 + (k + 1)(3k + 4) i 2 i=1

n(n + 1)k(k + 1)2 n(n + 1)(k + 1)(3k + 4) + 2 2

z udowodnionego punktu 2. 4. Załóżmy teraz, że zachodzi S(n, k) dla pewnych k, n ≥ 1. Udowodnimy S(n + 1, k). Rzeczywiście X

j(3j + 1)i =

X

j(3j + 1)i +

1≤i≤n,1≤j≤k

1≤i≤n+1,1≤j≤k

= = =

X

j(3j + 1)i

i=n+1,1≤j≤k

n(n + 1)k(k + 1)2 + k(3k + 1)(1 + 2 + . . . + (n + 1)) 2 n(n + 1)k(k + 1)2 (n + 1)(n + 2)k(3k + 1) + 2 2 2 (n + 1)(n + 2)k(k + 1) . 2

2o Silna zasada indukcji matematycznej. Niech S(n), n ∈ N , będzie stwierdzeniem logicznym dla którego 1. S(ko ) jest prawdziwe, 2. dla każdej liczby naturalnej k ≥ ko : z prawdziwości S(ko ), S(ko +1), ..., S(k− 1) wynika prawdziwość zdania dla S(k). Wtedy zdanie S(n) jest prawdziwe dla wszystkich liczb naturalnych n ∈ N , n ≥ ko . Przykład 1.5. Chcemy dowieść twierdzenie, że każda liczba naturalna większa od 1 albo jest pierwsza, albo można ją przedstawić jako iloczyn liczb pierwszych. Liczba 2 jest pierwsza a więc krok początkowy jest spełniony. Jeśli jednak weźmiemy liczbę 118973 to informacja, że 118972 jest pierwsza lub jest iloczynem liczb pierwszych nic nam nie daje. Musimy mieć silniejsze założenie. Dla dowolnej liczby załóżmy, że nie tylko poprzednią liczbę

7

Indukcja ale i wszystkie poprzednie można tak przedstawić. Wtedy albo k jest liczbą pierwszą, albo jest złożona, to znaczy, że jest iloczynem dwóch liczb i oraz j takich, że 1 < i, j < k a ponieważ z założenia indukcyjnego każda z nich jest albo pierwsza albo jest iloczynem liczb pierwszych, więc i k spełnia tezę. Przykład 1.6. Czasem nie docenia się kroku początkowego. Zwróćmy uwagę, że w ewidentnie fałszywym stwierdzeniu n = n − 3 krok indukcyjny jest spełniony bo k = (k − 1) + 1 = (k − 1) − 3 + 1 = k − 3 a mimo to nie istnieje żadna liczba naturalna dla której to stwierdzenie jest prawdziwe. 3o Logika Funkcja zdaniowa Φ(x), x ∈ A, określona na zbiorze A jest to funkcja, która dla każdej wartości x ∈ A jest zdaniem logicznym, to znaczy zdaniem, które przyjmuje jedną z dwóch możliwych wartości {0, 1}. Zdanie o wartości logicznej 0 interpretujemy jako zdanie fałszywe, natomiast zdanie o wartości logicznej 1 to zdanie prawdziwe. Dla zdań logicznych p, q (i w konsekwencji funkcji zdaniowych) możemy wprowadzić wiele różnych operatorów, np. zaprzeczenia ∼ p, koniunkcji p ∧ q, alternatywy p ∨ q czy implikacji p ⇒ q : p 0 0 1 1

q 0 1 0 1

∼p 1 1 0 0

p∧q 0 0 0 1

p∨q 0 1 1 1

p⇒q 1 1 0 1

p≡q 1 0 0 1

4o Podzielność Przez k|l oznaczać będziemy fakt, że liczba k jest dzielnikiem liczby l, czyli istnieje liczba całkowita m taka, że l = km. Zauważ, że w szczególności l|0 dla każdej liczby całkowitej l. Natomiast kr ||l oznacza, że kr |l ale kr+16 |l i mówimy wtedy, że kr jest właściwym dzielnikiem l. ZADANIA Udowodnij indukcyjnie: Zad. 1.1. 1 · 4 + 2 · 7 + 3 · 10 + . . . + n(3n + 1) = n(n + 1)2 , n ≥ 0, n ∈ N . Zad. 1.2. 1 1 1 n+2 1 )= , n ≥ 1, n ∈ N . (1 − )(1 − )(1 − ) . . . · (1 − 2 4 9 16 (n + 1) 2n + 2

8

Indukcja Zad. 1.3. 1 · 1! + 2 · 2! + 3 · 3! + . . . + n · n! = (n + 1)! − 1, n ≥ 1, n ∈ N . Zad. 1.4. 0 1 2 n−1 1 + + + ... + = 1 − , n ≥ 1, n ∈ N . 1! 2! 3! n! n! Zad. 1.5. 22 32 n2 n(n + 1) 12 + + + ... + = , n ≥ 1, n ∈ N . 1·3 3·5 5·7 (2n − 1) · (2n + 1) 2(2n + 1) Zad. 1.6. Dla n ≥ 1, n ∈ N : 1 2 3 n n(n + 1) + + +. . .+ = . 1·3·5 3·5·7 5·7·9 (2n − 1) · (2n + 1) · (2n + 3) 2(2n + 1)(2n + 3) Zad. 1.7. Dla n ≥ 1, n ∈ N : 1 1 1 1 1 1 1 + + +. . .+ = ( − ). 1·2·3 2·3·4 3·4·5 n · (n + 1) · (n + 2) 2 2 (n + 1) · (n + 2) Zad. 1.8. 1·2·3+2·3·4+3·4·5+. . .+n(n+1)(n+2) =

n(n + 1)(n + 2)(n + 3) , n ≥ 1, n ∈ N . 4

Zad. 1.9. 1 1 1 1 1 (1 − )(1 − )(1 − ) . . . (1 − )= , n ≥ 1, n ∈ N . 2 3 4 n+1 n+1 Zad. 1.10. 2·12 +3·22 +4·32 +. . .+(n+1)n2 =

n(n + 1)(n + 2)(3n + 1) , n ≥ 1, n ∈ N . 12

9

Indukcja Zad. 1.11. 1 1 1 1 + + + ... + 1·2·3·4 2·3·4·5 3·4·5·6 n(n + 1)(n + 2)(n + 3)  11 1 = − , n ≥ 1, n ∈ N . 3 6 (n + 1)(n + 2)(n + 3) Zad. 1.12. 5 + 55 + 555 + . . . + 555 . . . 5} = | {z n razy

5(10n+1 − 9n − 10) , n ≥ 1, n ∈ N . 81

Zad. 1.13. (n + 1)(n + 2)(n + 3) · . . . · (n + n) = 2n · 1 · 3 · 5 · . . . · (2n − 1), n ≥ 1, n ∈ N . Zad. 1.14. 1−

1 1 1 1 1 1 1 + − + ... + − = + ... + , n ≥ 1, n ∈ N . 2 3 4 2n − 1 2n n+1 2n

Zad. 1.15. Udowodnij indukcyjnie, że dla dowolnego rzeczywistego x 6= 1 i n ≥ 1, n ∈ N : x + 2x2 + 3x3 + . . . + nxn =

x − (n + 1)xn+1 + nxn+2 . (1 − x)2

Zad. 1.16. Udowodnij indukcyjnie, że dla dowolnej liczby rzeczywistej a a + 2n − 1 (a − 1)(2n − 1) a+1 a+3 a+7 + + +. . .+ = +n, n ≥ 1, n ∈ N . 2 4 8 2n 2n

Zad. 1.17. Udowodnij indukcyjnie, że dla dowolnego rzeczywistego x, |x| = 6 1, oraz wszystkich naturalnych n ≥ 0, n ∈ N : 2 4 2n 1 2n+1 1 + 2 + 4 + . . . + 2n = + . x+1 x +1 x +1 x +1 x − 1 1 − x2n+1

10

Indukcja Zad. 1.18. Udowodnij indukcyjnie, że dla dowolnego rzeczywistego x, |x| = 6 1, oraz wszystkich naturalnych n ≥ 1, n ∈ N : n−1

n

x 1 x − x2 x2 x4 x2 = · . + + + . . . + n 1 − x2 1 − x4 1 − x8 1 − x2 1 − x 1 − x2n Zad. 1.19. Udowodnij indukcyjnie, że dla dowolnego rzeczywistego x, x 6= 0, x 6= ±1, oraz wszystkich naturalnych n ≥ 1, n ∈ N : 1 1 1 1 1 1 (x− )2 +(x2 − 2 )2 +(x3 − 3 )2 +. . .+(xn − n )2 = 2 (x2n+2 − 2n )−2n−1. x x x x x −1 x Zad. 1.20. Udowodnij indukcyjnie dla n ≥ 1, n ∈ N : (a) (b) (c) (d) (e) (f ) (g) (h) (i) (j) (k) (l) (m)

35 9 17 11 64 19 37 57 133 25 23 120 1053

| | | | | | | | | | | | |

(62n − 1), (4n + 15n − 1), (25n+3 + 5n · 3n+2 ), (62n + 3n+2 + 3n ), (32n+2 − 8n − 9). (33n+2 + 5 · 23n+1 ), (2n+5 · 34n + 53n+1 ), (7n+2 + 82n+1 ), (11n+2 + 122n+1 ), (2n+2 · 3n + 5n − 4), (52n+1 + 2n+4 + 2n+1 ), n5 − 5n3 + 4n, (32n+2 · 52n − 33n+2 · 22n ).

Zad. 1.21. Udowodnij indukcyjnie, że √ √ (1 + 2)n + (1 − 2)n , n ≥ 1, an = 2 jest rozwiązaniem równania rekurencyjnego an = 2an−1 + an−2 , n ≥ 3, a1 = 1, a2 = 3. Zad. 1.22. Funkcja f : N → N jest określona następująco: f (0) = 2,

f (1) = 5,

f (n + 2) = 5f (n + 1) − 6f (n), dla każdego n ∈ N .

Udowodnij, że f (n) = 2n + 3n , dla każdego n ∈ N .

11

Indukcja Zad. 1.23. Udowodnij indukcyjnie, że (

a1 = 3, an = 32 n!, n ≥ 2,

jest rozwiązaniem równania rekurencyjnego: (

a1 = 3, an = 1 · a1 + 2 · a2 + 3 · a3 + . . . + (n − 1) · an−1 , n ≥ 2, n ∈ N .

Zad. 1.24. Udowodnij indukcyjnie, że   a1  an

= 5, = 5·

 n−2 3 2

, n ≥ 2,

jest rozwiązaniem równania rekurencyjnego: (

a1 = 5, a1 + an = 2n−2

a2 2n−3

+ ... +

an−1 ,n 20

≥ 2, n ∈ N .

Zad. 1.25. Ciąg {an , n ≥ 0} określają następujące warunki: (

ao = 2, a1 = 3, a2 = 6, an = (n + 4)an−1 − 4nan−2 + 4(n − 2)an−3 , n ≥ 3, n ∈ N .

Udowodnij, że an = n! + 2n dla każdego n ∈ N . Zad. 1.26. Niech fn (x) = f (f (. . . f (x) . . .)) . | {z } n razy

Znaleźć wzór na fn (x), n ≥ 1, i udowodnić jego prawdziwość indukcyjnie, jeśli 1 , x 6= 1, (a) f (x) = 1−x x √ (b) f (x) = . 1+x2 Zad. 1.27. Udowodnij, że dowolną liczbę naturalną większą od 1 można przedstawić w postaci iloczynu liczb pierwszych. (Jeśli n jest liczbą pierwszą, to ten iloczyn składa się tylko z jednego czynnika n).

12

Indukcja Zad. 1.28. Dane są liczby naturalne a, b, p, q. Udowodnij, że istnieje dokładnie jeden ciąg liczb naturalnych {xn , n ≥ 0} spełniający warunki: (

x0 = a, x1 = b, xn+2 = pxn+1 + qxn , n ≥ 0.

Zad. 1.29. Mówimy, że zbiór płaszczyzn znajduje się w położeniu ogólnym, gdy każde dwie się przecinają, a przecięcie dowolnych trzech nie tworzy prostej. Pokaż, że n płaszczyzn w przestrzeni trójwymiarowej, które znajdują się w położeniu ogólnym, dzieli przestrzeń na 2 + (n − 1)n obszarów. Zad. 1.30. Przeanalizujmy następujący dowód indukcyjny:

Teza: n(n + 1) jest nieparzystą liczbą dla każdego dodatniego naturalnego n. Dowód: Załóżmy, że teza jest prawdziwa dla n−1. Ponieważ (n−1)n jest liczbą nieparzystą a n(n + 1) = n(n − 1) + 2n, więc i n(n + 1) jest liczbą nieparzystą.

Jednak 9 · 10 = 90 jest liczbą parzystą? Zad. 1.31. Wyjaśnij, dlaczego następujący dowód indukcyjny:

Teza: Jeśli mamy na płaszczyźnie n prostych, z których żadne dwie nie są równoległe, to wszystkie proste przecinają się w jednym punkcie. Dowód: Twierdzenie jest prawdziwe dla 1 i również dla 2 prostych. Załóżmy, że teza jest prawdziwa dla n − 1 prostych. Rozważmy zbiór prostych P = {p1 , p2 , . . . pn } a zwłaszcza jego dwa podzbiory P1 = {p1 , p2 , . . . pn−1 } oraz P2 = {p2 , p3 , . . . pn }. Z założenia indukcyjnego proste z P1 przecinają się w jednym punkcie, proste w P2 też w jednym punkcie, a ponieważ p2 , p3 są prostymi należącymi do obu zbiorów, więc ten punkt musi być wspólny dla wszystkich prostych.

jest w sposób oczywisty fałszywy. Gdzie leży błąd w tym dowodzie?

13

Indukcja Zad. 1.32.⋆ Rozważmy następujący ciąg zadany rekurencyjnie: Funkcja Ackermanna A(m, n), m, n ∈ N : A(0, n) = n + 1, A(m, 0) = A(m − 1, 1), A(m, n) = A(m − 1, A(m, n − 1)) (a) Wyprowadź wzory na A(k, n), k = 0, 1, 2, 3, 4. (b) Udowodnij, że: A(0, n) = n + 1, A(m, n) > n + 1, m > 0, n ≥ 0, (c) Wykaż, że funkcja Ackermanna jest niemalejąca ze względu na pierwszą oraz drugą zmienną (d) Dla dowolnego x ≥ 4, m ≥ 0 oraz y ≤ x zachodzi A(m, A(m, . . . A(m A(m + 1, x)) . . .) ≤ A(m + 2, x). |

y−

{z

razy

}

Zad. 1.33. Dla ciągu {Ao , A1 , A2 , . . .} podzbiorów zbioru X ciąg zbiorów {Bo , B1 , B2 , . . .} definiujemy następująco (

Bo = Ao , Bn = Bn−1 ÷ An , n ≥ 1,

gdzie A ÷ B = (A\B) ∪ (B\A) oznacza różnicę symetryczną zbiorów A i B. Udowodnij, że x ∈ Bn wtedy i tylko wtedy gdy x występuje w nieparzystej liczbie zbiorów {Ao , A1 , A2 , . . . An }. Zad. 1.34. Korzystając z indukcji matematycznej udowodnij, że dla dowolnych zdań logicznych mamy (a) (b)

(p ∧ q ≡ p) ⇒ (p ∧ q ≡ p) ⇒ . . . ⇒ (p ∧ q ≡ p) ≡ 1, n ≥ 1,

|

{z

}

2n razy ∼ (p1 ∧ p2 ∧ p3 ∧ . . . ∧ pn ) ≡ (∼ p1 ∨ ∼ p2 ∨ ∼ p3 ∨ . . . ∨ ∼ pn ), n ≥ 1.

Zad. 1.35. Udowodnij, że każdą ilość złotówek, poza 1 zł. i 3 zł. można zamienić na monety 2- i 5-złotowe.

Rozdział 2 Wstęp do rekurencji, metoda repertuaru (22)

16

Wstęp do rekurencji, metoda repertuaru 1o Wieża w Hanoi (E. Lucas, 1883) Rysunek 2.1. Wieża w Hanoi.

U zarania czasu Bóg umieścił 64 złote krążki na jednej z trzech diamentowych iglic tak, że krążki najniżej położone miały największe promienie a te najwyżej położone najmniejsze promienie (zob. Rys. 2). Następnie Bóg polecił grupie mnichów przełożenie tych krążków na drugą iglicę (B), ale tak by: – w jednym ruchu przenosić tylko jeden krążek, – krążek większy nigdy nie może leżeć na krążku mniejszym, – można posługiwać się trzecią iglicą C. Jak można to zrobić i ile ruchów potrzeba na wykonanie tej pracy? Największy krążek można położyć tylko na wolną iglicę a więc trzeba wykonać hn−1 ruchów, potem przenieść największy krążek na pustą iglicę a potem przełożyć n − 1 kr ażków na iglicę z największym krążkiem (tak jakby ta iglica była pusta). Mamy więc h1 = 1,

hn = 2hn−1 + 1, n ≥ 2,

której rozwiązaniem jest hn = 2n − 1, n ≥ 0. 2o Problem pizzy Jaka jest największa możliwa liczba ln obszarów wyznaczonych przez n prostych na płaszczyźnie? (Jak najmniejszą liczbą cięć podzielić pizzę na ln kawałków?)

lo = 1

l1 = 2

❅ ❅ ❅

❅ ❅ ❅ ❅ ❅

l2 = 4

l3 = 7

❅ ❅ ❅ ❅ ❅

l4 = 11

Zauważmy, że nowa prosta zwiększa liczbę obszarów o k jeśli przecina dokładnie k − 1 poprzednich prostych i to w nowych punktach przecięć. Z

Wstęp do rekurencji, metoda repertuaru drugiej strony dwie proste mogą się przeciąć co najwyżej w jednym punkcie i przecinają się o ile nie są równoległe. Zatem (

lo = 1, ln = ln−1 + n, dla n ≥ 1,

a stąd ln = 1 +

n(n + 1) , n ≥ 0. 2

3o Problem Flawiusza 41 żydowskich powstańców zamkniętych jest przez Rzymian w jaskini. Aby nie dostać się w ręce wrogów powstańcy postanowili sami się zabić. Jednak prawowierny żyd nie może popełnić samobójstwa, dlatego postanowili zabić się nawzajem. Ustawili się w okrąg z wyróżnioną jedną osobą i zaczęli liczyć od tej wyróżnionej osoby co 3 osobę, zabijając ją. Na której pozycji należy się ustawić, aby zostać ostatnią osobą i uniknąć śmierci? Ogólnie mamy n osób i eliminujemy co k - tą osobę. Na której pozycji Jk (n) należy się ustawić, aby pozostać (będziemy w skrócie pisać J(n) = J2 (n))? Rekurencja, jaką otrzymujemy analizując eliminacje po przejściu pierwszy raz okręgu to    J(1)

= 1, J(2n) = 2J(n) − 1, dla n ≥ 1,   J(2n + 1) = 2J(n) + 1, dla n ≥ 1.

a jej rozwiązanie to J(n) = J(2m + l) = 2l + 1, n ≥ 1, gdzie 2m ≤ n < 2m+1 , l = n − 2m . Można też rozwiązanie rekurencji Flawiusza zapisać w postaci dwójkowej J(n) = J((1bm bm−1 . . . bo )2 ) = (bm−1 bm−2 . . . bo 1)2 , n ≥ 1, (zob. punkt poniżej). 4o Metoda repertuaru. Jeżeli mamy dane równanie rekurencyjne, np. (

h1 = 2, hn = 5hn−1 + n, n = 1, 2, 3, ....

to pierwszym krokiem metody repertuaru jest sparametryzowanie tego równania rekurencyjnego, np. (

f1 = α, fn = 5fn−1 + βn + γ, n = 1, 2, 3, ....

17

18

Wstęp do rekurencji, metoda repertuaru Dalej poszukujemy rozwiązania tego równania rekurencyjnego w postaci fn = A(n)α + B(n)β + C(n)γ, n ≥ 1. Staramy się znaleźć pewne przypadki szczególne tego równania rekurencyjnego wypróbowując najczęściej funkcje 1, n, n2 , n3 . . . 2n , 3n . . . n! itp.

(

fn = 1 1 = α, 1 = 5 + βn + γ,    α = 1, β = 0,   γ = −4, 1 = A(n) − 4C(n),

(

fn = n

1 = α, n = 5n − 5 + βn + γ,    α = 1, β = −4,   γ = 5, n = A(n) − 4B(n) + 5C(n),

(

fn = 5n 5 = α, 5n = 5n + βn + γ,    α = 5, β = 0,   γ = 0, 5n = 5A(n),

a stąd A(n) = 5n−1 , 5n−1 − n 5n − 5 B(n) = + , 4 16 5n−1 − 1 , C(n) = 4 zatem

5n−1 − n 5n − 5 5n−1 − 1 + )β + γ 4 16 4 a ponieważ rekurencja hn otrzymana jest z fn poprzez podstawienie α = 2, β = 1, γ = 0 więc fn = 5n−1 α + (

hn = 2 · 5n−1 + (

5n−1 − n 5n − 5 + ). 4 16

Uwaga 2.1. (i) Parametryzując równanie rekurencyjne, które zawiera funkcje np. 1, n2 , czasem lepiej jest dorzucić jeszcze jeden parametr z funkcją n. Na przykład Tn = Tn−1 + 3n2 − 5, n ≥ 1, dobrze jest sparametryzować do Tn = Tn−1 + αn2 + βn + γ, n ≥ 1. Podobnie, jeżeli występuje wyraz n w najwyższej potędze k to niezależnie od innych wyrazów, przy parametryzacji należy rozważać wielomian αnk + βnk−1 + γnk−2 + ... . (ii) Jeżeli w równaniu rekurencyjnym przy Tn−1 występuje zależny od n Q wyraz an to należy również rozważyć funkcję nk=1 ak . W szczególności dla rekurencji Tn = nTn−1 + 2n4 − 4, n ≥ 1, należy rozważyć funkcje: 1, n, n2 , n3 , n4 , n!, a w rekurencji Tn = 3Tn−1 +2n, n ≥ 1, funkcje 1, n, 3n .

Wstęp do rekurencji, metoda repertuaru (iii) Jeżeli mamy rekurencję postaci h(j) = αj , dla 1 ≤ j < d,

h(dn + j) = ch(n) + βj , dla 0 ≤ j < d, n ≥ 1 to rozwiązaniem tej rekurencji jest h(n) = h((bm bm−1 b . . . b1 bo )d ) = (αbm , βbm−1 , βbm−2 , . . . βb1 , βbo )c , P

k gdzie (cm cm−1 cm−2 . . . co )d = m k=0 ck d jest zapisem liczby w systemie o podstawie liczenia d (pseudozapisem, bo cyfry ci , i ≥ 0, niekoniecznie są nieujemne i mniejsze od d), a n = (bm bm−1 b . . . b1 bo )d .

Przykład 2.1. Niech f (1) = 5, f (2) = 11, f (3n) = 7f (n) + 12, f (3n + 1) = 7f (n) − 2,

f (3n + 2) = 7f (n) + 8, n ≥ 1. Jeśli chcemy obliczyć f (19) to ponieważ 1910 = 2013 a β0 = 12, α1 = 5, β1 = −2, α2 = 11, β2 = 8, więc f (1910 ) = f ((201)3 ) = (α2 β0 β1 )7 = (11, 12, −2)7 = 11 · 72 + 12 · 7 − 2 = 621.

ZADANIA Zad. 2.1. Podwójna wieża z Hanoi składa się z 2n krążków n różnych rozmiarów po dwa krążki każdego rozmiaru. Ile operacji przesunięcia potrzeba na przeniesienie tych krążków na jedną z wolnych iglic, przy czym nie wolno położyć większego krążka na mniejszy ale możemy położyć krążek na krążek tego samego rozmiaru?

19

20

Wstęp do rekurencji, metoda repertuaru Zad. 2.2. Niech Wn oznacza minimalną liczbę ruchów koniecznych do przeniesienia n krążków, przy założeniu, że mamy do dyspozycji 4 a nie 3 iglice. Rysunek 2.2. Wieża w Hanoi z 4 iglicami.

Udowodnij, że dla dowolnego 0 ≤ k ≤ n zachodzi Wn = 2Wn−k + hk , n ≥ 1, (hn minimalna ilość ruchów w ”zwykłej” wieży z Hanoi). Zad. 2.3. Wyprowadź rekurencję na maksymalną liczbę obszarów jakie wycina z płaszczyzny n nieskończonych liter V (dwóch półprostych startujących z tego samego punktu). Zad. 2.4. Wyprowadź rekurencję na maksymalną liczbę obszarów jakie wycina z płaszczyzny n trójkątów które możemy tylko przesuwać (bez obracania). Zad. 2.5. Wyprowadź rekurencję na maksymalną liczbę obszarów jakie wycina z płaszczyzny n trójkątów równobocznych, które możemy tylko obracać (bez przesuwania). Zad. 2.6. Wyprowadź rekurencję na maksymalną liczbę obszarów jakie wycina n par okręgów stycznych wewnętrznie. Zad. 2.7.⋆ Załóżmy, że w kręgu stoi 2n osób. Pierwsze n stanowią ”dobrzy” a drugie n ”źli”. Pokaż, że zawsze można dobrać liczbę m tak, że przy eliminowaniu w problemie Flawiusza co m-tej osoby po n-krokach zostaną wszyscy ”dobrzy”. Zad. 2.8. Rozwiąż rekurencję: (

Ro = α, R1 n−1 Rn = 1+R Rn−2 ,

= β, n > 1.

Zad. 2.9. Rozwiąż rekurencję: (

Ro = 1, R1 = 2, R2 +Rn−2 , n > 2. Rn = 1+Rn−1 Rn−3

=

5,

21

Wstęp do rekurencji, metoda repertuaru Zad. 2.10. Rozwiąż rekurencję:    go

g1

 

= 1, = 3,

gn =

2 gn−1 gn−2 , n

≥ 2.

Zad. 2.11. Rozwiąż rekurencję: (

g(2) = 0, √ g(n) = 2g( n) + 1, n ≥ 1.

k

dla n postaci 22 gdzie k jest pewną liczbą naturalną. Zad. 2.12. Rozwiąż rekurencję:    ao = 1,

n n   nan = 4 − 2

n−1 P k=0

kak , 2k

n = 1, 2, ....

Zad. 2.13. Rozwiąż metodą repertuaru: (

g(1) = α g(2n + j) = g(n) + βn + j, j = 0, 1, n > 1.

Zad. 2.14. Rozwiąż metodą repertuaru: (

h(1) = α h(2n + j) = 4h(n) + γj n + δj , j = 0, 1, n > 1.

Zad. 2.15. Oblicz h(125) gdzie                       

h(1) h(2) h(3) h(4n) h(4n + 1) h(4n + 2) h(4n + 3)

= = = = = = =

3 1 5 3h(n) − 2, 3h(n) + 5, 3h(n) − 3, 3h(n).

22

Wstęp do rekurencji, metoda repertuaru Zad. 2.16. Oblicz h(312) gdzie (

h(j) = 2j − 1, j = 1, 2, 3, 4 h(5n + j) = 2h(n) + j 2 , j = 0, 1, 2, 3, 4, n ≥ 1.

Rozwiąż następujące rekurencje metodą repertuaru: Zad. 2.17. (

T1 = 7, Tn = 4Tn−1 +

5 3n ,

dla n > 1.

To = 0, Tn = nTn−1 − 5n,

dla n > 0.

Zad. 2.18. (

Zad. 2.19.

Zad. 2.20.

Zad. 2.21.

(

(

(

g1 = 2, gn+1 = 2gn + 7, n = 1, 2, 3, ....

g1 = 1, gn+1 = gn + n2 + 3, n = 1, 2, 3, ....

g1 = −3, gn+1 = 3gn + n − 1, n = 1, 2, 3, ....

Zad. 2.22. (

g1 = −3, gn+1 = 2gn + n2 − 1, n = 1, 2, 3, ....

Rozdział 3 Sumy i ich obliczanie, metoda czynnika sumacyjnego (36)

24

Sumy i ich obliczanie, metoda czynnika sumacyjnego

1o Rozwiązywanie rekurencji metodą czynnika sumacyjnego Metodą tą możemy rozwiązywać jedynie rekurencję postaci (lub dające się sprowadzić do postaci): (

ao To = co , an Tn = bn Tn−1 + cn , dla n ≥ 1,

(3.1)

gdzie bn 6= 0, n ≥ 1. Kładąc sn =

n Y ai−1 ao a1 ...an−1 = , n ≥ 1, b1 b2 ...bn bi i=1

rozwiązaniem tej rekurencji jest Tn =

1 sn an (s1 b1 To

+

Pn

(3.2)

n ≥ 0.

k=1 sk ck ),

Przykład 3.1. Rozwiąż rekurencję metodą czynnika sumacyjnego: (

T0 = 3, 5Tn = nTn−1 + 2 · n!, n ≥ 1.

Porównanie powyższej rekurencji z rekurencją (3.1) prowadzi do 1, n = 0, 5, n ≥ 1, ( 3, n = 0, = 2 · n!, n ≥ 1,

an = cn

(

bn = n, n ≥ 1, sn =

ao a1 ...an−1 b1 b2 ...bn

=

5n−1 n!

i wstawiając do wzoru (3.2) otrzymujemy: n X n! 5k−1 · k!) (1 · 1 · 3 + 2 5n k! k=1

Tn =

n X n! 5k−1 ) (3 + 2 5n k=1

=

5n − 1 n! (3 + ) 5n 2 (5n−1 + 1) · n! . 2 · 5n−1

= =

2o Obliczanie sum metodą zaburzania P Sumę Sn = nk=1 ak metodą zaburzania możemy obliczyć wtedy, gdy istnieją jakieś proste funkcje fn takie, że fn (

n X

k=1

ak ) =

n+1 X k=2

ak , n ≥ 1.

25

Sumy i ich obliczanie, metoda czynnika sumacyjnego Wtedy obliczenie sumy Sn sprowadza się do rozwiąnia równiania fn (Sn ) = Sn + an+1 − a1 . Można również stosować metodę zaburzania do sum postaci Sn = Wtedy potrzebne są nam dwa ciągi funkcji: fn (

n X

k=1 n X

gn (

n+1 X

an,k ) =

k=2 n X

an,k ) =

k=1

k=1

Pn

k=1 an,k .

an+1,k , n ≥ 1, an+1,k , n ≥ 1.

Rozpisując sumę dwoma sposobami Sn+1 = an+1,1 +

n+1 X

an+1,k

k=2

= an+1,1 + fn (Sn ) =

n X

an+1,k + an+1,n+1

k=1

= gn (Sn ) + an+1,n+1 otrzymujemy równanie względem Sn : an+1,1 + fn (Sn ) = gn (Sn ) + an+1,n+1 , n ≥ 1. Przykład 3.2. Jeśli an = 3n to funkcja f (x) = 3x (fn = f, n ≥ 1) spełnia f (Sn ) = 3Sn =

n+1 X

3k

k=2

a zatem wystarczy rozwiązać równanie f (Sn ) = 3Sn = Sn + 3n+1 − 3 a stąd Sn =

3n+1 − 3 , n ≥ 1. 2

3o Metody różnicowe obliczania sum Jeśli wprowadzimy operator różnicowy (odwzorowujący funkcję w funkcję) wzorem (△f )(k) = f (k + 1) − f (k), k ∈ N

26

Sumy i ich obliczanie, metoda czynnika sumacyjnego oraz indukcyjnie (△n f )(k) = (△n−1 (△f ))(k) to tak wprowadzony operator jest odwrotny w stosunku do operatora tym sensie, że b X

(△f )(k) = f (b + 1) − f (a),

k=a

P

w

a, b, ∈ N .

Zdefiniujmy jeszcze funkcję m-ta dolna silnia od x przez xm =

   x(x − 1)(x − 2)...(x − m + 1),

1,

 

1 (x+1)(x+2)(x+3)...(x+(−m)) ,

dla m > 0, dla m = 0, dla m < 0.

Wtedy zachodzą następujące twierdzenia: Twierdzenie 3.1. Dla dowolnych liczb całkowitych m 6= 0, a, n zachodzi △(x + a)m △ax △xn △ cos(x)

1 △Hx−1 = x,

x △ nx = n−1 , 1 △ sin(x) = 2 sin( 2 ) cos(x + 12 ),

m(x + a)m−1 , (a − 1) · ax , Pn n
n−k , k=1 k x 1 −2 sin( 2 ) sin(x + 12 ).

= = = =

gdzie tutaj i w całym zbiorze Hn =

n X 1

k=1

k

, n ≥ 1,

oznacza sumy częściowe ciągu harmonicznego. Jako konsekwencję otrzymujemy Twierdzenie 3.2. Dla dowolnej liczby całkowitej m oraz naturalnych n i rzeczywistego a 6= 1 mamy n−1 X

k

m

=

k=0

n−1 X k=0

ak =

 

1 m+1 m+1 (n

 Hn

− 0m+1 )

dla m 6= −1, dla m = −1,

an − 1 . a−1

Ponadto analogicznie do wzorów na różniczkowanie iloczynu i ilorazu funkcji mamy: △(f · g)(x) = f (x)(△g)(x) + (△f )(x)g(x + 1) = (f (△g) + (△f )(Eg))(x), f  (△f )g − f (△g) (△f )(x)g(x) − f (x)(△g)(x) = (x). (x) = △ g g(x)g(x + 1) gEg

Sumy i ich obliczanie, metoda czynnika sumacyjnego a stąd możemy uzyskać wzór na różnicowanie przez części: n−1 X k=0

f (k) · △g(k) = f (k) · g(k)|n0 −

n−1 X

(△f )(k)g(k + 1).

k=0

Wyniki te są bardzo silnym narzędziem obliczania wielu typów sum. Przykład 3.3. Oblicz sumę: n−1 X k=0

(k3 − 5k2 − k3k −

k+3 ). (k + 1)(k + 2)

Ponieważ k+2+1 k+3 = = k−1 + k−2 , (k + 1)(k + 2) (k + 1)(k + 2) k3 = k3 + 3k2 + k1 , k2 = k2 + k1 , więc n−1 X

n−1 X k+3 (k − 5k − )= k3 − 2k2 − 4k1 − k−1 − k−2 (k + 1)(k + 2) k=0 k=0 3

2

1 4n 2 3n 1 −1 n k | − k | − 2k2 |n0 − Hn − k |0 4 0 3 0 −1 n(n − 1)(n − 2)(n − 3) 2n(n − 1)(n − 2) = − 4 3 1 −2n(n − 1) − Hn + − 1. n+1 =

Pozostaje tylko obliczyć mamy n−1 X

k3k =

k=0

=

Pn−1 k=0

k3k . Ze wzoru na różnicowanie przez części

n−1 X X 1 1 n−1 k△(3k ) = k3k |n0 − △(k1 )3k+1 2 k=0 2 k=0

X (n − 3)3n + 3 1 n 3 n−1 △(3k ) = n3 − . 2 2 k=0 2

4o Własności sum Podstawowe własności sum streszczamy poniżej:

27

28

Sumy i ich obliczanie, metoda czynnika sumacyjnego

X

cak = c

k∈K

X

k∈K

(ak ± bk ) = X

X

k∈K n X

ak +

X

k∈K′

k∈K

ak ±

n X

k=m

prawo jednorodności,

bk ,

prawo addytywności,

ap(k) ,

prawo przemienności,

X

k∈K

X

ak =

p(k)∈K

X

ak +

k∈K∪K′

(ak+1 − ak ) =

k=m

X

ak =

ak ,

k∈K

X

k∈K

X

prawo łączenia zbiorów

ak ,

k∈K∩K′

indeksów sumowania,

△(ak ) = an+1 − am , prawo składania (“telescoping”),

gdzie p(k) : K → K jest funkcją różnowartościową i ”na”. Szczególnie prawo przemienności i łączenia zbiorów indeksów sumowania są przydatne do obliczania sum wielokrotnych. Dla sum wielokrotnych kluczowe jest sprowadzenie tych sum do kilku pojedynczych sum. W tym celu stosujemy jedną z dwóch wersji przemienności sumowania: X X

aj,k =

j∈J k∈K

X X

j∈J k∈K(j)

aj,k =

X

aj,k =

aj,k ,

wersja waniliowa,

X

aj,k ,

wersja bakaliowa.

k∈K j∈J

j∈J k∈K

X

X X

aj,k =

X

k∈K′

j∈J k∈K(j)

j∈J ′ (k)

Przykład 3.4. Niech Zn (r, p) =

n X

k=1

Hrk+p, r, p ∈ Z.

Wyraź sumę Sn =

1 , 3j − 2i 2≤i 0) zachodzi: ⌈

n n+m−1 ⌉=⌊ ⌋. m m

Zad. 4.4. Znajdź dla x > 0 sumę wszystkich wielokrotności x znajdujących się w przedziale domkniętym [α, β], półotwartych (α, β] i [α, β) oraz otwartym (α, β).

41

Funkcje całkowitoliczbowe Zad. 4.5. Dla x > 0 znajdź iloczyn wszystkich wielokrotności x znajdujących się w przedziale domkniętym [α, β], półotwartych (α, β] i [α, β) oraz otwartym (α, β). Zad. 4.6. Dla jakich rzeczywistych b > 1 zachodzi ⌊logb x⌋ = ⌊logb ⌊x⌋⌋, dla wszystkich liczb rzeczywistych x > 1. Zad. 4.7.⋆ Rozwiąż rekurencję metodą czynnika sumacyjnego (

To = 0, ⌊⌊ n3 ⌋ + 2⌋Tn = ⌊ n3 ⌋Tn−1 + 1.

Zad. 4.8.⋆ Rozwiąż rekurencję metodą czynnika sumacyjnego: (

⌊⌊ n3 ⌋

To = 0, + 3⌋Tn = ⌊ n3 ⌋Tn−1 +

1 ⌊⌊ n ⌋+1⌋ , n 3

≥ 1.

Zad. 4.9.⋆ Porównaj dwie procedury potęgowania: Listing 4.1. Obliczanie an - metoda 1 p r o e d u r e Power1 ( a : r e a l ; n : begin x :=1.0 f o r i :=1 t o n do x := x ∗ a ; end ;

positive

integer )

positive

integer )

oraz Listing 4.2. Obliczanie an - metoda 2 p r o e d u r e Power2 ( a : r e a l ; n : begin x :=1.0 i :=n w h i l e i >0 do begin i f i 6= 2 ∗⌊ i /2 ⌋ t h e n x := x ∗ a ; i := ⌊ i /2 ⌋ i f i >0 t h e n a := a ∗ a ; end ; end ;

42

Funkcje całkowitoliczbowe Ile razy będzie się wykonywać pętla ”for” w pierwszej a pętla ”while” (oszacowanie z góry i z dołu) w drugiej procedurze. √ P Zad. 4.10. Oblicz: 0≤k 1 jest liczbą naturalną. Zad. 5.3.⋆ Znajdź x taki, że px ||n! dla pierwszej liczby p i naturalnej n.

Zad. 5.4.⋆ Udowodnij, że K = 1 + 12 + 31 + . . . + n1 nie jest liczbą całkowitą dla n > 1, n ∈ N .

1 Zad. 5.5.⋆ Udowodnij, że K = 1+ 31 + 51 +. . .+ 2n−1 nie jest liczbą całkowitą dla n > 1, n ∈ N .

Zad. 5.6.⋆ Niech a1 , a2 , . . . , an , n ≥ 1, będą niezerowymi liczbami całkowitymi. Przypuśćmy, że istnieje liczba pierwsza p i dodatnia liczba całkowita k takie, że pk |ai dla pewnego i oraz pk 6 | aj dla j 6= i. Udowodnij, że K = a11 + a12 + a13 + . . . + a1n nie jest liczbą całkowitą. Zad. 5.7. Udowodnij, że (a) 13|106 − 1, (b) 17|108 + 1,

55

56

Teoria liczb (c) 19|109 + 1, (d) Jeśli 3 6 |n to 3|n4 + n2 + 1. n

Zad. 5.8. Udowodnij, że 3|22 − 1. Zad. 5.9. Znajdź x, y ∈ Z takie, że x ≥ 0, y ≥ 0, N W D(a, b) = xa + yb gdy: (a) a = 1024, b = 10024 (b) a = 10024, b = 124 Zad. 5.10. Jak zważyć 32 g produktu na wadze szalkowej posiadając tylko odważniki 64 i 48 gramowe. Zad. 5.11. Uzyskaj 86 litrów płynu w naczyniu C o pojemności 1000 litrów stosując menzurki A i B odpowiednio o pojemnościach 64 i 53 litry. Zad. 5.12. Znajdź rozkład na czynniki pierwsze liczb n = 33, n = 55, n = 333, n = 555. Zad. 5.13. Znajdź rozkład na czynniki pierwsze liczb n = 33 · 55, n = 333 · 555. Zad. 5.14. Znajdź na podstawie rozkładu na czynniki pierwsze wartości N W D(256, 96) i N W W (256, 96). Zad. 5.15. Niech n = [0, 2, 5, 4, 12, 7, 1]; m = [0, 5, 1, 5, 1]; k = [0, 0, 0, 1, 0, 1, 2]. Oblicz N W D(N W D(k, m), k · N W W (n, m)). Zad. 5.16. Niech n = [0, 15, 3, 13, 0, 2, 7]; m = [0, 1, 1, 0, 1]; k = [0, 3, 2, 1, 0, 1, 2]. Oblicz N W D(N W W (k, m), k · N W D(n, m)). Zad. 5.17. Rozłożyć na czynniki pierwsze liczbę 100!. Zad. 5.18. Iloma zerami zakończone jest rozwinięcie dziesiętne liczby 1000!. Zad. 5.19. Iloma zerami jest zakończone przedstawienie w systemie szesnastkowym liczby 200! ? Zad. 5.20. Udowodnij, że jeśli n jest liczbą złożoną, to n ma dzielnik √ pierwszy nie przekraczający n. Zad. 5.21.⋆ Udowodnij, że jeśli n jest liczbą złożoną i najmniejsza liczba √ pierwsza p będąca dzielnikiem n przekracza 3 n, to np = 1 lub np jest liczbą pierwszą. Zad. 5.22. Niech p będzie liczbą pierwszą. Udowodnij, że p| k ≤ p − 1.

Zad. 5.23.⋆ Niech p będzie liczbą pierwszą. Udowodnij, że p|(

p
k

dla 1 ≤

np
p

− n).

57

Teoria liczb Zad. 5.24.⋆ Niech a, b będą względnie pierwszymi liczbami naturalnymi takimi, że ab = nk dla pewnych liczb naturalnych n i k. Pokaż, że istnieją liczby naturalne c i d takie, że a = ck i b = dk . Zad. 5.25.⋆ Udowodnij, że jeśli x, y i z są parami względnie pierwszymi liczbami naturalnymi będącymi rozwiązaniem równania x2 + y 2 = z 2 , to istnieją względnie pierwsze liczby naturalne a i b, z których jedna jest parzysta, takie, że x = a2 − b2 , y = 2ab i z = a2 + b2 (z dokładnością do zamiany miejscami liczb x i y). Zad. 5.26.⋆ Udowodnij, że x4 + y 4 = z 2 nie ma nietrywialnych rozwiązań naturalnych. Zad. 5.27.⋆ Udowodnij, że x4 − y 4 = z 2 nie ma nietrywialnych rozwiązań naturalnych. Zad. 5.28. Wyznacz wszystkie pary liczb względnie pierwszych występujące w zbiorze [14, 24] ∩ N ([14, 24]− domknięty przedział). Zad. 5.29.⋆ Niech pk oznacza k-tą liczbę pierwszą, k ≥ 1. Udowodnij, że k pk < 22 . W s k a z ó w k a. Udowodnij, że pk ≤ p1 p2 · · · pk−1 + 1. Zad. 5.30.⋆ Udowodnij, że π(x) ≥ log(log(x)) dla x > 1. √ Zad. 5.31.⋆ Udowodnij, że x ≤ 2π(x) . W s k a z ó w k a. Wykorzystaj fakt, że każda liczba naturalna może być przedstawiona w postaci mn2 gdzie m jest liczbą bezkwadratową (to znaczy, że nie istnieje w faktoryzacji liczby m żadna liczba pierwsza z wykładnikiem większym od 1). Zad. 5.32. Udowodnij, że π(x) ≥ Zad. 5.33.⋆ Udowodnij, że π(x) ≤

log(x) 2 log(2) . 9x log(x) log(2) ,

dla x ≥ 2. Q

W s k a z ó w k a. Wykorzystaj fakt, że (

2n
n −m, xj ≥ 0, j 6= i, 1 ≤ j ≤ k} dla pewnego 1 ≤ i ≤ k, to wtedy robimy podstawienie x′j = xj , j 6= i, x′i = xi + m, i widzimy, że Ln,k ({xi ≥ −m, xj ≥ 0, j 6= i, 1 ≤ j ≤ k}) = Ln+m,k (Wo ). 4o Podziały zbioru

Liczba podziałów zbioru n elementowego takich, że: jest λ1 klas o liczebności 1, jest λ2 klas o liczebności 2, .. . jest λn klas o liczebności n, gdzie n = 1 · λ1 + 2 · λ2 + ... + n · λn , wynosi P λ1 ,λ2 ,...,λn =

n! . λ1 !λ2 !...λn !(1!)λ1 (2!)λ2 ...(n!)λn

Na przykład zbiór {a, b, c, d, e} można podzielić na dwa zbiory o liczebności 1 i jeden zbiór o liczebności 3 w następujący sposób: {{a} {b} {c, d, e}} {{a} {c} {b, d, e}} {{a} {d} {b, c, e}} {{a} {e} {b, c, d}} {{b} {c} {a, d, e}} {{b} {d} {a, c, e}} {{b} {e} {a, c, d}} {{c} {d} {a, b, e}} {{c} {e} {a, b, d}} {{d} {e} {a, b, c}}

(6.1)

Taki podział nazywamy podziałem 12 31 . Przez S(n, k) oznaczać będziemy liczbę podziałów zbioru n-elementowego na k-klas i nazywamy liczbą Stirlinga II-go rodzaju. Liczby te spełniają następujące równanie rekurencyjne:   S(n + 1, k)   

S(n, 1)

 S(n, 0)   

S(0, 0)

= = = =

S(n, k − 1) + kS(n, k), S(n, n) = 1, 0, 1,

dla 1 ≤ k < n, dla n > 0, dla n > 0,

(6.2)

Liczbę s(n, k) podziałów zbioru n-elementowego na k cykli nazywamy liczbą Stirlinga I-go rodzaju. Liczby Stirlinga pierwszego rodzaju spełniają następujące równanie rekurencyjne:   s(n + 1, k)    s(n, 1)  s(n, n)   

s(n, 0)

= = = =

s(n, k − 1) + ns(n, k), (n − 1)!, 1, 0,

dla dla dla dla

1 ≤ k < n, n ≥ 1, n ≥ 0, n > 0.

(6.3)

68

Kombinatoryka Podział liczby n na k składników jest przedstawieniem n w postaci sumy a0 + . . . + ak−1 = n, gdzie a0 ≤ a1 ≤ . . . ≤ ak−1 ≤ 1. Liczbę podziałów n na k składników oznaczamy przez P (n, k). Na przykład podziały 8 na 4 składniki są następujące: 1+1+1+5,

1+1+2+4,

1+1+3+3

1+2+2+3

2+2+2+2,

a więc P (8, 4) = 5. 5o Klasyfikacje podziałów (i) Klasyfikacji n rozróżnialnych obiektów na k rozróżnialne kategorie jest n V k czyli kn . Takich klasyfikacji na dokładnie k kategorii jest k!S(n, k). (ii) Klasyfikacji rozróżnialnych obiektów na nierozróżnialne kategorie jest Pk i=1 S(n, i). Oczywiście gdy wszystkie kategorie są niepuste, to zbiór obiektów jest podzielony na dokładnie k bloków. Liczba takich konfiguracji wynosi S(n, k). (iii) Klasyfikacji nierozróżnialnych obiektów na rozróżnialne kategorie jest tyle ile podziałów liczby n na sumę n = x0 + . . . + xk−1 liczb natu
ralnych xi . Liczba rozwiązań takiego równania jest równa n+k−1 k−1 . A jeśli kategorii, czyli składników w rozkładzie n = x0 + . . . + xk−1 , ma być dokładnie k, to zliczamy jedynie rozwiązania spełniające dodatkowo
x0 , . . . , xk−1 ≥ 1, a tych jest n−1 . k−1 (iv) Klasyfikacji nierozróżnialnych obiektów na rozróżnialne kategorie jest P (n, k). Jeżeli dopuszczamy puste kategorie, to liczba konfiguracji jest sumą

k X

P (n, k).

i=1

6o Współczynniki dwumianowe Dla liczb rzeczywistych r i całkowitych k: r k

!

=

(

r(r−1)(r−2)...(r−k+1) k(k−1)(k−2)...2·1 ,

0,

k ∈ Z+ ∪ {0}, = k ∈ Z− ,

(

rk k! ,

0,

k ∈ Z+ ∪ {0}, k ∈ Z− ,

(r 0 = 1.) Wzór na dwumian Newtona. Niech x, y będą dwoma dowolnymi liczbami rzeczywistymi. Jeśli liczba całkowita r jest niedodatnia lub | xy | < 1 to X r r (x + y) = xk y r−k . k k∈Z

69

Kombinatoryka

ZADANIA Zad. 6.1. Oblicz:

P

k∈Z

1/3
2k 2/3−2k . k 5 10

Zad. 6.2. Na ile sposobów z talii 52 kart można wylosować 10 kart tak, aby był wśród nich dokładnie jeden as? Zad. 6.3. Na ile sposobów z talii 52 kart można wylosować 10 kart tak, aby był wśród nich co najmniej jeden as? Zad. 6.4. Na ile sposobów z talii 52 kart można wylosować 6 kart tak, aby były wśród nich karty wszystkich kolorów? Zad. 6.5. Na ile sposobów spośród n małżeństw można wylosować jedną kobietę i jednego mężczyznę, którzy nie są małżeństwem? Zad. 6.6. Sadzamy n osób przy okrągłym stole. Dwa rozsadzenia uważamy za identyczne, jeśli w obu przypadkach każda osoba ma tych samych sąsiadów. Ile jest możliwych sposobów rozsadzeń? Zad. 6.7. Na ile sposobów można posadzić przy okragłym stole n kobiet i n mężczyzn tak, aby żadne dwie osoby tej samej płci nie siedziały obok siebie? Dwa rozsadzenia uważamy za identyczne, jeśli w obu przypadkach każdy człowiek ma tych samych sąsiadów. Zad. 6.8. Na ile sposobów można rozmieścić k nierozróżnialnych kul w n ponumerowanych szufladach, przy założeniu, że w każdej szufladzie może znaleźć się co najwyżej jedna kula? Zad. 6.9. Na ile sposobów można rozmieścić k rozróżnialnych kul w n ponumerowanych szufladach, przy założeniu, że w każdej szufladzie może znaleźć się co najwyżej jedna kula? Zad. 6.10. Ile jest permutacji zbioru 1, ..., n, w których żadne dwie sąsiednie liczby nie są parzyste? Zad. 6.11. Restauracja serwuje 5 zup, 6 drugich dań i 2 desery. Na ile sposobów można skomponować pełny obiad? Jak wiele obiadów złożonych z dwóch składników można skomponować? Zad. 6.12. Cztery osoby: A, B, C i D postanowiły ustanowić komitet rewolucyjny: komisarz rewolucyjny, pierwszy sekretarz, przewodniczący i skarbnik. Na ile sposobów mogą rozdzielić te zaszczytne funkcje? Na ile sposobów można rozdzielić te funkcje spośród 20 spiskowców?

70

Kombinatoryka Zad. 6.13. Ankieterzy poprosili respondenta o wybór 3 najlepszych (wg. niego) spośród 8 samochodów. Na ile sposobów można to uczynić? Zad. 6.14. Jak wiele binarnych (zawierających tylko 0 i 1) ciągów długości 13 ma dokładnie 5 zer? Ile jest takich ciągów zawierających więcej 0 niż 1? Zad. 6.15. Udowodnij: (a) (b) (c) (d) (e) (f ) (g) (h) (i)

Pn


Pn k nk
k=1 Pn 2 n k=1
k k
Pn n n 2 k=1 k k
n−k
Pk n n−l Pkl=0 ml
k−l n
l=0 P l k−l n


k=0

= = = = = = Pnk≥0 2k k
= k=m m n
n−k = (m − 1) k Pn 3 = k=1 k

n2n−1 , n(n − 1)2n−2 + n2n−1 ,
n2 2n−2 , n−1 n
k k 2 , m+n
, Pk n
k≥0
2k+1 , n+1 m+1 , mn , n+1
2 . 2

Zad. 6.16. Ile jest liczb całkowitych dodatnich nie większych niż 10000 podzielnych przynajmniej przez jedną z liczb 2, 3, 5? Zad. 6.17. Ile jest całkowitoliczbowych rozwiązań równania x1 +· · ·+x6 = 30 spełniających poniższe warunki? (a) 0 ≤ xi ≤ 10, i = 1, . . . , 6, (b) −10 ≤ xi ≤ 20, i = 1, . . . , 6, (c) x1 ≤ 5, x2 ≤ 10, x3 ≤ 15, x4 ≤ 20, xi ≥ 0, i = 1, . . . , 6. Zad. 6.18. Na ile sposobów z talii 52 kart można wybrać 5 kart tak, aby otrzymać co najmniej jednego asa, co najmniej jednego króla i co najmniej jedną damę? Zad. 6.19. Ile jest permutacji zbioru 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, w których pierwsza liczba jest większa od 2, a ostatnia jest mniejsza od 9? Zad. 6.20. Ile jest ciągów długości n, n ≥ 3, złożonych z cyfr 0, 1, . . . , 9 takich, że każda z cyfr 1, 2, 3 występuje w każdym z ciągów co najmniej raz? Zad. 6.21. Ile jest macierzy zero-jedynkowych o wymiarach n na n, w których co najmniej jeden wiersz jest zerowy? Zad. 6.22. Ile jest układów kart do brydża wsród których są dokładnie cztery karty tej samej wysokości? Zad. 6.23. Ile jest układów możliwych rzutów dziesięć razy dwoma kostkami do gry, gdy uzyskujemy wszystkie pary {i, i}, gdzie i = 1, . . . , 6.

71

Kombinatoryka Zad. 6.24. Przy okrągłym stole sadzamy n małżeństw, na przemian kobietę i mężczyznę. Ile jest takich rozsadzeń, że żadne małżenstwo nie będzie siedziało obok siebie? Zad. 6.25. Na kanapie sadzamy n małżeństw, na przemian kobietę i mężczyznę. Ile jest takich rozsadzeń, że żadna małżonka nie będzie siedzieć po prawej stronie męża? Zad. 6.26. Oblicz Q k2
(a) nk=2 3k , Qn k 2 −1
(b) k=2 2k+3 , (c) (d) (e) Zad. (a) (b) (c) (d)

2 35
, 4 −1
k , n−1 n n! .

6.27. Oblicz
√ P −k 3 k∈Z 1/2 k 3 ,
P 1/3 −k k∈Z k 3 , P 1/3
2k 2/3−2k 5 10 , k∈Z √ P k 1/3
3 k −2k 9 k∈Z k (−1) 3 .

Zad. 6.28. (Ulice Manhattanu) Manhattan - dzielnica Nowego Yorku, słynie z ulic wytyczonych pod kątem prostym. Wyobraźmy sobie kratę utworzoną z 5 ulic biegnących poziomo (wschód-zachód) i 8 ulic biegnących pionowo (północ-południe). Znajdujemy się w lewym dolnym rogu A i chcemy przejść najkrótszą drogą do prawego górnego rogu B. Na ile sposobów możemy to zrobić? Zadanie uogólnij dla C(n, m) - ilości przejść gdy jest n ulic w prawo i m w górę. B

r

rA

Zad. 6.29.⋆ Podobnie jak w zadaniu 6.28 rozważamy kratę kwadratową n × n i drogi z lewego dolnego rogu do prawego górnego, jednak tylko takie drogi, które nie przecinają głównej przekątnej kwadratu (łączącej punkty A i B) a przechodzą poniżej tej przekątnej. Oblicz Cn - ilość takich dróg. Zad. 6.30. Przypuśćmy, że mamy pomalować sześć identycznych kul czterema kolorami. Na ile sposobów możemy to zrobić?

72

Kombinatoryka Zad. 6.31. W kolejce do sklepu stoi n osób, które są wpuszczane do sklepu grupami (kolejność osób w kolejce nie zmienia się). Na ile sposobów można utworzyć k niepustych grup przy wpuszczaniu osób do sklepu? Zad. 6.32. Ile rozwiązań ma równanie x1 + x2 + . . . + xk = n w dodatnich liczbach całkowitych? Zad. 6.33. W poczekalni do lekarza, w rzędzie złożonym z n krzeseł, siedzi k pacjentów, przy czym żadnych dwóch nie znajduje się obok siebie. Ile jest różnych sposobów takiego rozsadzenia pacjentów? Zad. 6.34. Pewna grupa n osób wita się podając sobie ręce, przy czym nikt nie wita się sam ze sobą i żadna para osób nie wita się więcej niż jeden raz. Czy jest możliwe aby liczba powitań wynosiła 2926? Jeśli tak, to ile było osób? Zad. 6.35. Napisano n listów i zaadresowano dla nich n kopert. Ile jest układów gdy listy wkładane są do kopert całkiem przypadkowo (ale zawsze w jednej kopercie jest dokładnie jeden list) i ile jest układów takich, że żaden list nie znajdzie się we właściwej kopercie? Zad. 6.36. Ile jest (a) podziałów liczby n na 1 część nie większą niż l, (b) podziałów liczby n na co najwyżej 2 części z których każda jest nie większa niż l, (c) podziałów liczby n na co najwyżej 3 części? Zad. 6.37. Ile jest (i) klasyfikacji n rozróżnialnych obiektów na co najwyżej k rozróżnialne kategorie (ii) klasyfikacji n rozróżnialnych obiektów na dokładnie k rozróżnialne kategorie dla (a) n = 7, k = 5, (b) n = 3, k = 2, (c) n = 5, k = 5? Wypisz te klasyfikacje. Zad. 6.38. Ile jest (i) klasyfikacji n rozróżnialnych obiektów na co najwyżej k nierozróżnialne kategorie (ii) klasyfikacji n rozróżnialnych obiektów na dokładnie k nierozróżnialne kategorie dla (a) n = 7, k = 5,

Kombinatoryka (b) n = 3, k = 2, (c) n = 5, k = 5? Wypisz te klasyfikacje. Zad. 6.39. Ile jest (i) klasyfikacji n nierozróżnialnych obiektów na co najwyżej k rozróżnialne kategorie (ii) klasyfikacji n nierozróżnialnych obiektów na dokładnie k rozróżnialne kategorie dla (a) n = 7, k = 5, (b) n = 3, k = 2, (c) n = 5, k = 5? Wypisz te klasyfikacje. Zad. 6.40. Ile jest (i) klasyfikacji n nierozróżnialnych obiektów na co najwyżej k nierozróżnialne kategorie (ii) klasyfikacji n nierozróżnialnych obiektów na dokładnie k nierozróżnialne kategorie dla (a) n = 7, k = 5, (b) n = 3, k = 2, (c) n = 5, k = 5? Wypisz te klasyfikacje. Zad. 6.41. Ile wynosi P (n, n − 2)? Zad. 6.42. DNA zapisywane jest dwoma komplementarnymi łańcuchami alfabetem czteroznakowym: adenina (A), cytozyna (C), guanina (G) i tymina (T), przy czym w drugim łańcuchu następuje zamiana wg. schematu A ↔ T, C ↔ C. Tak więc przykład DNA długości 6 mógłby wyglądać nastęA C G T A T pująco: Oba łańcuchy są między sobą nierozróżT G C A T A. nialne. Ile jest takich podwójnych łańcuchów DNA długości n? Zad. 6.43. Załóżmy, że mamy zbiór pięciu elementów {1, 2, 3, 4, 5} i każdy jego podzbiór interpretujemy w ten sposób, że w ciągu 12345 wstawiamy 1 jeżeli ten element należy do podzbioru i 0 jeżeli nie należy. Z jakich elementów składają się te podzbiory: 00000, 01101, 11011? Zad. 6.44. Ile jest różnych rozwiązań w zbiorze liczb nieujemnych całkowitych równania x + y + z = 19? A ile jest rozwiązań w zbiorze dodatnich całkowitych?

73

74

Kombinatoryka Zad. 6.45. Ile istnieje ciągów binarnych w których jest dokładnie p 1 i q 0, q > p − 1, takich, że żadne dwie cyfry 1 nie stoją obok siebie?


P

P

Zad. 6.46. Wykaż, że jeżeli an = nk=0 nk bk , n ≥ 0, to bn = nk=0 (−1)n−k
Pn n+k n a , n ≥ 0. Można to zapisać również korzystając z fragmenk=0 (−1) k k tu trójkąta Pascala: 

A−1 =

        



=

        

1 1 1 1 .. .

n
0

(−1)n

0 1 2 3 .. .

0 0 1 3 .. .

n
2

0 0 0 1 .. .

n
3

1 −1 1 −1 .. . n
0

... ... ... ... .. .

n
4

0 0 0 0 .. .

n
n

... 0 1 −2 3 .. .

(−1)n−1

n
2

−1         

0 0 1 −3 .. .

(−1)n−2

n
3

0 0 0 1 .. .

(−1)n−3

n
4

... ... ... ... .. . ...

Zad. 6.47. Udowodnij, że !

!

!

n n n + + + . . . = 2n−1 . 0 2 4 Zad. 6.48. Udowodnij, że !

!

!

n n n n − + + . . . + (−1)k 0 1 2 k

!

= (−1)k

Zad. 6.49. Udowodnij, że X k

r k

!

s n−k

!

=

!

r+s . n

Zad. 6.50. Udowodnij, że X k

m k k

!

n k

!

n
k ak

!

n+m−1 =n . n

!

n−1 . k

0 0 0 0 .. .

n
n



     = B.    

=

75

Kombinatoryka Zad. 6.51. Ile jest rozwiązań w zbiorze liczb całkowitych równania: x + y + z + w = 15, dla x > −5, y > 4, −2 < z < 5, 3 ≤ w ≤ 7. Zad. 6.52. Znajdź ilość nieujemnych liczb całkowitych spełniających nierówność x1 + x2 + x3 + . . . + xk ≤ n, n, k ≥ 0. √ √ Zad. 6.53. Niech ω = 12 (−1 + i 3), i = −1, będzie liczbą zespoloną, wtedy ω 3 = 1, ω 2 + ω + 1 = 0. Kładąc x = 1, y = ω, we wzorze na dwumian Newtona udowodnij, że !

!

!

n n n 1 nπ + + + . . . = (2n + 2 cos ). 0 3 6 3 3

Rozdział 7 Funkcje tworzące (35)

78

Funkcje tworzące

1o Funkcje tworzące i splot Dla dwóch ciągów [ao , a1 , a2 , ...] oraz [bo , b1 , b2 , ....] odpowiadających funkP∞ P k z k splot jest to ciąg cjom tworzącym A(z) = ∞ k=0 bkP k=0 sk z i B(z) = odpowiadający funkcji tworzącej C(z) = A(z)·B(z) = [ nk=0 ak bn−k , n ≥ 0]. Niektóre częściej używane funkcje tworzące:

Ciąg

Suma

[1, 0, 0, 0, . . .] [ 0, . . . , 0, 1, 0, 0, . . .]

P

n≥0 [n

P

n≥0 z

n

n≥0 z

n [n

|

{z

P

}

m

[1, 1, 1, 1, . . .]

P

[ 1, . . . , 1, 0, 0, . . .] | {z } m

[1, −1, 1, −1, . . .] [1, 0, 1, 0, . . .] [1, 0, . . . , 0, 1, 0, . . . , 0, 1, . . .] |

{z m

} |

[1, 2, 3, 4, . . .]

{z m

[1, 2, 4, 8, . . .] [12 , 22 , 32 , 43 , 52 , . . .]

}

c
c
2 , 3 , . . .]
c+2
[1, c, c+1 2 , 3 , . . .] [1, c, c2 , c3 , . . .]

[1, c,

[0, c, 2c2 , 3c3 , 4c4 , . . .] [0, 1, 21 , 13 , 14 , . . .] [0, 1, − 21 , 13 , − 14 , . . .] [ 0!1 , 1!1 , 2!1 , 3!1 , . . .] [F0 , F1 , F2 , F3 , F4 , . . .] [H0 , H1 , H2 , H3 , H4 , . . .]

Zwarty wzór 0]z n

= n n≥0 [n = m]z

≤ m]

1 zm 1 1−z 1−z n 1−z

P

1 1+z 1 1−z 2 1 1−z m

P

1 (1−z)2 1 1−2z 1+z (1−z)3

n n n≥0 (−1) z P n n≥0 [2|n]z P n n≥0 [m|n]z

n n≥0 (n + 1)z n n n≥0 2 z P 2 n n=0 (n + 1) z
P c n n≥0 n z P c+n−1
n z n≥0 n P n n n≥0 c z P n n n≥0 nc z P 1 n n>0 n z P n1 n n>0 (−1) n z P 1 n n≥0 n! z P n n≥0 Fn z P n n≥0 Hn z

P

Tabela 7.1. Funkcje tworzące

(1 + z)c 1 (1−z)c 1 1−cz cz (1−cz)2 1 ln( 1−z )

ln(1 + z) ez z 1−z−z 2 1 1 1−z ln( 1−z )

79

Funkcje tworzące gdzie {Fn , n ≥ 0} są to liczby Fibonacciego a {Hn , n ≥ 1} to ciąg liczb harmonicznych (zob. $2.4 [12]). 2o Rozwiązywanie rekurencji za pomocą funkcji tworzących, liczby Fibonacciego Liczby Fibonacciego są to rozwiązania następującego równania rekurencyjnego:    F0

= 0, = 1, = Fn−1 + Fn−2 dla n ≥ 2,

F

1   F n

Rozwiązaniem tej rekurencji jest: Fn =

√1 5



√ n 1+ 5 2

−



√ n  1− 5 . 2

Przykład 7.1. Rozwiąż rekurencję metodą funkcji tworzących:   g0       

= 0, g1 = 1, g2 = 5, gn = 5gn−1 − 6gn−2 , dla n ≥ 3,

• Dookreślamy gn = 0, n < 0, a ponieważ g2 = 5 = 5g1 − 6g0 ,

g1 = 1 = 5g0 − 6g−1 + [n = 1],

g0 = 0 = 5g−1 − 6g−2 , to otrzymujemy

gn = 5gn−1 − 6gn−2 + [n = 1], n ∈ Z. • Mnożymy stronami przez z n i sumujemy otrzymując X

n∈Z

gn z n = 5

X

n∈Z

gn−1 z n + 6

X

n∈Z

gn−2 z n +

X

n∈Z

Zatem G(z) = 5zG(z) − 6z 2 G(z) + z.

z n [n = 1].

80

Funkcje tworzące • Rozwiązujemy równanie wyliczając funkcję tworzącą: G(z) =

z . (1 − 2z)(1 − 3z)

• staramy się wykorzystać znane wzory na rozwinięcia funkcji w szereg potęgowy, a więc z 1 1 = − (1 − 2z)(1 − 3z) 1 − 3z 1 − 2z = [3n , n ≥ 0] − [2n , n ≥ 0] = [3n − 2n , n ≥ 0],

G(z) =

a stąd gn = 3n − 2n , n ≥ 0. 3o Algebra wielomianów rzeczywistych Algorytmu Euklidesa dla wielomianów: niech A(x) oraz B(x) będą wielomianami takimi, że deg B(x) > 0, wtedy istnieje dokładnie jeden układ wielomianów Q(x) oraz R(x) takich, że A(x) = Q(x)B(x) + R(x) gdzie deg R(x) < deg B(x). Mówimy, że wielomian B(x) jest dzielnikiem wielomianu A(x) i zapisujemy ten fakt B|A jeśli R(x) ≡ 0. Wielomian C(x) nazywamy największym wspólnym dzielnikiem wielomianów A(x) i B(x) (zapisujemy N W D(A, B)) jeśli: (i) Najwyższym współczynnikiem wielomianu C jest 1. (ii) C|A oraz C|B. (iii) Jeśli D|A i D|B to D|C. Wielomiany A(x) i B(x) nazywamy względnie pierwszymi jeżeli N W D(A, B) ≡ 1. Dla każdych dwóch wielomianów A(x) i B(x) istnieją wielomiany P (x) i Q(x) takie, że A(x)P (x) + B(x)Q(x) = N W D(A, B)(x). Mówimy, że wielomian P (x) jest pierwszy jeśli deg P (x) > 0 oraz nie istnieją wielomiany stopni dodatnich A(x) i B(x) takie, że P (x) = A(x)B(x). Dla każdego wielomianu o współczynnikach rzeczywistych A(x) istnieją liczby rzeczywiste ao , pi , qi , 1 ≤ i ≤ l, xi l + 1 ≤ i ≤ k oraz naturalne si , 1 ≤ i ≤ k, takie, że p2i − 4qi < 0, 1 ≤ i ≤ l, oraz A(x) = a0 (x2 + p1 x + q1 )s1 . . . (x2 + pl x + ql )sl (x − xl+1 )sl+1 . . . (x − xk )sk , (7.1)

81

Funkcje tworzące P

P

gdzie deg A(x) = 2 li=1 si + ki=l+1 si . Jeżeli liczba wymierna pq (p ⊥ q) jest miejscem zerowym wielomianu A(x) = an xn + an−1 xn−1 + . . . + a0 o współczynnikach całkowitych (ai ∈ Z, 0 ≤ i ≤ n) to p|a0 oraz q|an .

4o Twierdzenie o rozwinięciach wymiernych funkcji tworzą-

cych Jeśli R(x) = P (x)/Q(x), gdzie Q(x) = q0 · (1 − ρ1 x) · . . . · (1 − ρl x) i liczby ρ1 , . . . , ρl są parami różne, to w przypadku gdy P (x) jest wielomianem stopnia mniejszego niż l, zachodzi [xn ]R(x) = a1 ρn1 +. . .+al ρnl ,

dla ak =

P (1/ρk ) −ρk · P (1/ρk ) . = Q ′ Q (1/ρk ) ρ0 j6=k (1 − ρj /ρk )

Jeśli R(z) = P (z)/Q(z), gdzie Q(z) = (1 − ρ1 z)d1 ...(1 − ρl z)dl i liczby {ρ1 , ρ2 , ..., ρl } są parami różne, to w przypadku gdy P (z) jest wielomianem stopnia mniejszego niż d1 + d2 + ... + dl , zachodzi [z n ]R(z) = f1 (n)ρn1 + . . . + fl (n)ρnl ,

dla wszystkich n ≥ 0 gdzie wielomian fk (n) jest wielomianem stopnia dk − 1 z najbardziej znaczącym współczynnikiem ak =

P (1/ρk ) , 1 ≤ k ≤ l. (dk − 1)! j6=k (1 − ρj /ρk )dj Q

5o Równanie rekurencyjne liniowe jednorodne rzędu drugiego o stałych współczynnikach Równanie rekurencyjne liniowe jednorodne rzędu drugiego rn + prn−1 + qrn−2 = 0,

n ∈ N,

(7.2)

ma rozwiązania w zależności od zachowania trójmianu kwadratowego x2 + px + q = 0.

(7.3)

Jeśli • równanie (7.3)√ma dwa różne pierwiastki rzeczywiste ∆ = p2 − 4q > √ 0, α1 = (−p − ∆)/2, α2 = (−p + ∆)/2, to rozwiązanie równania (7.2) jest postaci: rn = A1 αn1 + A2 αn2 , n ≥ n0 , dla pewnych stałych A1 , A2 ,

82

Funkcje tworzące • równanie (7.3) ma jeden pierwiastek rzeczywisty △ = p2 − 4q = 0, to rozwiązanie (7.2) równania jest postaci: rn = (A1 n + A2 )(

−p n ) , 2

dla pewnych stałych A1 , A2 , • równanie (7.3) ma dwa różne pierwiastki zespolone (jest wielomianem pierwszym) α1 = r(cos(φ) + i sin(φ)), α2 = r(cos(φ) − i sin(φ)), to rozwiązanie równania (7.2) jest postaci: rn = r n (A1 cos(nφ) + A2 sin(nφ)), n ≥ n0 , dla pewnych stałych A1 , A2 , 6o Wielomiany wieżowe Definicja. Niech n, m ∈ N . Szachownicą o n wierszach i m kolumnach nazywamy każdą trójkę B = (I, J, F ), gdzie I i J są zbiorami, I = n, J = m, oraz F ⊂ I × J. Zbiór F nazywamy zbiorem pól zabronionych. Tak więc szachownica to tablica o n wierszach i m kolumnach, w której część pól to pola zabronione. Definicja. Niech B = (I, J, F ) będzie szachownica oraz k ∈ N. Rozstawieniem k wież na szachownicy B nazywamy każdy podzbiór A ⊂ I × J\F taki, że A = k oraz A\(i × J) ≤ 1 i A\(I × j) ≤ 1 (w każdym wierszu i kolumnie jest co najwyżej jedna wieża) dla wszystkich indeksow i ∈ I i j ∈ J. Ilość rozstawień k wież na szachownicy B oznaczamy przez rkB . Funkcję tworzącą ciągu {rkB , k ≥ 0} nazywamy wielomianem wieżowym i oznaczamy przez: RB (z) =

∞ X

rkB z k .

k=0

Twierdzenie 7.1. Niech B = (I, J, F ). Zachodzi: tr (a) Jeśli F tr = {(j, i) : (i, j) ∈ F }, B tr = (J, I, F tr ), to RB = RB . (b) Jeśli F = ∅ to B

R (z) =

X

k∈N

I k

!

!

J k!z k . k

(c) Jeśli σ i τ są permutacjami zbioru I i J odpowiednio, to RBσ = RB = RBτ , gdzie B = (i, J, F ), Bσ = (I, J, Fσ ), Bτ = (I, J, Fτ ), Fσ = {(σ(i), j) : (i, j) ∈ F }, Fτ = ((i, τ (j)), (i, j) ∈ F }.

83

Funkcje tworzące (d) Jeśli I = I1 ∪ I2 , J = J1 ∪ J2 , I1 ∩ I2 = ∅, J1 ∩ J2 = ∅, i ponadto (I1 × J2 ) ∪ (I2 × J1 ) ⊂ F, to RB = RB1 · RB2 , gdzie B1 = (I1 , J1 , F ∩ (I1 × J1 )), B2 = (I2 , J2 , F ∩ (I2 × J2 )), B1

B=

B2 (e) Jeśli F = (I × J)\F, B = (I, J, F ) oraz I = J = n to rnB =

n X

(−1)k · rkB · (n − k)!, n ≥ 0.

k=0

(Zwróć uwagę, że wzór ten jest prawdziwy tylko dla n-tego współczynnika.) (f ) Niech (io , jo ) ∈ (I × J)\F to jo

′

RB (z) = RB (z) + z · RBio (z), gdzie B ′ = (I, J, F ∪ {(io , jo )}), Bijoo = (I\{io }, J\{jo }, {(i, j) ∈ F : i 6= io , j 6= jo }). V (g) Jeśli dla pewnego io ∈ I : j∈J (io , j) ∈ F to RB = RBio . Jeśli dla V jo pewnego jo ∈ J : i∈I (i, jo ) ∈ F to RB = RB .

Przykład 7.2. Znajdź wielomian wieżowy następującej szachownicy

B=

Niech τ = (14325) będzie permutacją polegającą na zamianie drugiego z czwartym wierszem a σ = (13524) permutacją polegającą na wstawieniu trzeciej i piątej kolumny przed drugą, wtedy

Bτ =

Bτ ◦σ =

84

Funkcje tworzące Kładąc i0 = 3, jo = 1 widzimy z (c) i (f ) oraz (d), że RB (z) = RBτ ◦σ (z) = RC1 (z) + zRC2 (z) = RD1 (z)RD2 (z) + z(RD3 (z))2 , gdzie

C2 =

C1 =

D1 =

D2 =

D3 =

Natomiast z (b) mamy R

D1

(z) = R

D2

(z) =

2 X

k=0

R

D3

(z) =

2 X

k=0

2 k

!

3 k

!

!

2 k!z k = 1 + 6z + 6z 2 , k

!

2 k!z k = 1 + 4z + 2z 2 , k

a stąd RB (z) = (1 + 6z + 6z 2 )2 + z(1 + 4z + 2z 2 )2 = 1 + 13z + 56z 2 + 92z 3 + 52z 4 + 4z 5 .

ZADANIA Zad. 7.1. Znajdź wielomian wieżowy następującej szachownicy:

B=

Zad. 7.2. Na ile sposobów można postawić 8 nie atakujących się wzajemnie wież na następującej szachownicy?

85

Funkcje tworzące

B=

Zad. 7.3. Na ile sposobów można postawić n nie atakujących się wzajemnie wież na następującej o wymiarach n × n szachownicy?          

Rozwiąż rekurencje:

|

{z

n razy

}

n razy

        

Zad. 7.4. (

To = 2, T1 = 5, Tn = 8Tn−1 − 15Tn−2 , n = 2, 3, 4, . . . .

Zad. 7.5. (

To = 0, T1 = 1, Tn = Tn−1 − Tn−2 , n = 2, 3, 4, . . . .

Zad. 7.6. (

To = 0, T1 = 1, T2 = 9, Tn = 2Tn−1 + Tn−2 − 2Tn−3 , n = 3, 4, 5, . . . .

Zad. 7.7. (

To = 0, Tn+1 − 2Tn = n2 + n + 2, n = 0, 1, 2, . . . .

86

Funkcje tworzące Zad. 7.8. (

To = 0, T1 = 1, Tn + 2Tn−1 − 3Tn−2 = 1, n = 2, 3, 4, . . . .

Rozwiąż rekurencje metodą funkcji potęgowych: Zad. 7.9.    gn = 0,

dla n < 0,

g = 2,

0   g = 2g n n−1 − gn−2 ,

Zad. 7.10.

(

g0 = 3, g1 = 8, gn = 4gn−1 − 4gn−2 ,

dla n > 0.

dla n > 1.

Zad. 7.11. (

g0 = 3, g1 = 3, g2 = 4, gn = 4gn−1 − 5gn−2 + 2gn−3 ,

dla n > 2.

Zad. 7.12. (

g0 = 0, g1 = 0, g2 = −1, gn − 6gn−1 + 12gn−2 − 8gn−3 = n,

dla n > 2.

Zad. 7.13. Znajdź związek pomiędzy funkcjami tworzącymi A(z) = [an , n ≥ 0] oraz B(z) = [bn , n ≥ 0] jeśli (a) an+1 = bn , n ≥ 0. (b) an = nbn , n ≥ 0. P (c) an ni=0 bi , n ≥ 0.

Zad. 7.14. Udowodnij, że jeśli funkcja tworząca A(z) = [an , n ≥ 0] jest postaci A(z) = 1+c1 z+cW2 z(z) 2 +...c z k dla pewnego wielomianu W (z) takiego, że k deg(W (z)) < k to dla dowolnego n ≥ 0 zachodzi an+k + c1 an+k−1 + c2 an+k−2 + . . . ck an = 0.

Zad. 7.15.⋆ Znajdź funkcję tworzącą ciągów spełniających poniższe warunki a następnie znajdź prostsze rekurencje:

87

Funkcje tworzące P

(a) an+1 = ni=0 ai + 1, ao = 1. P (b) an+1 = ni=0 2n−i ai + 1, ao = 1. P (c) an+1 = ni=0 Fn−i ai + 1, ao = 1, gdzie {Fn , n ≥ 0} oznacza ciąg Fibonacciego. Zad. 7.16. Rozwiąż rekurencję metodą funkcji tworzących: (

g0 = 0, g1 = 1, gn = −2gn−1 − gn−2 + 5n ,

dla n > 1.

Zad. 7.17. Rozwiąż rekurencję metodą funkcji tworzących (dla pewnego ustalonego niezerowego c):    gn = 0,

g0 = 2,   g = c2 g n n−2 ,

dla n < 0, dla n > 0.

Zad. 7.18. Dwadzieścia lat temu pewna osoba wpłaciła na konto oprocentowane kwartalnie 8% (zysk netto po odpisaniu podatku) pewną kwotę, żeby teraz wypłacić 75 569 zł. 31 gr. Jaką kwotę wpłaciła ta osoba? Zad. 7.19. Rozwiąż układ rekurencji:   

sn = 8sn−1 − 9tn−1 , tn = 6sn−1 − 7tn−1 ,   s = 4, to = 1. o Zad. 7.20. Liczby    L1

L

2   L n

= p, = q, = Ln−1 + Ln−2 , n ≥ 3,

nazywamy liczbami Lucasa. Rozwiąż tę rekurencję. Zad. 7.21. Czy liczby Lucasa zdefiniowane w zadaniu 7.20 dają się przedstawić w zależności od liczb Fibonacciego {Fn , n ≥ 1} a jeśli tak, to w jaki sposób? Zad. 7.22. Niech k będzie dodatnią liczbą naturalną i niech α1 , α2 , . . . αk , będą liczbami rzeczywistymi takimi, że αk 6= 0. Wykaż, że r jest pierwiastkiem równiania xk = α1 xk−1 + α2 xk−2 + . . . + αk ,

88

Funkcje tworzące wtedy i tylko wtedy, gdy r n jest jednym z rozwiązań równania rekurencyjmego sn = α1 sn−1 + α2 sn−2 + . . . + αk sn−k .

Zad. 7.23. Wykaż, że jeśli un i vn są dwoma rozwiązaniami równania rekurencyjnego: sn = α1 sn−1 + α2 sn−2 + . . . + αk sn−k , (zob. 7.22) to aun + bvn też jest rozwiązaniem tej rekurencji. Zad. 7.24. Wykaż, że jeśli un jest rozwiązaniem równania rekurencyjnego: sn = α1 sn−1 + α2 sn−2 + . . . + αk sn−k , a vn rozwiązaniem równiania rekurencyjnego sn = α1 sn−1 + α2 sn−2 + . . . + αk sn−k + f (n), to aun + bvn też jest rozwiązaniem ostatniej rekurencji. Zad. 7.25. Niech ar będzie liczbą rozwiązań równania p + q = r gdzie p i P r q są liczbami pierwszymi. Znajdź funkcję tworzącą A(z) = ∞ r=0 ar z .

Zad. 7.26. Niech ar będzie liczbą rozwiązań 2k + p = r, gdzie k jest liczbą P r naturalną a p jest liczbą pierwszą. Znajdź funkcję tworzącą A(z) = ∞ r=0 ar z , oraz znajdź najmniejsze r > 2 takie, że ar = 0. Zad. 7.27. Niech ar będzie liczbą rozwiązań a2 + b2 + c2 + d2 = r, gdzie P r a, b, c, d, są liczbami naturalnymi. Znajdź funkcję tworzącą A(z) = ∞ r=0 ar z . Zad. 7.28. Jakie (możliwie proste) równanie rekurencyjne spełnia ciąg sn = 2n + 2 · 3n + n − 7? Zad. 7.29. Jakie (możliwie proste) równanie rekurencyjne spełnia ciąg sn = (n + 1)! − 1? Zad. 7.30. Znajdź możliwie proste równanie rekurencyjne ciągu zdefiniowanego wzorem: √ √ an = (1 + 2)n + (1 − 2)n , n ≥ 0. √ Udowodnij, że dla wszystkich naturalnych n mamy |(1+ 2)n | ≡ n (mod 2). Zad. 7.31. Rozważmy funkcję

89

Funkcje tworzące Listing 7.1. Algorytm rekurencyjny fun tion begin if if

En ode ( n :

integer ,

i

:

index , a

:

array )

n = 0 then p r i n t 0; n = 1 then print a [ i ℄ else begin En ode ( n − 1 , 2 , a ) En ode ( n − 2 , 2 , a ) En ode ( n − 1 , 1 , a ) end ;

end .

Ile razy będzie wykonana instrukcja print po wywołaniu Encode(n, 1, a)? Zad. 7.32. Pokaż, że n X

∀n≥0

Fi2 = Fn Fn+1 .

i=0

gdzie {Fn , n ≥ 0} są liczbami Fibonacciego. Zad. 7.33. Pokaż, że ∀n≥0

n X i=0

Fi = Fn+2 − 1.

Zad. 7.34. Pokaż, że ∀n≥2

"

1 1 1 0

#n

=

"

Fn Fn−1 Fn−1 Fn−2 .

#

.

Zad. 7.35. Pokaż, że ∀n≥0 liczby Fn i Fn+1 są względnie pierwsze.

Rozdział 8 Wstęp do analizy algorytmów (15)

92

Wstęp do analizy algorytmów

1o Asymptotyka Definicja. f (n) = 0, g(n) f (n) ≍ g(n) ⇐⇒ ∃C>0 ∀n∈N |f (n)| ≤ C|g(n)| ∧ |g(n)| ≤ C|f (n)|, f (n) = 1, f (n) ∼ g(n) ⇐⇒ lim n→∞ g(n) f (n) = O(g(n)) ⇐⇒ ∃C ∀n∈N |f (n)| ≤ C|g(n)|, f (n) ≺ g(n) ⇐⇒

lim

n→∞

f (n) = o(g(n)) ⇐⇒ ∀ǫ>0 ∃no ∈N ∀n≥no |f (n)| ≤ ǫ|g(n)|

Rozważając różne nieskończone ciągi możemy wprowadzić pewien porządek między ciągami uwzględniający tylko graniczne zachowanie ciągów. Twierdzenie 8.1. Niech a ≥ 1, b > 1, będą stałymi oraz niech f (n) będzie nieujemną funkcją określoną dla potęg b. Jeśli zdefiniujmy T (n) dla kolejnych potęg b wzorem T (n) =

(

c, aT (n/b) + f (n),

to

jeśli n = 1, jeśli n = bi , i ∈ N ,

logb n−1

T (n) = h(n) +

X

j=0

aj f (

n ), bj

gdzie h(n) ≍ nlogb a . W szczególności: 1. Jeśli f (n) = O(nlogb a−ǫ ) dla pewnego ǫ > 0, to T (n) ≍ nlogb a . 2. Jeśli f (n) ∼ nlogb a , to T (n) ≍ nlogb a ln n. 3. Jeśli f (n) ≻ nlogb a+ǫ dla pewnego ǫ > 0 oraz jeśli af (n/b) ≤ Cf (n) dla pewnej stałej C < 1, to T (n) ≍ f (n). 2o Problem alokacji rekordów

Problem rozmieszczenia rekordów w pamięci komputera jest szczególnie istotny w teorii baz danych. Mamy kilka metod rozwiązujących to zagadnienie. Metoda sekwencyjna polega na kolejnym rozmieszczaniu rekordów w pamięci komputera, w indeksowo-sekwencyjnej utrzymywany jest zbiów indeksów (odsyłaczy) do bloków sekwencyjnie rozmieszczonych rekordów (rekordy w tm bloku muszą mieć co najmniej jedną cechę wspólną np. klucz główny może należeć tylko do określonego przedziału - ta cecha jest uwidoczniona w indeksie), a w metodzie indeksowej do każdego rekordu utrzymywany

93

Wstęp do analizy algorytmów jest indeks. Jeśli zbiory uporządkujemy według klucza to najpopularniejsze są dwie metody: zbiory uporządkowane przeszukiwane blokowo (dzielimy rekordy na bloki równej długości i najpierw wyszukujemy blok porównując szukany klucz z pierwszym kluczem bloku, a następnie przeszukujemy wszystkie rekordy w obrębie bloku) oraz zbiory uporządkowane przeszukiwane binarnie (za każdym razem zbiór wyszukiwawczy jest dzielony na pół i porównując szukany klucz z kluczem rekordu znajdującego się w ”połowie” decydujemy którą połówkę zbioru mamy przeszukiwać dalej). Osobną grupą metod organizacji zbiorów wyszukiwawczych są metody używające funkcje przekształcające klucz w adres komputerowy. Aby te metody były skuteczne, ważne jest, aby ”mało” rekordów otrzymywało ten sam adres, takie ”dobrze rozrzucające” funkcje nazywamy funkcjami mieszającymi a używające je metody - metodami ”hash table” (tablice mieszające). Efektywność tych algorytmów podsumujemy w tabelce. Organizacja Sekwencyjna Indeksowo-sekwencyjna Indeksowa Uporządkowane przesz. blokowe Uporządkowane przesz. binarnie Tablice mieszające a b c d

Wmin Wsr Wmax NW O(1) O(N ) O(N ) O(N ) O( Nk )a b O(1) O( Nk )ab O( Nk )a b O(1) O(1) O(1) O(1) O(1) O(k + Nk )a b O(k + Nk )a b O(k + Nk )a b O(1)

O(ln(N ))

O(ln(N ))

O(ln(N ))

O(1)

cd O( N m)

O(N )

N cd O( m )

k jest ilością bloków. √ Minimalnie O( N ) m jest wielkością tablicy mieszającej. Minimalnie O(1)

ZADANIA

Zad. 8.1. Jakie jest prawdopodobieństwo wypadnięcia na ruletce (Rys. 8.1): (a) liczby kończącej się cyfrą 3 (b) liczby mającej ciemne niebieskie tło (c) liczby leżącej na szarym tle lub mającej ostatnią cyfrę 5 ale nie 25 (d) Opiszemy zasady gry w ruletkę. Gdy w ruletce wypadnie liczba na szarym polu stracimy 1000 zł., gdy wypadnie liczba na ciemnym niebieskim polu lub kończąca się na 3 to zyskamy 5 zł. w pozostałych przypadkach

94

Wstęp do analizy algorytmów płacimy 4 zł. Obstawienie każdej gry kosztuje 60 zł. Ile wynosi wartość oczekiwana i odchylenie standardowe opisanej gry? Rysunek 8.1. Ruletka.

Zad. 8.2. Udowodnij, że dla dowolnych nieujemnych ciągów f (n), g(n), zachodzi O(f (n)) + O(g(n)) = O(f (n) + g(n)), f (n) = O(f (n)), cO(f (n) = O(f (n)), O(O(f (n))) = O(f (n)), O(f (n))O(g(n)) = O(f (n)g(n)), O(f (n)g(n)) = f (n)O(g(n)), a dla f (n) → 0, gdy n → ∞, ln(1 + O(f (n))) = O(f (n)), eO(f (n)) = 1 + O(f (n)).

Zad. 8.3. Udowodnij, że dla dowolnych naturalnych liczb n i m, nieujemnych wymiernych liczb ro < r1 < . . . < rn i so < s1 < . . . < sm oraz rzeczywistych liczb ao , a1 , . . . an , bo , b1 , . . . bm , an 6= 0, bm 6= 0 zachodzi an rn −sm an xrn + an−1 xrn−1 + · · · + ao xro x ∼ . s s s bm x m + bm−1 x m−1 + · · · + bo x o bm Zad. 8.4. Udowodnij, że (i) jeżeli f (x) = O(h(x)) i h(x) = O(k(x)) to f (x) = O(k(x)), (ii) jeżeli f (x) = O(h(x)) i h(x) = o(k(x)) to f (x) = o(k(x)),

95

Wstęp do analizy algorytmów (iii) jeżeli g(x) = o(f (x)) to f (x) = O(f (x) − g(x)), (iv) jeżeli f (x) = o(1) to f (x)g(x) = o(g(x)). Zad. 8.5. Wykaż, że (a) n−1 X j=0

(b)

k

j ∼

  

1 k+1 , k+1 n

ln(n),

  1,

n!en n

n+ 21

∼

√

dla k ≥ 0, dla k = −1, dla k ≤ −2,

2π,

(c) nk ∼ 1, k ∈ Z. nk Zad. 8.6. Udowodnij, że jeżeli f (x) = O(h(x)) i g(x) = O(k(x)) to f (x)+ g(x) = O(max{|h(x)|, |k(x)|}). Zad. 8.7. Niech T (1) = c, dla pewnej dodatniej stałej c oraz dla n ≥ 2 : (a) T (n) = 3T ( n2 ) + n log2 n, (b) T (n) = 5T ( n5 ) + logn n , 2 √ (c) T (n) = 4T ( n2 ) + n2 n, (d) T (n) = 2T ( n2 ) + n log2 n, (e) T (n) = T (n − 1) + n1 , (f ) T (n) = T (n − 1) + log2 n, √ (g) T (n) = T ( n) + 1, √ √ (h) T (n) = nT ( n) + n. Podaj asymptotyczne górne oraz dolne oszacowanie dla T (n) przy n → ∞. Zad. 8.8. Problem zatrudnienia sekretarki. Przypuśćmy, że chciałbyś zatrudnić w swojej firmie nową sekretarkę i chciałbyś, żeby to była bezwzględnie najlepsza osoba. Dlatego zwracasz się do biura pośrednictwa pracy, które codziennie przysyła Ci nową kandydatkę, a Ty jak stwierdzisz, że jest lepsza od dotychczasowej to dotychczasową bezwzględnie zwalniasz a nową zatrudniasz - dzięki temu, mimo wysokich kosztów masz pewność, że będzie to osoba najlepsza. Przyjmijmy, że przesłuchanie ma niski koszt (powiedzmy ci ) a zatrudnienie wysoki (zwolnienie i odprawa poprzedniej oraz zatrudnienie nowej ch ). Przyjmijmy, że mamy n kandydatek, a nasz algorytm można opisać następująco:

96

Wstęp do analizy algorytmów Listing 8.1. Algorytm wyboru sekretarki b e s t :=1; {best to numer najlepszej kandydatki} f o r i :=1 t o n begin Przesªu haj kandydatk numer i i f Kandydatka numer i jest lepsza ni» kandydatka numer best t h e n begin Zatrudnij kandydatk numer i i zwolnij kandydatk numer best b e s t := i ; end ; end ;

Jakie są koszty zatrudnienia sekretarki w przypadku najlepszym, przeciętnym i najgorszym? Zad. 8.9. Tak częste zatrudnianie i zwalnianie osób, jak w algorytmie 8.1 może się skończyć kłopotami z Urzędem Pracy, dlatego zmodyfikujmy naszą strategię następująco: Przesłuchujemy k kandydatek nie zatrudniając ich za to notując która uzyskała najlepszy wynik (powiedzmy best) i następnie zatrudniamy pierwszą spośród pozostałych n − k kandydatek, która osiągnie lepszy od best wynik. Wyznaczyć dla każdego k prawdopodobieństwo, że znaleziona w opisany powyżej sposób kandydatka będzie najlepsza i wyznaczyć takie k, dla którego to prawdopodobieństwo jest największe. Zad. 8.10. Dla każdego z podanych niżej algorytmów oblicz ilość operacji porównania, podstawienia, dodawania/odejmowania, mnożenia/dzielenia i potęgowania. Nie uwzględniaj kosztów obsługi pętli a w przypadku różnych wyników w zależności od danych podaj wartości najgorszą, przeciętną i najlepszą. Przyjmując czas wykonania każdej z tych operacji na 1 nanosekundę oszacuj czas wykonania tych algorytmów dla n = 1000 i n = 10000000. Listing 8.2. Algorytm 1 for

i :=3 t o n −1 a :=3 ·n+2· i − 1;

Listing 8.3. Algorytm 2 max:= a [ 1 ℄ ; f o r i :=2 t o n i f max=1 do begin i f n mod 2=1 t h e n w:=w+s ; s :=n d i v 2 ; s := s ∗ s end ; r e t u r n (w) ;

gdzie n mod k oznacza resztę z dzielenia n przez k (zob §3.4 [12]) n div k = ⌊ nk ⌋. Zad. 8.12. Jaki jest koszt (liczba obrotów pętli) następującego algorytmu znajdującego i-ty najmniejszy element ciągu: Listing 8.18. Algorytm znajdywania i-tego najmniejszego elementu fun tion

r a n d o m S e l e t (A: a r r a y

of

reals ,

i : integer , n: integer )

100

Wstęp do analizy algorytmów H, L : a r r a y ; i f n=1 t h e n return A[ 1 ℄ else begin p := random ( 1 , n ) ; nH : = 0 ; nL : = 0 ; f o r j :=1 t o n i f j p t h e n begin i f A [ j ℄>A[ p ℄ t h e n begin nH:=nH+1; H [ nH ℄ : =A [ j ℄ ; else begin nL:=nL+1; L [ nL ℄ : =A [ i ℄ ; end ; i f nH=0 t h e n b e g i n nH : = 1 ; H[ nH ℄ : =A [ p ℄ ; end ; i f i : v1 , v2 ∈ V, k ∈ N \{0}}, zbiór dwuelementowych podzbiorów zbioru V zwany zbiorem krawędzi grafu, trzecim elementem jest krotność krawędzi (dwa wierzchołki mogą być połączone jedną, dwoma, trzema,... krawędziami). Graf G nazywamy grafem bez krawędzi wielokrotnych jeśli w każdej trójce < {v1 , v2 }, k >∈ E(G) mamy k = 1. Piszemy wtedy w krótszej formie E(G) ∈ {{v1 , v2 }, v1 , v2 ∈ V (G)} po prostu pomijając ostatni element k = 1. Grafem skierowanym G nazywamy uporządkowaną parę (V, E) gdzie V pewien skończony (albo nieskończony) zbiór zwany zbiorem wierzchołków (węzłów) grafu i E ∈ V × V × (N \{0}), zbiór dwuelementowych uporządkowanych par zbioru V gdzie pierwszym elementem jest początek a drugim koniec krawędzi a trzecim elementem jest krotność krawędzi. Graf G nazywamy grafem bez krawędzi wielokrotnych jeśli w każdej trójce < v1 , v2 , k >∈ E(G) mamy k = 1. Piszemy wtedy krótko E(G) ∈ {{v1 , v2 }, v1 , v2 ∈ V (G)}. 1o Reprezentacje grafów

Macierz sąsiedztwa MG = [mi,j ]. Macierz ta jest rozmiaru V (G) × V (G) i mi,j oznacza liczbę krawędzi grafu G łaczących ˙ i-ty i j-ty wierzchołek. Pętle wierzchołka i zaznaczamy w elemencie mi,i . Jeżeli graf jest nieskierowany to macierz sąsiedztwa jest symetryczna. W przypadku grafu którego krawędzie mają wagi, gdy nie dopuszczamy krawędzi wielokrotnych w macierzy sąsiedztwa mogą wystąpić wagi krawędzi. Wielkość 2

pamięci tej struktury to O(V ). Lista incydencji LG Należy utworzyć listy dla każdego wierzchołka v, w której przechowujemy zbiór wierzchołków połączonych krawędzią z v. Dla grafu skierowanego podajemy listę tych wierzchołków które są końcem krawędzi gdy początkiem jest v. W przypadku grafów z wagami krawędzi lista poza wierzchołkiem powinna również zawierać wagę. Wielkość zajętej pamięci w tej metodzie to O(V + E). Lista krawędzi IG Jest to w zasadzie bezpośrednia reprezentacja E(G), lista na której bezpośrednio podajemy wszystkie krawędzie grafu. Koszt to O(E). Macierz incydencji Υ = [µi,j ] to tablica o rozmiarach V × E. Składa się ona z E kolumn i V wierszy, jeśli krawędź wychodzi z danego wierzchołka to piszemy w odpowiedniej kolumnie (−1), jeśli do niego wchodzi piszemy (+1), jeśli wierzchołek nie należy do krawędzi piszemy 0, jeśli jest to pętla

105

Grafy własna piszemy 2. Koszt tej reprezentacji to O(V · E).

µi,j

  0    −1 =  1   

2

jeśli jeśli jeśli jeśli

vi vi vi ej

nie jest punktem końcowym ej , jest punktem początkowym ej , nie jest punktem końcowym ej , jest pętlą wierzchołka vi .

Gdyby krawędzie miały swoje wagi, to można by je umieszczać zamiast liczb ±1 lub dorzucić jeszcze jedną kolumnę z wagami. 2o Grafy eulerowskie i hamiltonowskie Definicja 9.2. Jeśli dla każdych dwóch wierzchołków u, v ∈ V (G) istnieje droga łącząca u i v to taki graf nazywamy spójnym. Definicja 9.3. Rozspójnienie grafu oznacza usunięcie krawędzi lub wierzchołków lub i krawędzi i wierzchołków tak, aby powstał graf niespójny. Najmniejszą liczbę usuniętych wierzchołków powodujących rozspójnienie grafu nazywamy spójnością wierzchołkową grafu i oznaczamy κ(G). Najmniejszą liczbę usuniętych krawędzi powodujących rozspójnienie grafu nazywamy spójnością krawędziową grafu λ(G). Dla niektórych grafów usuwanie dowolnej ilości wierzchołków (krawędzi) nigdy nie rozspójni graf, wtedy spójność wierzchołkowa (krawędziowa) nie istnieje. Definicja 9.4. Mówimy, że graf G jest grafem Eulera (graf eulerowski) lub że ma cykl Eulera jeżeli istnieje cykl (droga która kończy się w tym samym węźle z którego zaczyna) przechodzący przez wszystkie krawędzie grafu (oczywiście przez każdą tylko jeden raz). Cykl Hamiltona to cykl przechodzący przez wszystkie wierzchołki grafu (czyli ścieżka zamknięta odwiedzająca każdy wierzchołek dokładnie raz). Graf hamiltonowski to graf posiadający cykl Hamiltona. Twierdzenie 9.1. Graf skończony i spójny nieskierowany jest eulerowski wtedy i tylko wtedy gdy stopień każdego wierzchołka jest parzysty. Graf skończony i spójny skierowany jest eulerowski wtedy i tylko wtedy gdy stopień krawędzi wchodzących każdego wierzchołka jest taki sam jak stopień krawędzi wychodzących. Twierdzenie 9.2. (Euler) X

u∈V (G)

degG (u) = 2E(G).

106

Grafy Definicja 9.5. Ciąg {d1 , d2 , ..., dn } nazywamy ciągiem graficznym jeżeli istnieje prosty graf o n wierzchołkach (bez pętli i krawędzi wielokrotnych) taki, że liczby {di , 1 ≤ i ≤ n} są stopniami wierzchołków tego grafu. Twierdzenie 9.3. (P. Erd¨ os, T. Gallai 1960) Nierosnący ciąg liczb naP turalnych {d1 , .., dn } jest ciągiem graficznym wtedy i tylko wtedy, gdy ni=1 di jest liczbą parzystą oraz dla k = 1, 2, ..., n, k X i=1

di ≤ k(k − 1) +

n X

i=k+1

min{k, di }.

Twierdzenie 9.4. (Dirac) Graf prosty G taki, że (i) V (G) = n ≥ 3 (ii) ∀v∈V (G) degG (v) ≥ n2 , jest grafem hamiltonowskim. Twierdzenie 9.5. (Ore) Graf prosty G taki, że (i) V (G) = n ≥ 3 (ii) ∀{u,v}6∈E(G) degG (u) + degG (v) ≥ n, jest grafem hamiltonowskim. 3o Izomorfizm grafów Definicja 9.6. Izomorfizm grafów. Niech G = (V (G), E(G)) oraz F = (V (F), E(F)) będą dwoma grafami. Jeżeli istnieje bijekcja (funkcja różnowartościowa i ”na”) f : V (G) −→ V (F), taka, że 







{f (u), f (v)} ∈ E(F) ⇐⇒ {u, v} ∈ E(G)

to powiemy że grafy te są izomorficzne: F∼ = G.

4o Kolorowanie grafów planarnych Definicja 9.7. Graf planarny jest to graf, który można narysować na płaszczyźnie bez przecięć. Twierdzenie 9.6. (Euler) Jeżeli w grafie planarnym n jest liczbą wierzchołków, e liczbą krawędzi, a f liczbą ścian (część płaszczyzny, wyznaczona przez krawędzie tego grafu nazywamy ścianami wewnętrznymi a nieograniczony obszar poza grafem to ściana zewnętrzna), to zachodzi równość n − e + f = 2.

107

Grafy Twierdzenie 9.7. (Appel, Haken, komputer). Do pokolorowania grafu planarnego wystarczą 4 kolory. 5o Kody Gray’a i ciąg de Bruijna Definicja 9.8. Kodem Gray’a długości n nazywamy takie uporządkowanie wszystkich 2n ciągów n cyfr binarnych, że kolejne ciągi różnią się dokładnie jedną cyfrą. To samo dotyczy pierwszego i ostatniego ciągu. Np n=7 0000000 0000001 0000101 0010101 0010100 0010000 1234567.

Definicja 9.9. Ciągiem de Bruijna rzędu n nazywamy takie ustawienie 2n cyfr 0 i 1 (powiedzmy c1 c2 , ..., c2n ), że każdy ciąg długości n występuje w w tym ustawieniu dokładnie raz, to znaczy ciągi: (c1 , .., cn ), (c2 , ..., cn+1 )... (c2n c1 , ..., cn−1 ) są różne.

0

0 1 0

1

0 0 1

1 1 1 1

0 0 1

0

Rysunek 9.1. Ciąg de Bruijna dla n = 4

Graf de Bruijna ma wierzchołki etykietowane ciągami długości 2n−1 . Ciąg de Bruijna jest konstruowany tak, że jeżeli mamy element np 0110 to następny elementem musi być 110∗ gdzie w miejsce ∗ powinniśmy wstawić 0 lub 1. Oczywiście w całym ciągu musi być i 1100 i 1101. Graf de Bruijna skonstruowany jest tak, połączone są ze sobą wierzchołki c0 c1 c2 i c1 c2 0 oraz c1 c2 1. Wtedy problem znalezienia ciągu de Bruijna można interpretować jako znalezienie cyklu Hamiltona w skierowanym grafie de Bruijna.

108

Grafy 0

001 ✗ 0

1✒

000

✖ ■ ❅0 ❅

✻❅0 ❅ ❘ ❅

1 ❅

1✲ 010 ✛ 0 101

✠

0

100 ✛

✲ 011 1✒ ❅1 ❅ ❘ ❅ ❅1 ■ ❅ ❅

0

111

❄✠

1✔ ✕

110

Rysunek 9.2. Graf de Brujina

6o Drzewa, minimalne drzewo spinające graf, algorytm Huffmana Drzewo to prosty graf acykliczny i spójny. Definicja 9.10. Niech G = (V (G), E(G)) będzie dowolnym spójnym grafem. Drzewem T = (V (T ), E(T )) spinającym graf G nazywamy takie drzewo, że V (T ) = V (G), E(T ) ⊆ E(G). Definicja 9.11. Niech będzie dany graf G = (V, E) a H ⊆ G niech będzie podgrafem grafu G. Funkcja f taka, że f : E(G) −→ R+ ∪ {0}, nazywamy wagą grafu G. Wagę całego podgrafu definiuje się, jako ω(H) =

X

f (e).

e∈E(H)

Problem 9.1. Jak dla dowolnego grafu G z wagą f znaleźć drzewo T spinające ten graf o minimalnej wadze ω(T ). Algorytm 9.8. Algorytm Kruskala znajdywania minimalnego drzewo spinające graf Dane: Niech G będzie skończonym grafem spójnym z wagami, którego krawędzie uporządkowane są: e1 < e2 < e3 < ... < em tak, że f (e1 ) ≤ f (e2 ) ≤ f (e3 ) ≤ ... ≤ f (em ). Wynik: Zbiór E krawędzi minimalnego drzewa spinającego graf G. E:=∅

109

Grafy for j:=1 to m do if E ∪ {ej } jest acykliczny then E:=E∪{ej };

Algorytm 9.9. Algorytm Prima znajdywania minimalnego drzewo spinające graf Dane: Niech G będzie skończonym grafem spójnym z wagami (krawędzie niekoniecznie uporządkowane) Wynik: Zbiór E krawędzi minimalnego drzewa spinającego graf G. E:=∅ V:={v} {wybierz wierzcholek w ∈ V (G)} while V 6= V (G) do begin Wybierz krawędź {u, v} ze zbioru E(G) o najmniejszej wadze tak, że u ∈ V, v ∈ V (G) − V ; {Dopisz {u, v} do E} E:=E∪{{u, v}}; V:=V∪{v}; end; Definicja 9.12. Skierowane drzewo nazywamy drzewem z wagami jeżeli jest określona funkcja f przyporządkowująca liściom drzewa liczby rzeczywiste. Poziomem drzewa nazywamy długość drogi (liczba krawędzi) l jakie prowadzą od rdzenia drzewa do węzła. Wagą drzewa nazywamy wielkość v∈E(T ),v

X

f (v)l(v).

jest liściem

Definicja 9.13. Drzewo skierowane T nazywamy drzewem binanarnym jeśli dla każdego węzła v jest outdegT (v) = 2 lub outdegT (v) = 0 (wtedy v jest liściem). Algorytm Huffmana konstruuje dla zadanego ciągu liczb optymalne drzewo binarne to znaczy drzewo binarne o najmniejszej możliwej wadze. Algorytm 9.10. HUFFMAN(L) Dane: Ciąg L = {ω1 , ω2 , ..., ωt } Wynik: Optymalne drzewo binarne T (L) dla ciągu L Jeżeli t=2 to niech T (L) będzie drzewem z dwoma liśćmi ω1 i ω2 w przeciwnym razie 1. Znajdź dwa najmniejsze wyrazy w ciągu L powiedzmy u i v 2. Niech L′ będzie listą powstałą z L przez usunięcie u i v i wstawienie u + v. 3. Wykonaj algorytm HUFFMAN(L’) by otrzymać drzewo T (L′ ) 4. utwórz drzewo T (L) z drzewa T (L′ ) zastępując liść wagi u + v w drzewie T (L′ ) poddrzewem mającym dwa liście o wagach u i v

110

Grafy

ZADANIA

Zad. 9.1. Spośród następujących reprezentacji grafów: (i) Lista krawędzi E(G), (ii) Rysunek (iii) Macierz sąsiedztwa (iv) Lista incydencji (v) Macierz incydencji dla każdego grafu (niektóre są skierowane, niektóre nieskierowane) podaj pozostałe: (a) E(G) = {{1, 2}, {2, 3}, {1, 4}, {2, 5}, {4, 5}, {4, 6}, {5, 6}, {5, 7}},

3

(b)

1

q ✲ q4 ❄ ❄❄ 5 q2✲ q ✐ ✒ ✻ q✒

G

LG 1 : 2, 5, 6; 2 : 1, 2; (d) 3 : 4, 6; 4 : 3; 5 : 1; 6 : 1, 3;

7



     (c) MG =      

q

✻✻ 6

q



      (e) ΥG =       

0 1 2 0 1 1 0

3 1 0 1 0 0 0

1 0 0 1 2 0 0

0 0 1 0 0 1 0

0 1 0 0 0 0 1

2 0 0 0 1 0 0

1 2 3 4 5 E 1 − 3 −1 0 1 0 0 0 0 0 0 0 0 1−1 2 1−4 1 0 0 −1 0 0 2 − 3 0 −2 2 0 0 0 2−4 0 1 0 −1 0 0 0 0 2 0 0 4−4 0 0 0 0 2 −2 4−5 0

0 0 0 1 0 0 0

           



      .      

Zad. 9.2. (Lemat o uściskach dłoni) W każdej chwili liczba osób we Wszechświecie, które w swym życiu uścisnęły nieparzystą liczbę dłoni jest parzysta.

111

Grafy Zad. 9.3. Rozwiąż problem Eulera (istnienia drogi i cyklu przechodzącej przez wszystkie mosty ale tylko raz) w innych, niż Królewiec, miastach: Rysunek 9.3. Problem Eulera w Rzymie, Paryżu i Zahlenbergu.

Zad. 9.4. Czy można narysować kopertę nie odrywając ołówka od papieru i nie rysując dwa razy po tej samej linii? Zad. 9.5. Czy można narysować linię ciągłą, która przetnie każdy z odcinków poniższej figury dokładnie raz? Czy ta linia może być zamknięta? Zadanie rozwiąż dla każdej podanej figury.

❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅

Figura F1

Figura F2

Figura F3

❅ ❅

Figura F4

112

Grafy Zad. 9.6. Który z poniższych grafów ma drogę (cykl) Hamiltona i jaką? Rysunek 9.4. Grafy hamiltonowskie.

Zad. 9.7. Czy te grafy są izomorficzne? Gq

✑◗ ◗ E Aq✑✑ βq τq ◗q ❅ ❅ ❅ αq ❅Cq Dq ❅δq ❅qǫ ❅ ❅ Bq ηq ❅qψ q ❅F

G1

g ✘✘q ✘ ✘✘✘ e ✂ a q ✂ q ✘ ✘ ❅ ✂ dq ❅cq ✂ ❅ ✂ bq f ❅q✂ G3

G2

Zad. 9.8. Czy następujące grafy są izomorficzne:

(a) q ✂❇

q q✂

✂

(c)

(b)

✂ ✂

✂ ❇

❇ ❇

❇

q ❇q

q ✚❩ ✚ ❩ ✚ ❩ q✚ ❩q ❆ ✁ ❆ ✁ ❆ ✁ ❆q ✁q

q

q

q

q

q q ✡❏ ✡ ❏ ✡ ❏q q ❅ ❅ ❅ ❅q q ✡ ❏ ❏ ✡ q ❏✡

q

q q q ❍ ❅❍ ❅ ✟✟ ❅❍❍✟✟ ❅ ✟✟❍❍❅ ❅ ❍❍ ❅q q✟✟ ❅q q ✡ ✟✟ q ✟ ✡ ✟ q ❍ ❏ ❍✡ ✟✟ ❏✡❍❍✟✟ ✡❏✟✟❍❍ ❍❍q q✡ ✟✟❏ ✟✟ ❏ ✟ ❏q✟

Zad. 9.9. Czy następujące grafy są izomorficzne:

113

Grafy (a)

(b)

q ❅ ❅q

q ❅ ❅q

q

q ❅ ❅ ❅ ❅q q

q ❅ ❅q

q ❅ ❅q

q

(c)

q

q

q

q

q

q

q

q q

q ✟✟❩ ❩ ✟ q ✟ ❩ ❅ ❩q ✚ q ❅ ❍❍❅ ✚ ✚ ❍❍✚ ❅q

q ❅ ❅ ❅ ❅q q

q q

Zad. 9.10. Narysuj wszystkie nieizomorficzne grafy: (a) mające 3 wierzchołki (b) mające 4 wierzchołki? Zad. 9.11. Czy te grafy są izomorficzne? Jeśli tak to jak przekształcić pierwszy aby uzyskać drugi? Rysunek 9.5. Izomorfizm grafów.

Zad. 9.12. Narysuj wszystkie nieizomorficzne spójne grafy proste (bez pętli i krawędzi wielokrotnych) mające 5 wierzchołków o stopniach 1, 2, 2, 2 i 3. Zad. 9.13. Narysuj wszystkie nieizomorficzne spójne grafy proste mające 6 wierzchołków o stopniach 1, 1, 1, 2, 2 i 3. Zad. 9.14. Narysuj graf którego wierzchołki są etykietowane dwuelementowymi podzbiorami zbioru {1, 2, 3, 4} a dwa wierzchołki (A1 i A2 , powiedzmy) są połączone krawędzią gdy A1 ∩ A2 6= ∅. Zad. 9.15. Który z podanych niżej ciągów jest ciągiem graficznym:

114

Grafy (a) (b) (c) (d) (e)

{11, 7, 7, 7, 5, 4, 3, 1}, {5, 5, 4, 2, 1, 1}, {4, 4, 3, 3, 2, 1, 1}, {7, 6, 5, 4, 3, 2, 1}, {8, 8, 8, 8, 8, 8, 8, 8, 4, 4, 4, 4, 2, 2}.

Zad. 9.16. Jak pokolorować mapę Ameryki Południowej i ile kolorów wystarczy, aby żadne dwa sąsiadujące państwa nie miały tego samego koloru? Rysunek 9.6. Kolorowanie grafów planarnych.

Zad. 9.17. Izomery są to związki chemiczne nie różniące się ilością pierwiastków, ale budową. Na przykład są trzy izomery C5 H12 można przedstawić grafami: Rysunek 9.7. Izomery C5 H12 .

115

Grafy

Ile jest różnych izomerów C6 H14 ? Zad. 9.18. Znajdź wszystkie kody Gray’a które na 3 pozycji mają 011 na 5 pozycji 101 a na 8 pozycji 010. Zad. 9.19. Jaka jest odległość (ile węzłów dzieli) 011011 i 110110 w Q6 ? Zad. 9.20. Skonstruuj kody Gray’a długości 2 dla alfabetu {0, 1, 2}. Zad. 9.21. Co należy wstawić w miejsce gwiazdek w ciągu de Bruijna: 110 ∗ 00100 ∗ 101011? Czy istnieje uogólnienie ciągu de Bruijna dla alfabetu trzyznakowego {0, 1, 2} i n = 2? Zad. 9.22. Odległości miejscowości w milach podane są na rysunku: Rysunek 9.8. Tabela odległości.

Towarzystwo naftowe chce połączyć te miasta rurociągami przechodzącymi bezpośrednio pomiędzy tymi miastami. Ile co najmniej mil rur do tego potrzeba? Zad. 9.23. Znajdź T (L) dla L = {3.2; 4.1; 1.8; 1.1; 2.5; 1.1; 7.6; 5.5; 4.1; 3.3; 7.1; 8.1; 4.0; 2.5; 6.2; 7.7} Zad. 9.24.⋆ (Kody Gaussa) Rozważmy krzywą zamkniętą na płaszczyźnie o skończonej liczbie punktów samoprzecięcia, przy czym załóżmy, że krzywa przechodzi przez każdy z nich dokładnie dwa razy. Oznaczając te punkty symbolami A, B, C, ... i obiegając krzywą w jednym z dwóch możliwych kierunków otrzymamy pewien ciąg (kod), w którym każdy symbol występuje dokładnie dwa razy. Pokaż, że liczba symboli pojawiających się dokładnie jeden raz pomiędzy dwoma wystąpieniami tego samego symbolu w kodzie Gaussa jest zawsze parzysta.

116

Grafy

F ✗ G✎

✎

E

C

❄ ✾ D ✣B

❘

✻

A ✲

Cykl Gaussa ABCDBEF GEADCGF

Zad. 9.25. Rozważmy następujący problem: Mamy wykonać pewne zadanie reklamowe złożone z 11 elementów:

Kod zadania A B C D E F G H I J K

Nazwa zadania Wybór elementów (manager) Wybór elementów (kupujący) Wybór i oszacowanie kosztów reklamy Przygotowanie obrazu Przygotowanie kopii Projekt reklamy Lista odbiorców reklam Wydruk adresów odbiorców Wydruk reklamy Zaadresowanie reklam Dostarczenie reklamy

Czas wykonania zadania 3 2 2 4 3 2 3 1 5 2 10

Zadanie można wykonać gdy ukończone jest Nic Nic A,B C C D,E C G F H,I J

Wyznacz najmniejszą liczbę dni potrzebną do wykonania tego zadania. Zad. 9.26. Wyznacz najkrótszy całkowity czas wykonania projektów: (a) B ❤✲ E ❤ 4 5

✯ ✂✍ ❅ ❅ ❅ ❅ ✂ C A❤ ❘ H ❅ ❘ F ❅ 7 ✲ 5❤✲ 3❤✲ 9❤ ✒ ❇ G❤ D❇◆ ❤✲ 5 6

(b)

A❥ D❥ ✲H0.8❥ ✲K4.5❥ 7.1 ✲4.3

(c)

✸

❇ E❇◆❥

✲I 1.2❥ ✣ ✂✍ ✡✡ ✂ ✲F ❥ ✡ L ❥ B❥ 5.3 6.1 3.0 ❏ ✡ ✣ ✂✍ ✡ ❏❏ ✂ ❫ ✡ ✲2.6❥ ✲2.0❥ ❥ 4.9

B ❤✲ E ❤✲ G ❤✲ H❤ 8 8 3 5

3.3

C

G

J

✒ A❤ 13

❅ D❅ ❘❤ ❅ 9

✂✍

✂✍

✂ ✂✲ F ❤ ✲C18❤ 1 ✸

❄ I ❤ ✲ 5

117

Grafy (d) C❤ 7

(e) H❤ 5

F A ❤✒ ❅ ❘ ❤✒ ❅ 3 2 I D ❅ ❘ ❤✒ ❅ ❅ ❘ ❤ ❅ 5 5 G ✒ B ❤✒ ❅ ❘ 4❤ ❅ 4 E ✒ ❅J ❅ ❘ ❤ ❅ ❘ ❤ ❅ 3 4

A ❤✲ C ❤✲ E ❤✲ G 1 ✑ 4 ✶6❤ ✸3

B

✑ ✑ ✲ ❤ 2 4❤✲ 4❤✲ 6❤ D

F

H

Zad. 9.27. Wyznacz najkrótszy całkowity czas wykonania Zadania Zadanie Czas poprzedzające Zadanie Czas A 11 Nic A 0.05 B 13 Nic B 0.09 C 12 Nic C 0.10 D 14 Nic (a) (b) D 0.07 E 8 A,C,D E 0.02 F 6 A,B,D F 0.04 G 10 A,B,C G 0.11 H 5 B,C,D H 0.09 I 9 E,F,H I 0.06 J 7 F,G,H Zadania Zadanie Czas poprzedzające Zadanie Czas A 6 Nic A 3 B 9 A,D B 5 C 10 B,I C 2 (c) D (d) D 8 Nic 4 E 9 B E 6 F 13 I F 6 G 5 C,E,F G 3 H 9 Nic H 3 I 6 D,H I 2

projektów: Zadania poprzedzające Nic A A,F B,C Nic E E F,G D,H Zadania poprzedzające Nic Nic A A,B A,B C,D,E D,E F,G F,G

Rozdział 10 Zadania przekrojowe (18)

120

Zadania przekrojowe

ZADANIA Zad. 10.1.⋆ Która z podanych liczb jest mniejsza: (a)

99 X

(k3 + 2k −

k−5 ) (k + 1)(k + 2)(k + 3)

!

!

k=0

czy !

100 100 100 (b) 6 +6 +3 + 1 + H100 − ϕ(8) P2 J2 (65) − 1

2

100
? 2

Zad. 10.2.⋆ Oblicz  LCG(19, 5, 2, 7, 4) − pJ (34) − J (17) + J (12) J3917 (192764) 9 9 5

2 · (Spec12 (37.2) mod 7)

.

Zad. 10.3.⋆ Sprawdź prawdziwość kongruencji : N W W ([3,5,0,1,...],[1,2,1,2,...]) [4,...] ) mod [2,4,...]·3·72 P √ 3 1/3 −k 4 7 7 P14 11L10 k∈Z ( k ) ) P L7 P5 L12 P7 + 3φ(75)P8 L5 P12 L7

(a)

(φ(450) − J2 (129))16 ≡ (L3 P2 ·

(b)

(N W W ([2, 1, . . .], [4, . . .]) + ≡ 1 mod Spec26 ( 72 ),

(c) (d) (e)

13,




P

2k 2/3−2k + Spec ( 5 ))φ(4)+1 , (J2 (66) + k∈Z 1/3 10 9 k 5 10 ≡ (LP3 L7 P L12 P5 + L4 P7 LP12 L5 )[3,7,12,5,33,45,1,...] mod 7,

39N W D([5,0,2,5,0,3...],[2,5,0,0,2,...]) 5 ≡ 16(mod(8φ(12)L32 P17 L65 P43 L5 P9 · P32 L17 P65 L43 P5 L9 + Spec6 ( J2 (67) )),

(16 + Spec10 ( 59 ))φ(4)+1 ≡ (L13 P27 L15 P61 L32 P11 · P13 L27 P15 L61 P32 L11 )φ(3327510) (mod7).

Zad. 10.4. Znajdź proste równanie rekurencyjne, które spełnia ciąg: gn = (5n−1)(

X

k∈Z

!

!

!

n X −1/2 1/2−k X −1/2 1/2−k 2n n 2 + 2 ) +(3n+1) . k k − 1 k k∈Z k=0

121

Zadania przekrojowe Zad. 10.5.⋆ Udowodnij, że dla ciągu Fibonacciego {Fn , n ≥ 0} zachodzi: |

N W D(Fm , Fn ),

N W D(Fn , Fn+1 )

=

1,

Fm Fn−m+1 + Fm−1 Fn−m

=

Fn2

=

Fn .n ≥ m ≥ 1,

Fn+1 n→∞ Fn

=

FN W D(m,n)

m|n =⇒ Fm |Fn ,

Fn+1 Fn−1 − lim

(−1)n , n ≥ 1, √ 1+ 5 . 2

Zad. 10.6. Ciąg Fibonacciego można zdefiniować również dla liczb całkowitych ujemnych korzystając ze wzoru Fn−2 = Fn − Fn−1 , 1 ≥ n. Jaki jest wzór na ciąg Fibonacciego dla wszystkich liczb całkowitych? Zad. 10.7.⋆ Wykaż, że n X

k

(−1)

k=1

!2

n k

=

(

n

(−1) 2

n
n 2

, n parzyste, 0, n nieparzyste.

Zad. 10.8. Na ile sposobów można pokonać n stopni, jeżeli możemy poruszać się o 1 bądź 2 stopnie do góry? Wyprowadź rekurencję i ją rozwiąż. Zad. 10.9. Niech pn oznacza liczbę możliwych pokryć prostokąta o wymiarach n × 2 kostkami domina o wymiarach 2 × 1. Na przykład, jak wynika z rysunku poniżej p2 = 2, p3 = 3 :

p2 = 2

p3 = 3

Rysunek 10.1. Pokrycia prostokąta n × 2 kostkami domina

Wyprowadź rekurencję na pn , n ≥ 2, i ją rozwiąż. Zad. 10.10. Mamy flagę złożoną z n poziomych pasów. Każde dwa sąsiadujące pasy są różnych kolorów, a do dyspozycji mamy tylko 3 kolory. Ile jest takich flag gdzie pasy najwyższy i najniższy są różnych koloru? Zad. 10.11.⋆ Oblicz dn - liczbę permutacji π ciągu n-elementowego {1, 2, 3, 4, 5, . . . n}, takich, że π(i) 6= i, 1 ≤ i ≤ n.

122

Zadania przekrojowe Zad. 10.12.⋆ Oblicz dn (k) - liczbę permutacji π ciągu n-elementowego {1, 2, 3, 4, 5, . . . n}, takich, że card{i ∈ {1, 2, 3, . . . n} : π(i) = i} = k, (czyli że dokładnie k spośród liczb 1, 2, 3, . . . n, jest na swoim miejscu. Zad. 10.13. Rozważmy graf skierowany G

✛ ✲

v1r ❄

✒

✓✏ r

v4

✲ ✒✑

✲

r

v2

✻ ❄ r

v3

Podaj macierz sąsiedztwa dla tego grafu. Na ile sposobów można dotrzeć z wierzchołka v1 do v2 przejeżdżając przez trzy krawędzie? Zad. 10.14. MH jest macierzą sąsiedztwa pewnego grafu H: 



1 1 2   MH =  0 0 1  1 2 0

Czy graf ten jest skierowany, czy posiada pętle a krawędzie wielokrotne? Narysuj graf H. Podaj stopnie wierzchołków, określ spójność wierzchołkową i krawędziową. Zad. 10.15. Dla grafu nieskierowanego F v5 r e4 v4

r

e2 e3 e5 e8

e1 ✓✏ vr 1 ✒✑ e6

vr2

r e7

v3

podaj macierz sąsiedztwa, incydencji i listę incydencji i krawędzi. Wyznacz ciąg stopni wierzchołków, spójność krawędziową i wierzchołkową. Czy ten graf ma drogę/cykl Eulera/Hamiltona? Zad. 10.16.⋆ Sprawdź, czy te grafy mają cykl (drogę) Hamiltona, cykl (drogę) Eulera, znajdź minimalne drzewo spinające graf, wagę tego drzewa, oraz ich spójność wierzchołkową i krawędziową (odp. uzasadnij)

123

Zadania przekrojowe

q 4 q ❅3 ✁ ❅ 6✁ 2 4 ❅q 5 ✁ 1 ❅ ✁ ❅✁q 7 q 6 q 2 1 ❆ ❅1 ❆ ❅❅q 5 ❆ 3 4❆ G2 q 4 ❆q 2

3 q 2 q 4 q ❅ ❅ 4 1 2 7 ❅ ❅ 2 5 1 q q ❅q ❅q ❅ 1 4 3❅ 2 q ❅q

G1

2 q q ❅ ✁ ❆ 4 ✁ ❆❅8 ❆3❅q 5 ✁ ❆ ✁❆ ✁ 5 6 ❆✁ 1✁❆ ✁ ❆ q ✁ ❆ 2 9 ✁ ❅ ❆ ✁ 6 3❅❆ 7 ❅❆q q✁

q 3

5 1

q

G4

4

q 2 q ❅3 5 4 ❅ 1 ❅ q ❅q 6

G5

4

q 5 q 1 q

q

3 7 8

q

q 4 q 2 ✟❍ ✟ 3 ❍q 1 ✁❅2 1 ❆ 2 ✁q 2 ❅q 4 ❆q ❆ ❅ ✁ 3 4 4 5 1 q q ❆❍ ✁ ❅ ✟ q 5 6 ❍✟

G3

q 5 ❍❍q ❍❍ 5 5 q 6 3 ❍❍ ✟✟ ❅3 3 1❅q✟✟ 4 2 P q✟✟ PPP 5

G6

q q 1 q ❅5 2 ❅4 3 ❅ ❅ ❅q ❅q 3 4 1 ❅3 1 2 ❅ ❅❛ 5 q q

G7

Zad. 10.17.⋆ Znajdź T (L) gdzie L = {J2 (52), 17 · L2 P7 , φ(120), 7, N W D([1, 3, 1, 4, . . .], [0, 2, 0, 1, . . .]), Spec11 (3 51 ), 32, 26 mod 17, φ(75)} Zad. 10.18. Dla jakich n można w poniższym grafie znaleźć drogę (cykl)

124

Zadania przekrojowe Eulera i Hamiltona? Narysuj te drogi (cykle). Ile wynosi spójność tego grafu? Rysunek 10.2. Grafy hamiltonowskie.

Rozwiązania

Rozdział 1. Indukcja 1.1. 0 · (3 · 0 + 1) = 0 = 0 · 12 ,

S(0) : S(k) ⇒ S(k + 1) :

1 · 4 + 2 · 7 + 3 · 10 + . . . + k(3k + 1) + (k + 1)(3k + 4)

k(k + 1)2 + (k + 1)(3k + 4) = (k + 1)(k 2 + k + 3k + 4)

=

(k + 1)(k + 2)2 .

= 1.2.

3 1+2 1 = = , (1 + 1)2 4 2·1+2 1 1 1 1 ) (1 − )(1 − )(1 − ) . . . · (1 − 4 9 16 (k + 2)2 1 (k + 2)(k + 3)(k + 1) k+2 · (1 − )= 2 2k + 2 (k + 2) 2(k + 1)(k + 2)2 k+3 . 2(k + 2)

1−

S(1) : S(k) ⇒ S(k + 1) : = = 1.3.

1 · 1! = 1 = (1 + 1)! − 1,

S(1) : S(k) ⇒ S(k + 1) :

=

1 · 1! + 2 · 2! + 3 · 3! + . . . + (k + 1) · (k + 1)!

(k + 1)! − 1 + (k + 1) · (k + 1)! = (k + 2)! − 1.

1.4. S(1) : S(k) ⇒ S(k + 1) :

1 0 =0=1− , 1! 1! 1 2 k 1 k 0 + + + ... + =1− + 1! 2! 3! (k + 1)! k! (k + 1)!

126

Rozwiązania =

1−

k+1 k 1 + =1− . (k + 1)! (k + 1)! (k + 1)!

1.5. S(1) : S(k) ⇒ S(k + 1) : = = = =

1 1·2 12 = = , 1·3 3 2·3 22 32 (k + 1)2 12 + + + ... + 1·3 3·5 5·7 (2k + 1) · (2k + 3) 2 k(k + 1) (k + 1) + 2(2k + 1) (2k + 1) · (2k + 3) k(2k + 3) + 2(k + 1) (k + 1) 2(2k + 1)(2k + 3) (k + 1)(2k + 1)(k + 2)) 2(2k + 1)(2k + 3) (k + 1)(k + 2) . 2(2k + 3)

1.6. S(1) : S(k) ⇒ S(k + 1) : = =

1 1·2 1 = = , 1·3·5 15 2·3·5 1 2 3 k+1 + + + ... + 1·3·5 3·5·7 5·7·9 (2k + 1)(2k + 3)(2k + 5) k(k + 1) k+1 + 2(2k + 1)(2k + 3) (2k + 1)(2k + 3)(2k + 5) (k + 1)(k + 2) k(k + 1)(2k + 5) + 2(k + 1) = . 2(2k + 1)(2k + 3)(2k + 5) 2(2k + 3)(2k + 5)

1.7. S(1) : S(k) ⇒ S(k + 1) : = = =

1 1 1 1 1 = = ( − ), 1·2·3 6 2 2 6 1 1 1 + + ... + 1·2·3 3·4·5 (k + 1)(k + 2)(k + 3)   1 1 1 1 − + 2 2 (k + 1)(k + 2) (k + 1)(k + 2)(k + 3)  11 (k + 3) − 2 − 2 2 (k + 1)(k + 2)(k + 3)  1 11 − . 2 2 (k + 2)(k + 3)

127

Rozwiązania

1.8. 1·2·3·4 , 4 1 · 2 · 3 + 2 · 3 · 4 + 3 · 4 · 5 + . . . + (k + 1)(k + 2)(k + 3) k(k + 1)(k + 2)(k + 3) + (k + 1)(k + 2)(k + 3) 4 (k + 1)(k + 2)(k + 3)(k + 4) . 4 1·2·3 =6=

S(1) : S(k) ⇒ S(k + 1) : = = 1.9.

1 1 = , 2 2 1 1 1 1 (1 − )(1 − )(1 − ) . . . (1 − ) 2 3 4 k+2 1 (k + 1) 1 1 (1 − )= = . k+1 k+2 (k + 1)(k + 2) k+2 1−

S(1) : S(k) ⇒ S(k + 1) : = 1.10.

1·2·3·4 , 12 2 · 12 + 3 · 22 + 4 · 32 + . . . + (k + 2)(k + 1)2 k(k + 1)(k + 2)(3k + 1) + (k + 2)(k + 1)2 12 (k + 1)(k + 2)(3k2 + k + 12k + 12) 12 (k + 1)(k + 2)(k + 3)(3k + 4) . 12 2 · 12 = 2 =

S(1) : S(k) ⇒ S(k + 1) : = = = 1.11. S(1) : S(k) ⇒ S(k + 1) :

= = =

1 11 1  1 = = − , 1·2·3·4 24 3 6 2·3·4 1 1 1 + + + ... 1·2·3·4 2·3·4·5 3·4·5·6 1 + (k + 1)(k + 2)(k + 3)(k + 4)  1 1 11 − + 3 6 (k + 1)(k + 2)(k + 3) (k + 1)(k + 2)(k + 3)(k + 4)  11 k+4−3 − 3 6 (k + 1)(k + 2)(k + 3)(k + 4)  1 11 − . 3 6 (k + 2)(k + 3)(k + 4)

128

Rozwiązania

1.12. S(1) :

5(100 − 9 − 10) , 81 5 + 55 + 555 + . . . + 555 . . . 5} | {z 5=

S(k) ⇒ S(k + 1) :

k+1 razy

=

5(10k+1

− 9k − 10) + |555{z . . . 5} 81 k+1 razy

k+1 razy

=

= = =

5(10k+1

z

}|

{

− 9k − 10) 111 . . . 1 ·81 +5· 81 81

5(10k+1

k razy

z }| {

− 9k − 10) 8 99 . . . 9 1 +5· 81 81 10k+2 − 1 − 10k+1 − 8 5(10k+1 − 9k − 10) +5· 81 81 5(10k+2 − 9(k + 1) − 10) . 81

1.13. (1 + 1) = 2 = 21 · 1,

S(1) : S(k) ⇒ S(k + 1) : = = =

(k + 2)(k + 3)(k + 4) · . . . · (k + 1 + k + 1) (2k + 1) · (2k + 2) (k + 1)(k + 2)(k + 3) · . . . · (k + k) (k + 1) 2k · 1 · 3 · 5 · . . . · (2k − 1) · 2 · (2k + 1) 2k+1 · 1 · 3 · 5 · . . . · (2k + 1).

1.14. 1 1 = , 2 2 1 1 1 1 1 1 − + − + ... + − 2 3 4 2k + 1 2k + 2 1 1 1 1 + ... + + − k+1 2k 2k + 1 2k + 2 1 1 1 1 + ... + + −2 k+2 2k + 2 k + 1 2k + 2 1 1 + ... + . k+2 2k + 2 1−

S(1) : S(k) ⇒ S(k + 1) : = = =

129

Rozwiązania

1.15. S(1) :

x=

S(k) ⇒ S(k + 1) : = =

=

x − 2x2 + x3 , (1 − x)2

x + 2x2 + 3x3 + . . . + (k + 1)xk+1 x − (k + 1)xk+1 + kxk+2 + (k + 1)xk+1 (1 − x)2 x − (k + 1)xk+1 + kxk+2 + (k + 1)xk+1 − 2(k + 1)xk+2 (1 − x)2 (k + 1)xk+3 + (1 − x)2 x − (k + 2)xk+2 + (k + 1)xk+3 . (1 − x)2

1.16. S(1) : S(k) ⇒ S(k + 1) : = = =

(a − 1)(2 − 1) a+1 = + 1, 2 2 a+1 a+3 a+7 a + 2k+1 − 1 + + + ... + 2 4 8 2k+1 k+1 k a+2 −1 (a − 1)(2 − 1) +k+ k k+1 2 2 (a − 1)(2k+1 − 2) + k2k+1 + a + 2k+1 − 1 2k+1 (a − 1)(2k+1 − 1) + (k + 1). 2k+1

1.17. S(0) : S(k) ⇒ S(k + 1) : = = =

x−1 1 2 1 = 2 = + , x+1 x −1 x − 1 1 − x2 1 2 4 2k+1 + 2 + 4 + . . . + 2k+1 x+1 x +1 x +1 x +1 k+1 k+1 1 2 2 + k+1 + k+1 2 2 x−1 1−x x +1 k+1 k+1 k+1 2 )2 + 2k+1 (1 − x2 ) (1 + x 1 + x−1 1 − x2k+2 1 2k+2 . + x − 1 1 − x2k+2

130

Rozwiązania

1.18. x 1 x(1 − x) = · 2 1−x 1 − x 1 − x2 k x2 x4 x2 x + + + ... + , 1 − x2 1 − x4 1 − x8 1 − x2k+1 k k 1 x − x2 x2 · + 1 − x 1 − x2k 1 − x2k+1 k k k (1 + x2 )(x − x2 ) + (1 − x)x2 (1 − x)(1 − x2k+1 )

S(1) : S(k) ⇒ S(k + 1) : = =

k+1

x − x2 . (1 − x)(1 − x2k+1 )

= 1.19.

1 2 x4 + x2 + 1 1 −3 = x2 − 2 + 2 = x x x2 1 1 x6 − 1 −3= 2 (x4 − 2 ) − 3, 2 2 x (x − 1) x −1 x 1 1 1 1 2 (x − ) + (x2 − 2 )2 + (x3 − 3 )2 + . . . + (xk+1 − k+1 )2 x x x x  2 1 1  1  2k+2 x − 2k − 2k − 1 + xk+1 − k+1 x2 − 1 x x 4(k+1) + 1 1 1 x (x2k+2 − 2k ) − 2(k + 1) − 1 + x2 − 1 x x2(k+1) x4(k+1) − x2 + x4k+6 − x4(k+1) + x2 − 1 − 2(k + 1) − 1 x2(k+1) (x2 − 1) 1  1  2k+4 − 2(k + 1) − 1. x − x2 − 1 x2k+2 

x−

S(1) : = S(k) ⇒ S(k + 1) : = = = =

1.20. Dla pewnego całkowitego l mamy (a) 62 − 1 = 36 − 1 = 35.

S(1) :

62(k+1) − 1 = 36 · 62k − 1 = 35 · 62k + 62k − 1 = 35l.

S(k) ⇒ S(k + 1) : (d)

62 + 31+2 + 31 = 36 + 27 + 3 = 66

S(1) : S(k) ⇒ S(k + 1) :

62k+2 + 3k+3 + 3k+1 =

36 · (62k + 3k+2 + 3k ) + 3k+3 + 3k+1 − 36 · 3k+2 − 36 · 3k

131

Rozwiązania = = =

11l − (6 + 324) · 3k 11(l − 30 · 3k ).

Ponieważ 1053 = 34 · 13 więc twierdzenie jest rów-

(m)

noważne 13|32n−2 (52n − 3n 22n ), czyli 13|52n − 3n 22n ,

30 · 52 − 31 · 22 = 25 − 12 = 13,

S(1) : S(k) ⇒ S(k + 1) :

11 · l + (27 + 3 − 36 · 9 − 36) · 3k

=

52k+2 − 3k+1 22k+2 = 25 · 5k − 12 · 3k 22k 12(5k − 3k 22k ) + 13 · 52 = 13l + 13 · 52 .

1.21. Korzystamy tutaj z zasady indukcji zupełnej. √ √ (1 + 2)1 + (1 − 2)1 2 S(1) : = = 1 = a1 , 2 2 √ √ 6 (1 + 2)2 + (1 − 2)2 = = 3 = a2 , S(2) : 2 2 S(i), 1 ≤ i ≤ k ⇒ S(k + 1) : ak+1 = 2ak + ak−1 √ √ (1 + 2)k + (1 − 2)k = 2 √ 2 √ (1 + 2)k−1 + (1 − 2)k−1 + 2√ √ √ √ (3 + 2 2)(1 + 2)k−1 + (3 − 2 2)(1 − 2)k−1 = √ k+1 √ 2k+1 (1 + 2) + (1 − 2) . = 2 1.22. S(0) :

20 + 30 = 2 = f (0),

S(1) :

21 + 31 = 5 = f (1),

S(i), 1 ≤ i ≤ k ⇒ S(k + 1) :

= =

f (k + 1) = 5f (k) − 6f (k − 1)

5 · 2k + 5 · 3k − 6 · 2k−1 − 6 · 3k−1 ,

4 · 2k−1 + 9 · 3k−1 = 2k+1 + 3k+1 .

1.23. S(1) : S(i), 1 ≤ i ≤ k ⇒ S(k + 1) :

oczywiste, ak+1 = 1 · a1 + 2 · a2 + 3 · a3 + . . . + k · ak

132

Rozwiązania 3 · 1! +

=

3 3 3 · 2 · 2! + · 3 · 3! + . . . + · k · k! 2 2 2

3 3 + [(3! − 2!) + (4! − 3!) + . . . + ((k + 1)! − k!)] 2 3 (k + 1)!. 2

= = 1.24. S(1) : S(2) : S(i), 1 ≤ i ≤ k ⇒ S(k + 1) : = = = =

5 = a1 , 5 = 5 = a2 , 20 a1 a2 ak ak+1 = k−1 + k−2 + . . . + 0 2 2 2 5 · 32 5 · ( 32 )k−2 5 5 + + + ... 2k−1 2k−2 2k−3 20 h i 5 1 2 k−2 + 1 + 3 + 3 + . . . + 3 2k−2 2 5 1 + 3k−1 − 1 2k−2 2  3 k−1 . 5· 2

1.25. S(0) :

0! + 20 = 2,

S(1) :

1! + 21 = 3,

S(2) :

2! + 22 = 6,

S(i), 0 ≥ i ≥ k ⇒ S(k + 1) :

= = = =

ak+1 = (k + 5)ak − 4(k + 1)ak−1 + 4(k − 1)ak−2 (k + 5)(k! + 2k ) − 4(k + 1)((k − 1)! + 2k−1 )

+4(k − 1)((k − 2)! + 2k−2 )

(k − 1)!(k2 + 5k − 4k − 4 + 4)

+2k (k + 5 − 2k − 2 + k − 1)

(k − 1)!(k2 + k) + 2k · 2 (k + 1)! + 2k+1 .

133

Rozwiązania 1.26. Mamy (a)

fn (x) =

(b)

fn (x) =

  

1 1−x , − 1−x x ,

n = 3k + 1, n = 3k + 2, n = 3k,

  x,

√ x , 1+nx2

Dowód (a) S(1) : S(3k + 1) ⇒ S(3k + 2) : S(3k + 2) ⇒ S(3k + 3) : S(3k + 3) ⇒ S(3k + 1) :

oczywiste, 1 1−x = 1 , −x 1 − 1−x x=

1 1−x − 1 1−x

1

,

oczywiste .

natomiast dowód (b): S(1) :

oczywiste, x

S(k) ⇒ S(k + 1) :

√ x 2 p q 1+x . = 2 x2 1 + (k + 1)x 1 + k 1+x 2

1.27. Oczywiście n = 2 jest liczbą pierwszą, czyli iloczynem jednej liczby pierwszej - samej siebie. Niech n będzie dowolną liczbą naturalną większą od 2. Załóżmy, że każdą liczbę naturalną mniejszą od n można przedstawić w postaci iloczynu liczb pierwszych. Pokażemy, że n też można. Jeśli n jest liczbą pierwszą, to teza dla n zachodzi. Jeśli n jest liczbą złożoną, to można ją przedstawić w postaci iloczynu dwóch liczb od niej mniejszych, ale większych od 1 : n = k · l, 1 < k, l < n. Na mocy założenia zarówno k, jak i l, jest iloczynem liczb pierwszych: k = p1 · . . . · pi , l = q1 · . . . · qj , a więc n = k · l też, oczywiście można tak przedstawić: n = p1 · . . . · pi · q1 · . . . · qj , co kończy dowód kroku indukcyjnego. 1.28. Gdyby istniały dwa takie ciągi {xn , n ≥ 0} i {yn , n ≥ 0} to x0 = y0 = a, x1 = y1 = b. Załóżmy więc, że istnieje takie k, że xi = yi , 0 ≤ i ≤ k − 1, i xk 6= yk , (krok indukcyjny) ale xk = pxk−1 +qxk−2 = pyk−1 +qyk−2 = yk , co prowadzi do sprzeczności. 1.29. Jedna płaszczyzna dzieli przestszeń na 2 + (1 − 1) · 1 = 2 różne obszary a jeśli mamy n − 1 płaszczyzn i 2 + (n − 2)(n − 1) obszarów, to dokładając jedną płaszczyznę w położeniu ogólnym, dochodzi nam 2(n − 1) obszarów, a więc mamy 2+(n−2)(n−1)+2(n−1) = 2+(n−1)n obszarów.

134

Rozwiązania 1.30. Oczywiście w dowodzie indukcyjnym pominęliśmy krok początkowy: dla n = 1 mamy n(n + 1) = 2 - liczba parzysta. 1.31. W przypadku n = 3 mamy P1 = {p2 , p3 } i P2 = {p1 , p2 } i punkty przecięcia prostych z P1 i P2 mogą być różne. 1.32. (a) Mamy x\y 0 1 2 3 4

0 1 2 3 5

1 2 3 5 13

13 65533 2

2 3 4 7 29 22

22

−3

3 4 5 9 61 2

2 22

22

4 5 6 11 125 −3 2

22 22

22

n n+1 n+2 2n + 3 2n+3 − 3 −3

(b) Indukcyjnie ze względu na m. m = 0. Dla m = 0 wynika to wprost z definicji. m = 1. Natomiast dla m = 1 otrzymujemy

·2 ··

2| 2{z } −3 n+3 razy

A(1, 0) = A(0, 1) = 2 > 1, A(1, n) = A(0, A(1, n − 1)) = A(1, n − 1) + 1 > (n − 1) + 1 + 1 = n + 1. m > 1. Mamy z założeń indukcyjnych: A(m, 0) = A(m − 1, 1)

założenie ind.

>

1,

A(m, n) = A(m − 1, A(m, n − 1))

założenie ind.

>

A(m, n − 1) + 1,

tak więc wykonujemy tutaj indukcję względem n i otrzymujemy tezę. (c) Z udowodnionego punktu (b) mamy A(m, n) = A(m − 1, A(m, n − 1)) ≥ A(m, n − 1) + 1 > A(m, n − 1), a więc funkcja Ackermanna jest funkcją niemalejącą drugiego argumentu. Z drugiej strony, wykorzystując ten fakt oraz A(m, n−1) ≥ n−1+1 = n otrzymujemy A(m, n) = A(m − 1, A(m, n − 1)) ≥ A(m − 1, n), co kończy dowód tego podpunktu. (d) Iterując definicję otrzymujemy A(m + 1, x + y) = A(m, A(m + 1, x + y − 1))

= A(m, A(m, A(m + 1, x + y − 2))) = . . . = A(m, A(m, . . . A(m A(m + 1, x)) . . .). {z } | y− razy

(10.1)

135

Rozwiązania Zauważmy teraz, że Ponieważ

A(m + 2, x − 1) ≥ 2x.

A(1, n) = A(0, A(1, n − 1)) = A(1, n − 1) + 1 = A(1, n − 2) + 2 = . . . = A(1, 0) + n = n + 2.

oraz A(2, n) = A(1, A(2, n − 1)) = 2 + A(2, n − 1) = 4 + A(2, n − 2) = . . . = 2n + A(2, 0) = 2n + A(1, 1) = 2n + 3,

(por. z tabelą z punktu (a)). Ponadto wykorzystując wynik punktu (c) mamy A(m + 2, x − 1) = A(m + 1, A(m + 2, x − 2)) | {z } | {z } ≥1

≥2

≥ A(1, A(2, x − 2)) = A(2, x − 2) + 2

= 2(x − 2) + 3 + 2 > 2x.

Stąd, kładąc 0 ≤ y ≤ x otrzymujemy A(m+1, x+y) ≤ A(m+1, 2x) ≤ A(m+1, A(m+2, x−1)) = A(m+2, x), co po uwzględnieniu (10.1) kończy dowód (d). 1.33. S(0) Oczywiście x ∈ Bo wtedy i tylko wtedy gdy x ∈ Ao .

S(k) ⇒ S(k + 1) Niech x będzie dowolnym elementem zbioru X. Zdefiniujmy dwie funkcje zdaniowe: Φ(k) = {x występuje w parzystej liczbie zbiorów spośród {Ao , A1 , A2 , . . . Ak },},

Ψ(k) = {x ∈ Ak },

i rozważmy cztery sytuacje: Φ(k) ∧ Ψ(k + 1) Wtedy z założenia indukcyjnego x 6∈ Bk a więc x ∈ Ak+1 \Bk ⊂ Bk ÷ Ak+1 . Φ(k) ∧ (∼ Ψ(k + 1)) Wtedy z założenia indukcyjnego x 6∈ Bk a więc x 6∈ Bk ÷ Ak+1 .

136

Rozwiązania (∼ Φ(k)) ∧ Ψ(k + 1) Wtedy z założenia indukcyjnego x ∈ Bk a więc x ∈ Ak+1 ∩ Bk a stąd x 6∈ Bk ÷ Ak+1 . (∼ Φ(k)) ∧ (∼ Ψ(k + 1)) Wtedy z założenia indukcyjnego x ∈ Bk a więc x ∈ Bk \Ak+1 ⊂ Bk ÷ Ak+1 . 1.34. (a) Udowodnimy, że p ⇒ p ⇒ . . . ⇒ p jest zdaniem zawsze prawdziwym dla |

{z

2n razy

}

dowolnego p i n ≥ 1. S(1) : Rzeczywiście, z Tabelki 1 mamy p ⇒ p ≡ 1 zarówno dla p = 0 jak i p = 1. S(k) ⇒ S(k + 1) : Z założenia indukcyjnego wystarczy wykazać, że 1 ⇒ p ⇒ p ≡ 1 ale zwróćmy uwagę, że 1 ⇒ p jest zdaniem, które ma zawsze wartość logiczną p i teza wynika z poprzedniego podpunktu. (b) S(1) : Oczywiście ∼ p1 ≡∼ p1 . S(k) ⇒ S(k + 1) : Z założenia indukcyjnego wystarczy wykazać, że ∼ (p ∧ q) ≡ (∼ p∨ ∼ q) a to wynika z Tabelki p 0 0 1 1

p∧q 0 0 0 1

q 0 1 0 1

∼ (p ∧ q) 1 1 1 0

∼p 1 1 1 0

∼q 1 1 1 0

∼ p∨ ∼ q 1 1 1 0

Kładziemy teraz p = p1 ∧ p2 ∧ p3 ∧ . . . ∧ pk , q = pk+1 i otrzymujemy tezę. 1.35. S(4) : S(5) :

4 = 2 · 2 zł. + 0 · 5 zł.,

5 = 0 · 2 zł. + 1 · 5 zł.,

jeśli teraz założymy S(k − 1), S(k), a więc w szczególności k − 1 = α · 2 zł. + β · 5 zł., to wtedy S(k + 1)

:

k + 1 = (α + 1) · 2 zł. + β · 5 zł.

137

Rozwiązania

Rozdział 2. Wstęp do rekurencji, metoda repertuaru 2.1. Przenosimy na wolną iglicę podwójną (n − 1)-wieżę, następnie przenosimy dwa największe krążki i znowu przenosimy podwójną (n − 1)-wieżę, co prowadzi do rekurencji (

T1 = 2, Tn = 2Tn−1 + 2,

którą można rozwiązać na przykład metodą repertuaru parametryzując do (

t1 = α, tn = 2Tn−1 + β,

dalej testujemy funkcje

(

(

tn = 1 1 = α 1 = 2+β

α = 1 β = −1 1 = A(n) − B(n)

(

tn = 2n 21 = α 2n = 2n + β (

α = 2 β = 0 2n = 2A(n)

zatem tn = α2n−1 + β(2n−1 − 1). Stąd Tn = 2n+1 − 2 = 2hn , n ≥ 0, gdzie hn jest minimalną ilością ruchów potrzebnych do przeniesienia krążków w ”zwykłej” wieży z Hanoi. 2.2. Rekurencja powstała w wyniku następującej procedury: (i) Przenosimy n − k krążków na jedną iglicę wykorzystując wszystkie 4 iglice (Wn−k ). (ii) Przenosimy największe k krążki na wolną iglicę wykorzystując tylko trzy iglice (hk ). (iii) Przeniesione w punkcie (i) krążki przenosimy na tę iglicę, na którą przenieśliśmy krążki w punkcie (ii) wykorzystując dowolnie wszystkie 4 iglice. 2.3. Zauważmy, że każdą taką ”literę” V można w myślach przedłużyć do dwóch przecinających się prostych:

138

Rozwiązania

✁5 ✁✟✟ ✟✟✁ ❆ ✟✟ ✁ ❆ ✁6 ❆ 3 ✟✟ ❍ ✁ ❆✟✟ ✁ ❍✟✟❆ 4 ✟❍❍ 2 ❆ ✁ ❍ ✟ ❆❍❍ ✁ ✁ ❆ ❍❍ 1 ❆7 ✁ ❍❍ ❍ ❆✁ ✁❆ ❆ ❆

❍

✟✟ ✟✟ 2 ❍✟✟ ✟❍❍ ❍ 1 ❍❍ ❍

❍ ✟ ✟

❍

✟

V2 = 7

V1 = 2

✁

❆

Jeśli więc ln jest liczbą obszarów w problemie ”pizzy” (zob. Problem 1.2.2 + [12]) to poszukiwana liczba obszarów Vn = l2n −2n, a ponieważ ln = n(n+1) 2 1, n ≥ 0, więc Vn = n(2n − 1) + 1, n ≥ 0. 2.4.

✁ ✁

✁❆ ✁ ❆

❆ ❆

R1 = 2

Ro = 1

✁❆ ✁✁❆❆ ✁✁ ❆❆ ❆❆ ✁✁ ✁ ❆

R2 = 4

✁❆ ✁✁❆❆ ✁✁✁❆❆❆ ✁✁✁ ❆❆❆ ❆❆ ✁✁ ✁ ❆

R3 = 8

✁❆ ✁✁❆❆ ✁✁✁✁❆❆❆❆ ✁✁✁✁ ❆❆❆❆ ❆❆ ✁✁ ❆❆ ✁✁ ✁ ❆

R4 = 14

✁❆ ✁✁❆❆ ✁✁✁✁❆❆❆❆ ✁✁✁✁✁❆❆❆❆❆ ✁✁✁ ❆❆❆ ❆❆ ✁✁ ❆❆ ✁✁ ✁ ❆

R5 = 22

Łatwo widać, że pierwszy trójkąt dodał dwa obszary (wewnętrzny i zewnętrzny) a każdy następny (n-ty) trójkąt dodaje 2(n − 1) obszarów do poprzednich. Zatem (

Ro = 1, R1 = 2, Rn = 2(n − 1) + Rn−1 , n ≥ 2,

a stąd Rn =

(

2(n − 1) + 2(n − 2) + . . . + 2 + 2 = n2 − n + 2, n ≥ 1, 1, n = 0.

2.5. Mamy

139

Rozwiązania

Po = 1

P1 = 2

P2 = 8

P3 = 20

Łatwo widać, że kolejny, n-ty trójkąt może zwiększyć maksymalnie ilość obszarów o 6(n − 1). Stąd Pn = 6(n − 1) + 6(n − 2) + . . . 6 + P1 , n ≥ 1, zatem uwzględniając, że P1 = 2 : Pn = 3n(n − 1) + 3, n ≥ 1. W konsekwencji Pn =

(

3n(n − 1) + 2, n ≥ 1, 1, n = 0.

2.6. Mamy ✤✜ ✎☞ ✍✌ ✣✢

Oo = 1

O1 = 3

✤✜ ✛✘ ✤✜ ✎☞ ✚✙ ✣✢ ✍✌ ✣✢

O2 = 12

Łatwo widać, że kolejne, n-te koło może zwiększyć maksymalnie liczbę obszarów o 8(n − 1) + 1. Stąd On = 8(n − 1) + On−1 + 1, n ≥ 1, zatem On =

8n(n − 1) + n + 1 + Oo = 4n2 − 3n + 2, n ≥ 1, 2

więc ostatecznie On =

(

4n2 − 3n + 2, n ≥ 1, 1, n = 0.

2.7. Niech m = N W W (n + 1, n + 2, . . . , 2n). Można też wybrać dowolną wielokrotność N W W (n + 1, n + 2, . . . 2n), na przykład m = (2n)! n! .

140

Rozwiązania 2.8. Wypiszmy kilka początkowych wyrazów ciągu: Wyraz Wartość Ro α R1 β 1+β R2 α 1+α+β R3 αβ 1+α R4 β R5 α R6 β i jak widać ciąg ten jest okresowy o okresie 5, a więc

R5n+k =

  α       β       

1+β α 1+α+β αβ 1+α β

dla dla dla dla dla

k k k k k

= 0, = 1, = 2, = 3, = 4.

2.9. Wypiszmy kilka początkowych wyrazów ciągu: Wyraz Wartość Wyraz Wartość 4 Ro 1 R7 5 R1 2 R8 1 2 R2 5 R9 R3 8 R10 5 8 R4 7 R11 16 R5 R 7 12 5 16 7 R6 5 R14 5 i jak widać ciąg ten jest okresowy o okresie 8, a więc

R8n+k

              

1 2 5 8 =  7             

16 5 7 5 4 5

dla dla dla dla dla dla dla

k k k k k k k

= 0, = 1, = 2, = 3, = 4, = 5, = 6,

dla k = 7.

141

Rozwiązania 2.10. Wypisując kilka początkowych wyrazów widzimy, że gn = 3n jest rozwiązaniem tej rekurencji. Żeby to udowodnić posłużymy się dowodem indukcyjnym: S(0) :

30 = 1,

S(1) :

31 = 3, gn = 32(n−1)−(n−2) = 3n .

S(n − 1), S(n − 2) ⇒ S(n) :

k

2.11. Wypisując kilka początkowych wyrazów widzimy, że g(22 ) = k jest rozwiązaniem tej rekurencji. Żeby to udowodnić posłużymy się dowodem indukcyjnym: S(0) : k−1

S(22

k

) ⇒ S(22 ) :

0

g(22 ) = 0, p

k−1

g22k = 2g( 22k ) + 1 = g(22

) + 1 = k − 1 + 1 = k.

2.12. Dzielimy stronami rekurencję przez 2n i podstawiamy Tn = otrzymując

   To = 1,

(

n   Tn = 2 −

ao ,

nan 2n ,

n−1 P k=1

n = 0, n ≥ 1,

Tk , n = 1, 2, ....

Przepisując ostatnie równanie dla n i n − 1 i odejmując stronami otrzymujemy

−

Tn Tn−1

= 2n − T1 − T2 − . . . − Tn−2 − Tn−1 , = 2n−1 − T1 − T2 − . . . − Tn−2 ,

Tn − Tn−1 = 2n−1

czyli Tn = 2n−1 , n ≥ 2.

Bezpośrednio obliczamy To = 1, T1 = 2, i wracamy do an    1,

n = 0, n = 1, an =   22n−1 n , n ≥ 2. 4,

− Tn−1

142

Rozwiązania 2.13. Szukamy rozwiązania postaci g(n) = αA(n) + βB(n), n ≥ 1. Z Uwagi 2.1 (iii) wiemy, że jeśli n = (1, bm−1 bm−2 . . . b1 bo )2 to αA(n) = (α, bm−1 , bm−2 , . . . b1 , b0 )1 = α + bm−1 + bm−2 + . . . + b1 + b0 , n ≥ 1, co stanowi definicję funkcji A. Przyjmijmy teraz g(n) = n wtedy g(n) = n α=1 β=1 prowadząc do B(n) = n − A(n), n ≥ 1,

i w konsekwencji:

g(n) = (α − β)A(n) + βn, n ≥ 1. 2.14. Szukamy rozwiązania postaci h(n) = αA(n) + γo B(n) + γ1 C(n) + δ0 D(n) + δ1 E(n). Z Uwagi 2.1 (iii) wiemy, że jeśli n = (1, bm−1 bm−2 . . . b1 bo )2 to αA(n) + δ0 D(n) + δ1 E(n) = (α, δbm−1 , δbm−2 , . . . δb1 , δb0 )4 , n ≥ 1, co stanowi definicę funkcji A, D, E. Przyjmijmy teraz h(n) = n i h(n) = n2 , wtedy h(n) = n h(n) = n2 α=1 α=1 γo = −2 γo = 0 γ1 = −2 γ1 = 4 δo = 0 δ0 = 0 δ1 = 1 δ1 = 1 prowadząc do B(n) = C(n) =

3A(n) + 3E(n) − n(n + 1) , n ≥ 1, 4 n2 − A(n) − E(n) , n ≥ 1. 4

143

Rozwiązania

2.15. Z Uwagi 2.1 (iii) mamy h(125) = h((1331)4 ) = (α1 , β3 , β3 , β1 )3 = (3, 0, 0, 5)3 = 86. 2.16. Z Uwagi 2.1 (iii) dla βj = j 2 , j = 0, 1, 2, 3, 4, mamy h(312) = h((2222)5 ) = (α2 , β2 , β2 , β2 )2 = (3, 4, 4, 4)2 = 52. 2.17. Parametryzujemy do (

T1 = α, Tn = 4Tn−1 +

β 3n ,

dla n > 0.

i testujemy różne funkcje: (

1 3n

Tn = 1/3n 1 3 1 n 3(

= α, 4 = 3n−1 + 3βn , α = 31 , β = −11, 1 = 3 A(n) − 11B(n),

(

Tn = 4n 4 = α, 4n = 4n + 3βn , ( α = 4, β = 0, n 4 = 4A(n),

skąd A(n) = 4n−1 , 12n−1 − 1 , B(n) = 11 · 3n

a zatem

Tn = 7 · 4n−1 + 5 ·

12n−1 − 1 . 11 · 3n

2.18. Parametryzujemy do (

To = α, Tn = nTn−1 + βn + γ,

dla n > 0.

i rozważamy rekurencję: Tn = nTn−1 + 1. Rekurencja ta, po rozpisaniu początkowych wyrazów ma jedno z rozwiązań Tn = 1 + n + n(n − 1) + . . . n! =

n X n!

k=1

k!

dlatego testujemy (zob. Uwaga 2.1 (ii)) następujące funkcje

144

Rozwiązania

Tn = 1

Pn Tn = k=1 n! k!  = α,  0P Pn−1 n n! = n k=1 (n−1)! k=1 k! k!  +βn + γ,   α = 0, β = 0,  γ = 1, Pn n! k=1 k! = C(n)

Tn = n!



1 = α, 1 = n + βn + γ,   α = 1, β = −1,  γ = 1, 1 = A(n) − B(n) + C(n),



1 = α, n! = n · (n − 1)! + βn + γ,   α = 1, β = 0,  γ = 0, n! = A(n),

skąd A(n) = n!, n X n!

B(n) = n! − 1 + n X n!

C(n) =

k=1

k!

k!

k=1

,

,

a zatem 

Tn = −5 · n! − 1 +

n X n! 

k=1

k!

.

2.19. Parametryzujemy do (

g1 = α, gn+1 = 2gn + β,

dla n > 0,

i wybieramy (zob. Uwaga 2.1 (ii)) następujące funkcje (

(

gn = 1 1 = α, 1 = 2 + β,

α = 1, β = −1, 1 = A(n) − B(n),

(

gn = 2n 2 = α, 2n+1 = 2 · 2n + β, (

α = 2, β = 0, n 2 = 2A(n),

skąd A(n) = 2n−1 , B(n) = 2n−1 − 1, a zatem gn = 2n + 7 · (2n−1 − 1).

145

Rozwiązania

2.20. Parametryzujemy (zob. Uwaga 2.1 (i)) do (

g1 = α, gn+1 = gn + βn2 + γn + δ,

dla n > 0,

i podstawiamy następujące funkcje gn = 1 1 = α, 1 = 1 + βn2 + γn + δ, α = 1,    β = 0, γ = 0,    δ = 0, 1 = A(n), g n = n2  1 = α, n2 + 2n + 1 = n2 + βn2 + γn + δ, α = 1,    β = 0, γ = 2,    δ = 1, n2 = A(n) + 2C(n) + D(n), 

gn = n 1 = α, n+1  = n + βn2 + γn + δ, α = 1,    β = 0, γ = 0,    δ = 1, n = A(n) + D(n), g n = n3  1 = α, n3 + 3n2 + 3n + 1 = n3 + βn2 + γn + δ, α = 1,    β = 3, γ = 3,    δ = 1, n3 = A(n) + 3B(n) + 3C(n) + D(n), 

skąd A(n) = 1, n(n − 1)(2n − 1) B(n) = , 6 n(n − 1) C(n) = , 2 D(n) = n − 1, a zatem gn =

n(n − 1)(2n − 1) + 3n − 2. 6

2.21. Parametryzujemy do (

g1 = α, gn+1 = 3gn + βn + γ,

dla n > 0,

i sprawdzamy następujące funkcje (zob. Uwaga 2.1 (ii))

146

(

Rozwiązania

gn = 1 1 = α, 1 = 3 + βn + γ,    α = 1, β = 0,   γ = −2, 1 = A(n) − 2C(n),

gn = n

(

(

1 = α, n + 1 = 3n + βn + γ,    α = 1, β = −2,   γ = 1, n = A(n) − 2B(n) + C(n),

gn = 3n 3 = α, 3n+1 = 3n+1 + βn + γ,    α = 3, β = 0,   γ = 0, 3n = 3A(n),

skąd A(n) = 3n−1 , 3n − 1 − 2n B(n) = , 4 3n−1 − 1 , C(n) = 2 a zatem gn = −3n +

3n − 1 − 2n 3n−1 − 1 − . 4 2

2.22. Parametryzujemy do (

g1 = α, gn+1 = 2gn + βn2 + γn + δ,

dla n > 0,

i testujemy następujące funkcje (zob. Uwaga 2.1 (ii)) gn = 1 1 = α, 2 1 =  2 + βn + γn + δ, α = 1,    β = 0, γ = 0,    δ = −1, 1 = A(n) − D(n), g n = n2  1 = α, n2 + 2n +  1 = 2n2 + βn2 + γn + δ, α = 1,    β = −1, γ = 2,    δ = 1, n2 = A(n) − B(n) + 2C(n) + D(n), 

gn = n 1 = α, n + 1 = 2n + βn2 + γn + δ, α = 1,    β = 0, γ = −1,    δ = 1, n = A(n) − C(n) + D(n), gn = 2n  2 = α, 2n+1 = 2n+1 + βn2 + γn + δ, α = 2,    β = 0, γ = 0,    δ = 0, 2n = 2A(n), 

147

Rozwiązania skąd A(n) = 2n−1 , B(n) = 3 · 2n − n2 − 2n − 3, C(n) = 2n − n − 1,

D(n) = 2n−1 − 1, a zatem

gn = 2n − n2 − 2n − 2.

Rozdział 3. Sumy i ich obliczanie, metoda czynnika sumacyjnego 3.1. Mamy an = cn =

(

(

a więc

1, n = 0, 1, 2, n ≥ 2,

n = 1, n ≥ 2, ( 1, n = 1, = 2n−2 n , n ≥ 2,

bn =

4, n = 0, 5n, n ≥ 1,

sn

(

1,

n n−1 ,

   4,

n = 0, n = 1, Tn =   n (9 + 5 Pn−2 2k ), n ≥ 2, k=0 2n−2 9,

a ponieważ

n−2 X k=0

więc Tn =

(

2k = 2n−1 − 1,

4, n

2n−1

(5 ·

2n−1

n = 0, + 4), n ≥ 1.

3.2. Mamy an =

(

1, n = 0, 2, n ≥ 1,

bn = 3, n ≥ 1,

cn = 3n , n ≥ 0,

a więc Tn =

n X 2k−1 k 3n 1 · 3 · 1 + ( 3 ) 2n 3 3k k=1

sn =

2n−1 , n ≥ 1, 3n

148

Rozwiązania n−1 X 3n (1 + 2k ) n 2 k=0

=

= 3n . 3.3. Mamy an = cn = a więc

(

    

1,

n = 0, 1, n ≥ 2, 3, n = 0, 1, n = 1, n! n−1 , n ≥ 2,

bn = n, n ≥ 1,

n2 (n−1)2 ,

Tn =

(

sn =

3, n! n2 (3

+1+

a ponieważ n−1 X

k=

k=0

więc Tn =

(

+

1, (n−1)2 n! ,

n = 1, n ≥ 2,

n = 0, k), n ≥ 1, k=0

Pn−1

(n − 1)n , 2

3, n! n2 (4

(

(n−1)n ), 2

n = 0, n ≥ 1.

3.4. Dzieląc ostatnią równanie przez n mamy 1, n = 0, n, n ≥ 1, ( 7, n = 0, = 1 3n (n−1)! , n ≥ 1,

an = cn

(

bn = 1, n ≥ 1, sn = (n − 1)!, n ≥ 1,

a więc Tn = = =

n X 1 1 (7 + ) k n! 3 k=1

1 1 − 3n+1 1 (7 − 1 + ) n! 1 − 31 1 1 1 (7 − ), n ≥ 1. n! 2 2 · 3n

149

Rozwiązania 3.5. Podane równanie rekurencyjne jest równoważne (

czyli

To = 0, 1 )3 , n = 1, 2, 3, ... . (n2 Tn − (n − 1)Tn−1 )3 = ( (n+1)! (

a tutaj

(

1, n = 0, n2 , n ≥ 1, ( 0, n = 0, = 1 (n+1)! , n ≥ 1,

an = cn

To = 0, n2 Tn = (n − 1)Tn−1 +

1 (n+1)! ,

n = 1, 2, 3, ... .

bn = (n − 1), n ≥ 1, sn = (n − 1)!, n ≥ 1,

a więc n 1 1 X n · n! k=1 k(k + 1)

Tn =

n 1 1 1 X ( − ) n · n! k=1 k k + 1

=

1 1 (1 − ) n · n! n+1 1 , n ≥ 1. (n + 1)!

= = 3.6. Mamy an cn

(

1, n = 0, = 2, n ≥ 1, ( 3, n = 0, = n3 2n , n ≥ 1,

a więc Tn =

(

bn =

(

sn =

2n−1 n2 , n

3, n2 2n (3

+

n(n+1) ), 4

1, n = 1, n 2 ) , n ≥ 2, ( n−1 ≥ 1,

n = 0, n ≥ 1.

3.7. Dzielimy ostatnie równanie stronami przez 2n i podstawiamy Tn = an 2n , n ≥ 0, otrzymując    To = 1,

n   Tn = 2 +

n−1 P k=0

Tk , n = 1, 2, ... .

150

Rozwiązania Odejmując stronami ostatnie równanie dla n i dla n − 1 otrzymujemy

−

= 2n + T1 + T2 + . . . + Tn−2 + Tn−1 , = 2n−1 + T1 + T2 + . . . + Tn−2 ,

Tn Tn−1

Tn − Tn−1 = 2n−1

+ Tn−1

a więc otrzymujemy rekurencję (

To = 1, Tn = 2Tn−1 + 2n−1 , n = 1, 2, ... .

Stosując metodę czynnika sumacyjnego otrzymujemy an = 1, n ≥ 0,

bn = 2, n ≥ 1,

cn =

(

1, n = 0, 2n−1 , n ≥ 1,

sn =

1 , n ≥ 1, 2n

a więc Tn =

(

1, n = 0, 2n (1 + n2 ), n ≥ 1,

a początkowy ciąg spełnia an =

(

1, n = 0, n n 4 (1 + 2 ), n ≥ 1.

3.8. Mamy    1,

n = 0, an = 2, n = 1,   n, n ≥ 2,  3,      1, 2 n(n+2) cn = a więc

Tn =

    

(n−1)!2(n+1)(n+3) 5n2 , + 2·(n−3)!

   3,  

n = 0, n = 1,

7 4,

1 1 2·(n−1)! (3 2

+

Pn

+

n2 2n−1 (n−1)!

n ≥ 2,

k+2 k=2 ( (k+1)(k+3)

bn =

(

sn =

(

1, n n−1 ,

n = 1, n ≥ 2,

1, 2·(n−1)! , n

n = 1, n ≥ 2,

n = 0, n = 1, + k2k + 5k(k − 1)(k − 2))), n ≥ 2.

151

Rozwiązania Z drugiej strony k2 + 4k + 4 k(k + 3) + k + 4 = (k + 1)(k + 2)(k + 3) (k + 1)(k + 2)(k + 3) k k+4 = + (k + 1)(k + 2) (k + 1)(k + 2)(k + 3) k+3+1 k+2−2 + = (k + 1)(k + 2) (k + 1)(k + 2)(k + 3) = k−1 − 2k−2 + k−2 + k−3

k+2 (k + 1)(k + 3)

=

= k−1 − k−2 + k−3 ,

oraz n X

k2k =

k=0

n X

k=0

k(△2k ) = k2k |n+1 − 0 n+1

= (n + 1)2

n+1

= (n − 1)2

n+1

−2

+2

n X

(△k)2k+1

k=0

+ 2,

a więc n X

k+2 + k2k + 5k3 , (k + 1)(k + 3) k=2

S =

n X

=

(k−1 − k−2 + k−3 + k2k + 5k3 ) − 3

k=0

= Hn+1 − 1 +

1 24

1 1 1 + − n + 2 4 2(n + 2)(n + 3)

1 5 + n(n − 1)(n − 2)(n − 3) + (n − 1)2n+1 + 2 − 3 , 4 24 zatem

Tn =

 3,     7

n = 0, n = 1,

4,

   

17 1 1 1 2·(n−1)! (1 24 + Hn+1 + n+2 − 2(n+2)(n+3) + 45 n(n − 1)(n − 2)(n − 3) + (n − 1)2n+1 ),

n ≥ 2.

3.9. Mamy

(

1, n = 0, β, n ≥ 1, ( α, n = 0, cn = γn!, n ≥ 1,

an =

bn = n, n ≥ 1, sn =

β n−1 n! , n

≥ 1,

152

Rozwiązania a więc Tn =

γ(β n − 1) n! ), n ≥ 0. (α + βn β−1

3.10. Połóżmy un vn

(

=

(

=

           

sn,k =

          

a stąd

1 n = 1, β1,0 , α1,0 α2,0 ...αn−1,0 β1,0 β2,0 ...βn−1,0 βn,0 , n > 1, 1 n = 1, β0,1 , α0,1 α0,2 ...α0,n−1 β0,1 β0,2 ...β0,n−1 β0,n , n > 1, a1,k−n+1 a2,k−n+2 ...an−1,k−1 b1,k−n+1 b2,k−n+2 ...bn−1,k−1 bn,k , 1 b1,k , an−k+1,1 an−k+2,2 ...an−1,k−1 bn−k+1,1 bn−k+2,2 ...bn−1,k−1 bn,k , 1 bn,1 , a1,1 a2,2 ...an−1,k−1 b1,1 b2,2 ...bn−1,k−1 bn,k ,

Tn,0 =

β1,0 ···βn,0 α1,0 ···αn,0

T0,k

β0,1 ···β0,k α0,1 ···α0,k

=

Tn,k =

          





1 sn,k an,k 1 sn,k an,k 1 sn,k an,k

d+

d+   

1 < n < k, 1 = n < k, n > k, 1 = k ≤ n, n = k,



Pn

i=1 ui γi,0 ,

Pk



i=1 vi γ0,i ,

T0,k−n + Tn−k,0 + d+

Pn

Pn



i=1 si,k−n+i ci,k−n+i , n < k,

Pk

i=1 sn−k+i,i cn−k+i,i

i=1 si,i ci,i



,



, n > k, n = k.

3.11. Ponieważ (

−1, k ≥ n, 1, k < n,

cn,k =

an,k = 2k,

bn,k =

αn,0 = n,

βn,0 = 1,

γn,0 =

α0,k = (k + 1)2 ,

β0,k = k,

γ0,k =

więc un = (n − 1)!, vn = n!,

sn,k

  

(−1)n 2n−1 (k−1)! , (k−n)! k−1 2 (k − 1)!,

k > n, = k < n,   (−1)k 2k−1 (k − 1)!, k = n,

(

1 (k−1)! , 1 (n−1)! ,

2n−1 (n−1)! , (−2)k−1 , k!

k ≥ n, k < n,

153

Rozwiązania a stąd T0,0 = 0, 2n − 1 , n > 1, Tn,0 = n! 1 − (−2)k T0,k = , k > 1, 3(k + 1)(k + 1)! Tn,k =

        

h

1−(−2)k−n 1 2 (−2)n k! 3(k−n+1) h 1 n−k 2 − 2k k!(n−k)! n n 2 −(−1) 3·2n ·n! ,

i

(−2)n −1 , 3 i Pk 2i−1 , + i=1 n−k+i−1 ( )

+ 1

n < k, n > k,

n−k

n = k.

3.12. Oczywiście Tn,k = =

bn,k cn,k Tn,k−1 + an,k an,k bn,k γn,k−1 cn,k bn,k βn,k−1 Tn−1,k−1 + + , an,k αn,k−1 an,k αn,k−1 an,k

a z drugiej strony Tn,k = =

γn,k βn,k Tn−1,k + αn,k αn,k βn,k cn−1,k γn,k βn,k bn−1,k Tn−1,k−1 + + , αn,k an−1,k αn,k an−1,k αn,k

zatem βn,k bn−1,k αn,k an−1,k

=

bn,k βn,k−1 an,k αn,k−1 ,

γn,k αn,k

=

bn,k γn,k−1 an,k αn,k−1

βn,k cn−1,k αn,k an−1,k

+

+

cn,k an,k .

Jeśli teraz położymy an,0 an,1 . . . an,k−1 , bn,1 bn,2 . . . bn,k α0,0 α1,0 . . . αn−1,0 , = β1,0 β2,0 . . . βn,0 = 1,

sn,k = vn α0,0 to

Tn,k =

h

an,0 1 (d sn,k an,k vn αn,0

+

Pn

j=1 vj γj,0 ) +

Pk

i

j=1 sn,j cn,j , n, k ≥ 0.

154

Rozwiązania 3.13. Ponieważ (n − 1)Un−1 = 2Tn−1 − więc

(

T0 = 1, nTn = 2Tn−1 −

3 , (n − 1)!

2 (n−1)! .

Podstawiając do wzoru na rozwiązanie metodą czynnika sumacyjnego (

1, n = 0, n, n ≥ 1, ( 1, n = 0, cn = 2 , n ≥ 1, − (n−1)! an =

otrzymujemy

a

bn = 2, sn =

(n−1)! 2n , n

n  X 2n+1 − 2 2n  1− 21−j = Tn = n! n! j=1

Un =

(

5,

n = 0,

2n+2 −7 n!·n ,

n ≥ 1.

3.14. Musimy policzyć: i

S =

j k−1 n X 2 X X X

1

i=0 j=1 k=1 l=1 i

=

j n X 2 X X

(k − 1)

i=0 j=1 k=1 i

=

n X 2 X (j − 1)j

2

i=0 j=1

i

= = = =

n X 2 1X j2 2 i=0 j=0

n i 1X j 3 |20 +1 6 i=0

n 1X (2i + 1)3 6 i=0

n 1X (2i + 1)2i (2i − 1) 6 i=0

≥ 1,

155

Rozwiązania = =

n 1X (8i − 2i ) 6 i=0

1 8n+1 − 1 2n+1 − 1 ( − ). 6 7 2

3.15. Musimy policzyć: S = = = =

n−1 i−1 XX

(k2 − 2k )

i=0 k=0 n−1 i−1 XX

(k2 + k1 + 2k )

i=0 k=0 n−1 X 1 3

1 ( i + i2 − 2i + 1) 3 2 i=0

1 4 1 3 n + n − 2n + 1 + n. 12 6

3.16. Obliczamy: IN CREM EN T

=

10 X i−1 k−1 X X

1

i=1 k=1 j=1

= = = =

10 X i−1 X

(k − 1)

i=1 k=1 10 X

i=1 9 X

(i − 1)(i − 2)/2 i2 /2

i=0 103

6 8 · 9 · 10 = 6 = 120. SU M

=

IN CREM X EN T i=1

120 · 121 2 = 7260.

=

i

156

Rozwiązania 3.17. Tablica a przyjmuje wartości: 

   [ai,j , 1 ≤ i, j ≤ n] =    

1 k 2k .. .

n2 kn2 2kn2 .. .

n kn 2kn .. .

... ... ... .. .

nn−1 knn−1 2knn−1 .. .

(n − 1)k (n − 1)kn (n − 1)kn2 . . . (n − 1)knn−1

a poszukiwana suma to: S =

n X X

ai,j

j|100 i=1

=

X

n

j−1

j|100

= k(

X

j|100

= =

n X

(

i=2

nj−1 )

(i − 1)k + 1)

kn(n − 1) + 2 2

X kn(n − 1) + 2 nj−1 2 j∈{1,2,4,5,10,20,25,50,100}

kn(n − 1) + 2 (1 + n + n3 + n4 + n9 + n19 + n24 + n49 + n99 ). 2

3.18. Tablica a przyjmuje wartości: 

   [ai,j 1 ≤ i, j ≤ n] =    

1 k k2 .. .

n2 kn2 k 2 n2 .. .

n kn k2 n .. .

... ... ... .. .

nn−1 knn−1 k2 nn−1 .. .

kn−1 kn−1 n k n−1 n2 . . . kn−1 nn−1

a poszukiwana suma to:

S = =

n XX

j|13 i=1 n XX

ai,j nj−1 ki−1

j|13 i=1

=

X

nj−1

j|13

= (

X

j|13

n

n−1 X

ki

i=0 n j−1 k

)

−1 k−1

       

       

157

Rozwiązania = (1 + n12 )

kn − 1 . k−1

3.19. Ponieważ n X

X

(−1)n+1−j = (−1)Sn ,

j=0

X

(−1)n+1−j =

1≤j≤n+1

(−1)n−j = Sn

0≤j≤n

więc w tym przypadku f (x) = x, g(x) = −x, zatem powinniśmy rozwiązać równanie (−1)n+1−0 + Sn = −Sn + (−1)n+1−n−1 czyli

Sn = Zauważmy, że

1 − (−1)n+1 , n ≥ 0. 2

n+1 X

Pn+1 =

k=0

(−1)n+1−k k = (−1)n+1 · 0 +

X

=

n+1−k

(−1)

1≤k≤n+1 n X n−k

=

(−1)

=

X

(−1)n+1−k k

k=1

(−1)n−k (k + 1)

0≤k≤n

k+

k=0

a ponadto

k

k→k+1

n+1 X

Pn+1 = (n + 1) −

n X

(−1)n−k = Pn + Sn ,

k=0 n X

(−1)n−k k = n + 1 − Pn ,

k=1

(zatem w naszym przypadku fn (x) = x + Sn , gn (x) = −x) a stąd n + 1 − Pn = Pn + Sn , n ≥ 0,

co prowadzi do

2n + 1 + (−1)n+1 , n ≥ 0. 4 Podobnie jak i w poprzednim przypadku Pn =

Rn+1 =

n+1 X k=0

= =

(−1)n+1−k k2 = (−1)n+1 · 0 +

X

n+1−k 2 k→k+1

(−1)

1≤k≤n+1 n X n−k 2

(−1)

k +2

k=0

= Rn + 2Pn + Sn ,

k

=

X

n+1 X

(−1)n+1−k k2

k=1

(−1)n−k (k2 + 2k + 1)

0≤k≤n n X

(−1)n−k k +

k=0

n X

(−1)n−k

k=0

158

Rozwiązania oraz n+1 X

n X

(−1)n+1−k k2 =

Rn+1 =

k=0

(−1)n+1−k k2 + (n + 1)2

k=0 2

= −Rn + (n + 1) co prowadzi do

Rn + 2Pn + Sn = −Rn + (n + 1)2 , n ≥ 0, a stąd n2 + n , n ≥ 0, 2 (fn (x) = x + 2Pn + Sn , g(x) = −x). 3.20. Ponieważ Rn =

Sn+1 = sin(x) +

n+1 X

k→k+1

(−1)k+1 sin(kx)

=

k=2

sin(x) −

= sin(x) − cos(x)Sn + sin(x)Cn

n X



(−1)k+1 sin (k + 1)x

k=1



a z drugiej strony 



Sn+1 = (−1)n+2 sin (n + 1)x + Sn , i podobnie Cn+1 = −cos(x) +

n+1 X

(−1)k cos(kx)

k→k+1

=

k=2

−cos(x) −

= −cos(x) − cos(x)Cn − sin(x)Sn oraz



n X



(−1)k cos (k + 1)x

k=1



Cn+1 = (−1)n+1 cos (n + 1)x + Cn , zatem wystarczy rozwiązać układ równań:   (1 + cos(x))Sn − sin(x)Cn  sin(x)Sn + (1 + cos(x))Cn

W

=







= −cos(x) − (−1)n+1 cos (n + 1)x .

Wyznaczniki tego układu równań to 1 + cos(x) sin(x)



= sin(x) − (−1)n+2 sin (n + 1)x ,

−sin(x) 1 + cos(x)

x = 2(1 + cos(x)) = 4cos2 ( ), 2



159

Rozwiązania   sin(x) − (−1)n+2 sin (n + 1)x   −cos(x) − (−1)n+1 cos (n + 1)x  x

W Sn =

WCn

a więc

1 + cos(x) 

−sin(x)

= sin(x) − (−1)n [2cos2 ( )sin (n + 1)x  2  x x −2sin( )cos( )cos (n + 1)x ] 2 2  x h x 1 i = 2cos( ) sin( ) − (−1)n sin (n + )x , 2 2 2  n+2 sin (n + 1)x 1 + cos(x) sin(x) − (−1)   = −cos(x) − (−1)n+1 cos (n + 1)x sin(x)   x = −cos(x) − 1 + (−1)n [2cos2 ( )cos (n + 1)x 2  x x −2sin( )cos( )sin (n + 1)x ] 2 2  x h x 1 i = 2cos( ) −cos( ) − (−1)n cos (n + )x , 2 2 2

Sn =

sin( 21 x) − (−1)n sin((n + 12 )x) W Sn = , W 2cos( 12 x)

Cn =

−cos( 21 x) − (−1)n cos((n + 12 )x) WCn . = W 2cos( 12 x)



3.21. Ponieważ zaburzanie Zn nie daje efektów, spróbujmy zaburzyć Un : Un+1

=

Un + (n + 1)Hn+1 ,

Un+1

=

1+

1 Hk+1 =Hk + k+1

n+1 X k=2 n X

kHk

k→k+1

=

=

1+

=

n + 1 + Un + Zn

1+

(k + 1)(Hk +

k=1

n X

(k + 1)Hk+1

k=1 n X 1 )=1+n+ (k + 1)Hk k+1 k=1

a z równania Un + (n + 1)Hn+1 = n + 1 + Un + Zn otrzymujemy Zn = (n + 1)(Hn+1 − 1), n ≥ 1. Podobnie z Tn+1

=

Tn + (n + 1)2 Hn+1 ,

160

Rozwiązania

Tn+1

=

1+

1 Hk+1 =Hk + k+1

n+1 X

k 2 Hk

k→k+1

=

n X

1+

k=2 n X

(k + 1)2 Hk+1

k=1

(k + 1)2 (Hk +

1 ) k+1

=

1+

=

(n + 1)(n + 2) + Tn + 2Un + Zn , 2

k=1

otrzymujemy (n + 1)(n + 2) + Tn + 2Un + Zn 2

Tn + (n + 1)2 Hn+1 = co prowadzi do

n(n+1)(2Hn+1 −1) ,n 4

Un =

Pn

Trzecią sumę (Tn ) obliczamy zaburzając Qn = Qn+1

=

Qn + (n + 1)3 Hn+1 ,

Qn+1

=

1+

1 Hk+1 =Hk + k+1

n+1 X

k 3 Hk

k→k+1

=

≥ 1. k=1 k

1+

k=2 n X

n X

3H

k:

(k + 1)3 Hk+1

k=1

=

1 1+ (k + 1)3 (Hk + ) k+1 k=1

=

(n + 1)(n + 2)(2n + 3) + Qn + 3Tn + 3Un + Zn , 6

skąd Tn =

n(n+1)(2n+1)Hn+1 6

−

n(n+1)(4n+5) ,n 36

≥ 1.

3.22. Metodą czynnika sumacyjnego mamy Tn = 1 +

n X

k k

(−1) 3 =

k=1

n X

(−1)k 3k .

k=0

Ponadto Tn+1 = 1 +

n+1 X

(−1)k 3k = 1 +

k=1

= 1 − 3Tn ,

Tn+1 = Tn + (−3)n+1 ,

n X

(−1)k+1 3k+1

k=0

161

Rozwiązania zatem 1 − 3Tn = Tn + (−3)n+1 ,

czyli

Tn =

1 − (−3)n+1 , n ≥ 1. 4

3.23. Odejmując stronami otrzymujemy Tn = nTn−1 + n!nHn ,

T0 = 1,

T1 = T0 + 1,

stąd an = 1, n ≥ 0,

bn = n, n ≥ 1,

cn =

(

1, n = 0, n!nHn , n ≥ 1,

sn =

1 , n ≥ 1, n!

zatem (zobacz zadanie 3.21) Tn = n!(1 +

n X

kHk )

k=1

= n!(1 +

n(n + 1) n(n + 1) Hn − ), n ≥ 1, 2 4

T0 = 1. 3.24. Ponieważ an = 1, n ≥ 0,

bn = (−3), n ≥ 1,

a więc Tn =

n X

cn =

(

0, n = 0, n + 1, n ≥ 1,

(k + 1)(−3)n−k ,

k=1

a ponieważ

Tn+1 = −3Tn + n + 2 n

Tn+1 = 2(−3) + = 2(−3)n +

n+1 X

(k + 1)(−3)n+1−k

k=2 n X

(k + 2)(−3)n−k

k=1

= 2(−3)n + Tn +

(−3)n − 1 , −4

sn =

1 , n ≥ 1, (−3)n

162

Rozwiązania zatem −3Tn + n + 2 = 2(−3)n + Tn +

−(−3)n + 1 , 4

czyli Tn =

n + 2 7(−3)n + 1 − , n ≥ 1. 4 16

3.25. Zwróćmy uwagę, że △(k2k ) = △(k)2k + (k + 1)△(2k ) = (k + 2)2k ,

△2 (k2k ) = △((k + 2)2k ) = (k + 4)2k ,

△n (k2k ) = (k + 2n)2k , n ≥ 0. Z kolei

△0 (Hk ) = Hk , 1 = k−1 , △(Hk ) = k+1 △2 (Hk ) = △(k−1 ) = −1k−2 ,

△n (Hk ) = (−1)n−1 (n − 1)!k−n , n ≥ 1, oraz △(k3 + 5k1 ) = 3k2 + 5,

△2 (k3 + 5k1 ) = 3!k1 , △3 (k3 + 5k1 ) = 3!,

△n (k3 + 5k1 ) = 0, n ≥ 4. 3.26. Ponieważ △(k2 ) = △(k2 + k1 ) = 2k + 1 oraz △(2k ) = 2k więc zachodzi: △(

k2 2k ) = Hk + k = = =

(△(k2 2k ))(Hk + k) − k2 2k △(Hk + k) (Hk + k)(Hk+1 + k + 1) 1 2 k (k 2 + (2k + 1)2k+1 )(Hk + k) − k2 2k ( k+1 + 1) (Hk + k)(Hk+1 + k + 1) 2 (k + 4k + 2)(k + 1)2k (Hk + k) − k2 (k + 2)2k (Hk + k)(Hk+1 + k + 1) 2 ((k + 4k + 2)(k + 1)(Hk + k) − k2 (k + 2))2k , (Hk + k)(Hk+1 + k + 1)

163

Rozwiązania oraz △(kHk 3k ) = k△(Hk 3k ) + (△(k))Hk+1 3k+1

= k(Hk △(3k ) + △(Hk )3k+1 ) + (△(k))Hk+1 3k+1 k3k+1 = 2kHk 3k + + Hk+1 3k+1 k+1

i !

k+n (k + n)n ) △( ) = △( n! k = =

n(k + n)n−1 ) n!! k+n . k+1

3.27. Ponieważ, traktując n jako parametr 1 1 1 1 1 1 = − ( − )= , − △ 2 2k − 1 2 2k + 1 2k − 1 (2k − 1)(2k + 1) 1 1 1 1 1 1 = − ( − )= , − △ 3 3k − 2 3 3k + 1 3k − 2 (3k − 2)(3k + 1) 1 1 = , −△ n+k (n + k)(n + k + 1) 1 1 1 △ = , 2 n − 2k + 2 (n − 2k)(n − 2k + 2)

więc

n X

1 (2k − 1)(2k + 1) k=1

= = =

n X

1 (3k − 2)(3k + 1) k=1

= = =

n 1 −1 X △ 2 k=1 2k − 1

1 1 −1 ( − ) 2 2n + 1 2 − 1 1 1 (1 − ), n ≥ 1, 2 2n + 1 n 1 −1 X △ 3 k=1 3k − 2

1 1 −1 ( − ) 3 3n + 1 3 − 2 1 1 (1 − ), n ≥ 1, 3 3n + 1

164

Rozwiązania n−1 X

1 (n + k)(n + k + 1) k=0

= − = =

n−1 X k=0

△

1 n+k

1 1 − n 2n 1 , n ≥ 1. 2n

Ostatnia suma dla parzystych n nie istnieje (bo pojawia się człon 10 ) natomiast dla n nieparzystych n−1 X

1 (n − 2k)(n − 2k + 2) k=0

=

X 1 1 n−1 △ 2 k=0 n − 2k + 2

1 1 1 (− − ) 2 n−2 n+2 n , n ≥ 1. = − 2 n −4 =

3.28. Ponieważ k + k2 + 1 k(k + 3) − 2k + 1 = (k + 1)(k + 2)(k + 3) (k + 1)(k + 2)(k + 3) 2(k + 3) − 7 k − = (k + 1)(k + 2) (k + 1)(k + 2)(k + 3) k+2 2 2 7 = − − + (k + 1)(k + 2) (k + 1)(k + 2) (k + 1)(k + 2) (k + 1)(k + 2)(k + 3) = k−1 − 4k−2 + 7k−3 więc k3 = k3 + 3k2 + k1 , −3k = −3k1 ,

k + k2 + 1 (k + 1)(k + 2)(k + 3)

= k−1 − 4k−2 + 7k−3 .

Zatem n−1 X k=0

(k3 − 3k −

=

n−1 X k=0

k + k2 + 1 ) (k + 1)(k + 2)(k + 3)

(k3 + 3k2 − 2k1 + k−1 − 4k−2 + 7k−3 )

165

Rozwiązania 1 4n 4 −1 n 7 −2 n k |0 + k3 |n0 − k2 |n0 + Hn − k |0 + k |0 4 −1 −2 n4 7 7 = + n3 − n2 + Hn + 4n−1 − 4 − n−2 + 4 2 4 n(n − 1)(n − 2)(n − 3) + n(n − 1)(n − 2) − n(n − 1) + Hn = 4 4 7 1 − . −2 + 4 n + 1 2(n + 1)(n + 2) =

3.29. Ponieważ k2 − 5 (k + 1)(k + 2)(k + 3)

k(k + 3) − 3k − 5 (k + 1)(k + 2)(k + 3) 3(k + 3) k+2−2 − = (k + 1)(k + 2) (k + 1)(k + 2)(k + 3) 4 + (k + 1)(k + 2)(k + 3) −1 = k − 5k−2 + 4k−3 , =

k2 = k2 + k1 , k = k1 , więc n−1 X k=0

(k2 + 2k −

= =

n−1 X k2 − 5 )= k2 + 3k1 − k−1 + 5k−2 − 4k−3 (k + 1)(k + 2)(k + 3) k=0

1 3n 3 2n 5 −1 n 4 −2 n k |0 + k |0 − Hn + k |0 − k |0 3 2 −1 −2 n(n − 1)(n − 2) 3n(n − 1) 5 2 + − Hn − +4+ . 3 2 n+1 (n + 1)(n + 2)

Pozostaje tylko obliczyć przez części mamy n−1 X k=0

Pn−1

k2 2k =

k=0

n−1 X k=0

k2 2k i

Pn−1

k k=0 (−1) . n−1 X

k2 △(2k ) +

= k2 2k |n0 − 2

n−1 X

k=0

Za wzoru ma różnicowanie

k1 △(2k )

k1 2k+1 +

k=0

= n(n − 1)2n − 3

n−1 X k=0

n−1 X k=0

k1 △(2k )

k1 △(2k )

= n(n − 1)2n − 3(k1 2k |n0 −

n−1 X k=0

2k+1 )

166

Rozwiązania = n(n − 1)2n − 3n2n + 6 = (n(n − 4) + 6)2n − 6, oraz

n−1 X

1 + (−1)n = (−1) = 2 k=0 k

(

n−1 X k=0

△(2k )

1, n parzyste, 0, n nieparzyste.

3.30. Mamy Zn =

n X

Hk =

k=1

n X

△(k)Hk

k=1 n X

= kHk |n+1 − 1

(k + 1)△(Hk )

k=1

= (n + 1)Hn+1 − n − 1, czyli Zn = (n + 1)(Hn+1 − 1), n ≥ 1.

Podobnie Un =

n X

kHk =

k=1

= =

n 1X △(k2 )Hk 2 k=1

n 1X 1 (k + 1)k△(Hk ) k(k − 1)Hk |n+1 − 1 2 2 k=1

(n + 1)nHn+1 (n + 1)n − , 2 4

a więc Un =

n(n + 1)(2Hn+1 − 1) , n ≥ 1, 4

i wreszcie Tn =

n X

k=1

= = =

k 2 Hk =

n X

k=1

k 2 H k + Un =

n 1X △(k3 )Hk + Un 3 k=1

n 1 3 1 1X (k + 1)3 k Hk |n+1 + Un − 1 3 3 k=1 k+1

1 1 (n + 1)n(n − 1)Hn+1 − (n + 1)3 + Un 3 9 (n + 1)n(n − 1)(3Hn+1 − 1) + Un 9

167

Rozwiązania a więc Tn =

(n + 1)n(n − 1)(3Hn+1 − 1) n(n + 1)(2Hn+1 − 1) + , n ≥ 1, 9 4

a po uporządkowaniu Tn =

n(n + 1)(2n + 1)Hn+1 n(n + 1)(4n + 5) − , n ≥ 1. 6 36

3.31. Ponieważ k3 + 4k2 − k − 4 = (k + 4)(k − 1)(k + 1), więc k2 − k k3 + 4k2 − k − 4

= = = = = =

=

=

k(k − 1) k = (k − 1)(k + 1)(k + 4) (k + 1)(k + 4) k(k + 2)(k + 3) k3 + 5k2 + 6k = (k + 1)(k + 2)(k + 3)(k + 4) (k + 1)(k + 2)(k + 3)(k + 4) 2 2 k (k + 4) + k + 6k (k + 1)(k + 2)(k + 3)(k + 4) k2 k2 + 6k + (k + 1)(k + 2)(k + 3) (k + 1)(k + 2)(k + 3)(k + 4) k(k + 4) + 2k k(k + 3) − 3k + (k + 1)(k + 2)(k + 3) (k + 1)(k + 2)(k + 3)(k + 4) k k −3 (k + 1)(k + 2) (k + 1)(k + 2)(k + 3) 2k k + + (k + 1)(k + 2)(k + 3) (k + 1)(k + 2)(k + 3)(k + 4) k+2−2 k+3−3 −3 (k + 1)(k + 2) (k + 1)(k + 2)(k + 3) 2(k + 4) − 8 k+3−3 + + (k + 1)(k + 2)(k + 3) (k + 1)(k + 2)(k + 3)(k + 4) k−1 − 2k−2 − 3k−2 + 9k−3 + k−2 − 3k−3 + 2k−3 − 8k−4

= k−1 − 4k−2 + 8k−3 − 8k−4 , oraz

3k3 + 2k2 = 3k3 + 11k2 + 5k1 . Zatem Sn =

n−1 X k=0

(3k3 + 11k2 + 5k1 + k−1 − 4k−2 + 8k−3 − 8k−4 )

168

Rozwiązania 3 4 n 11 3 n 5 2 n 4 −1 n 8 −2 n 8 −3 n k |0 + k |0 + k |0 + Hn − k |0 + k |0 − k |0 4 3 2 −1 −2 −3 3n(n − 1)(n − 2)(n − 3) 11n(n − 1)(n − 2) 5n(n − 1) = + + + Hn 4 3 2 4 4 8 4 + −4− +2+ − n+1 (n + 1)(n + 2) 3(n + 1)(n + 2)(n + 3) 9 3n(n − 1)(n − 2)(n − 3) 11n(n − 1)(n − 2) 5n(n − 1) + + + Hn = 4 3 2 4 4 8 4 + − + −2 . n + 1 (n + 1)(n + 2) 3(n + 1)(n + 2)(n + 3) 9

=

3.32. Uwzględniając k2 + 1 k2 + 4k + 3

= = = = =

k2 + 1 k3 + 2k2 + k + 2 = (k + 1)(k + 3) (k + 1)(k + 2)(k + 3) 2 k (k + 3) − k(k + 3) + 4(k + 3) − 10 (k + 1)(k + 2)(k + 3) k+2−2 k(k + 2) −3 + 4k−2 − 10k−3 (k + 1)(k + 2) (k + 1)(k + 2) k+1−1 − 3k−1 + 10k−2 − 10k−3 k+1 k0 − 4k−1 + 10k−2 − 10k−3

otrzymujemy Sn =

n−1 X k=0

= =

(k1 + k0 − 4k−1 + 10k−2 − 10k−3 )

1 2n 10 −1 n 10 −2 n k |0 + k1 |n0 − 4Hn + k |0 − k |0 2 −1 −2 n(n − 1) 10 1 5 + n − 4Hn − +7 + . 2 n+1 2 (n + 1)(n + 2)

3.33. Oznaczając przez S =

n X n X

(aj bk − ak bj )2 ,

j=1 k=1

S△ = S∇ = S =

X

(aj bk − ak bj )2 ,

1≤j