mat05_zeszyt_cwiczen_dla_ucznia.doc

Zeszyt ćwiczeń

LICZBY WOKÓŁ NAS

dr Barbara Roszkowska-Lech

LICZBY FIBONACCIEGO

Ciąg Fibonaciego

f1 = f2 = 1, fn = fn-1 + fn-2,  dla  n >2,

1.     Na ile sposobów można ułożyć mozaikę na chodniku długości  1xn, gdy mamy  do dyspozycji  płytki  kwadratowe 1x1 oraz  prostokątne 1x2 (patrz rysunek)

Rozwiązanie.  Oczywiste jest, że jeśli nasz chodnik ma długość 1, to mamy tylko jedną możliwość. (używamy płytki 1x1), a jeśli nasz chodnik ma długość  2, to mamy  2 możliwości: możemy użyć dwóch płytek 1x1 (1 sposób) lub jednej płytki 1x2.   Oznaczmy liczbę możliwych ułożeń chodnika długości n przez Cn.  Mamy  C1=1,  C2=2.     Załóżmy, że mamy  chodnik długości n >2. Zobaczmy jaka jest ostatnia płytka. Mamy dwie możliwości: jeśli jest to płytka 1x1, to możliwych ułożeń jest Cn-1, a jeśli płytka 1x2 to takich ułożeń jest Cn-2. Zatem chodnik długości n można ułożyć na Cn = Cn-1 + Cn-2.  (Porównajmy ciąg Cnz ciągiem Fibonacciegofn.  Widać, że dla n>1, Cn =  fn+1).

2.     Udowodnić, że  fn+3 = 1 + f1 +f2+ …. + fn + fn+1 dla  n>0.

Rozwiązanie Z poprzedniego zadania wynika, że liczba fn+1 jest liczba możliwych ułożeń chodnika 1xn z płytek kwadratowych i prostokątnych. Zatem fn+3 to  liczba możliwych ułożeń chodnika długości n+2.  Wśród tych ułożeń jest tylko jedno składające się z samych kwadratów.  W każdym innym ułożeniu jest co najmniej jeden prostokąt 1x2.  Jeśli taki prostokąt jest ostatnią płytką na naszym chodniku to takich ułożeń jest tyle ile wynosi Cn, czyli fn+1.  Wybierzmy prostokąt, który znajduje się na naszym chodniku długości n+2  najbardziej na prawo (to znaczy na lewo od niego są tylko kwadraty) i policzmy ile jest możliwych ułożeń naszego chodnika. Za każdym razem liczba ta jest równa liczbie możliwych ułożeń chodnika z płytek leżących na lewo od naszego prostokąta. Sumujemy teraz wszystkie możliwe liczby ułożeń i dostaniemy nasz wzór.

3.     Udowodnić że  fn+k = fkfn+1 + fk-1fn  dla n>0 i k>1.

Rozwiązanie. Znowu przyjrzyjmy się naszemu chodnikowi. Liczba fn+k to liczba sposobów ułożenia chodnika długości n+k-1.  Podzielmy nasz chodnik w na długości n.  możliwe są dwa przypadki:

·         Linia podziału nie przebiega przez prostokąt. Wtedy po lewej stronie linii podziału mamy  chodnik długości n, a po prawej długości k-1. Takich możliwych ułożeń jest fkfn+1

·         Linia podziału przebiega przez kostkę prostokątną. Wtedy po lewej stronie linii podziału mamy chodnik długości n-1, a po prawej długości k-2. Takich możliwych ułożeń jest fk-1fn.

Suma liczb uzyskanych w obu przypadkach jest równa fn+k.

PODZIELNOŚĆ

4.     Wykazać, że dla dowolnej liczby naturalnej n,  liczba    jest liczbą naturalną.

Rozwiązanie.  Liczba jest liczbą naturalną  wtedy tylko wtedy gdy   12 dzieli  (3n+1)(n3 -3n2 +2n).  Oznaczmy Ln = (3n+1)(n3 -3n2 +2n).  Zauważmy, że Ln = (3n+1)n(n-1)(n-2). Zauważmy ponadto, że  liczba n(n-1)(n-2) jako iloczyn trzech kolejnych liczb naturalnych jest zawsze podzielna przez 6. Ponadto, jeśli n jest liczbą parzystą to liczba ta jest  podzielna przez 4, a więc Ln jest podzielna  przez 12. Załóżmy więc, że  n jest liczbą nieparzystą. Wtedy liczba 3n+1  jest parzysta a więc  znowu Ln jest podzielna przez 12.

5.     Niech n będzie liczba całkowitą większą od 1. Udowodnij, że

a.     2n jest sumą dwóch kolejnych liczb nieparzystych,

b.     3n  jest suma trzech kolejnych liczb całkowitych.

Wskazówki a) Dwie kolejne liczby nieparzyste są postaci 2k -1 oraz 2k +1, dla dowolnego k.. Załóż, że  2n = (2k-1) + (2k+1) i oblicz k. Zawsze daje się obliczyć!

b) Podobnie, trzy kolejne liczby całkowite to k-1, k, k+1, dla dowolnego k.  Oblicz k, jeśli    3n = (k-1) +k  + (k-1).

6.     Niech k będzie liczba parzystą. Czy możliwe jest przedstawienie 1 jedynki za pomocą sumy odwrotności k nieparzystych liczb całkowitych?

Rozwiązanie. Pytamy, czy istnieje k  nieparzystych liczb naturalnych n1, n2, …,nk  takich, że .  Załóżmy, że takie liczby istnieją.  Oznacza to, że     gdzie  wszystkie liczby   są  nieparzyste. Jest ich parzyście wiele (k), a więc ta suma jest parzysta. Lewa strona tej równości jest liczbą nieparzystą. Otrzymana sprzeczność dowodzi, że  nie można przedstawić jedynki w żądany sposób.

7.     Jaś wybrał pięć liczb ze zbioru {1,2,3,4,5,6,7}, obliczył ich iloczyn i podał Zosi. Zosia chciała wiedzieć, czy suma wybranych liczb jest parzysta czy nie.  Okazało się, że znajomość iloczynu nie wystarczyła do rozstrzygnięcia tego problemu. Jaki jest iloczyn pięciu wybranych przez Jasia liczb?

Rozwiązanie. Zauważ, że znajomość iloczynu pięciu wybranych liczb jest równoważna  ze znajomością iloczynu dwóch pozostałych liczb. Jakie liczby można przedstawić na więcej niż jeden sposób jako iloczyn liczb z naszego zbioru?  Są dwie takie liczby 12 = , oraz . W drugim  przypadku suma dwóch niewybranych liczb jest nieparzysta, a więc suma wybranych jest również nieparzysta. Zatem  zachodzi  pierwszy przypadek, czyli zatem iloczyn pięciu wybranych liczb jest równy

8.     Smok ma 1000 głów. Rycerz może jednym cieciem obciąć 21 lub 33 lub 14 lub 1 głowę. Smokowi odrasta natychmiast odpowiednio 51, 0 , 11 lub 103 głowy. Smok zostaje zabity gdy wszystkie głowy zostają ścięte. Czy rycerz może zabić smoka?

Rozwiązanie Nie. Po każdej akcji rycerza liczba głów smoka nie zmienia reszty z dzielenia przez 3. (Sprawdź sam) Rycerzowi udało by się zabić smoka, gdyby  reszta z dzielenia przez 3 liczby 1000 była równa 0. A tak nie jest.

9.     Udowodnić ,  że liczba n= 10a+b jest podzielna przez 7 wtedy i tylko wtedy liczba a -2b jest podzielna przez 7.  Stosując udowodnioną własność sprawdzić, czy liczba 648186 jest podzielna przez 7.

Rozwiązanie Zauważmy, że liczba  (10a +b) + 4(a-2b) = 14a -7b jest zawsze podzielna przez 7.  Jeśli oznaczymy m= a-2b to zawsze  liczba k = n+4m jest liczbą podzielną przez 7. Jeśli teraz 7 dzieli m to 7 dzieli n=k-4m. Podobnie  jeśli 7 dzieli n to dzieli też 4m = k-n, a ponieważ 4 i 7 są względnie pierwsze to 7 dzieli m. Aby sprawdzić podzielność przez 7  liczby  648186 obliczamy:  64818 -26 = 64806, 6480- 2   646 -2 = 630. Liczba  630 = 790, a więc  648186 jest również podzielna przez 7.

LICZBY PIERWSZE

10. *Udowodnić, że jest nieskończenie wiele liczb pierwszych postaci 4k-1, czyli dających resztę 3 z dzielenia przez 4.

Rozwiązanie (szkic). Zauważmy, że taka liczba pierwsza istnieje (3 jest taką liczbą) Spróbujmy powtórzyć  z lekką modyfikacją rozumowanie Euklidesa. Przypuśćmy, że A ={p1, p2, …,pk} będą wszystkimi liczbami pierwszymi dającymi resztę 3 z dzielenia przez 4. Niech M = 4p1p2…pk-1. Liczba M daje resztę 3  z dzielenia przez 4 i liczba ta ma jakiś dzielnik pierwszy. Dowolna liczba pierwsza daje resztę 1 lub 3  z dzielenia przez 4 (Dlaczego?). Gdyby wszystkie pierwsze dzielniki  liczby M miały resztę 1 z dzielenia przez 4 to liczba M również dałaby przy dzieleniu przez 4 resztę 1. (Dlaczego?) Wniosek: liczba M ma dzielnik pierwszy p, który przy dzieleniu przez 4 daje resztę 3. Ale liczba p nie należy do zbioru A, bo żadna z liczb ze zbioru A nie dzieli liczby M. Otrzymana sprzeczność dowodzi, że jest nieskończenie wiele liczb pierwszych postaci 4k-1.

Projekt współfinansowany z Europejskiego Funduszu Społecznego w ramach Programu Operacyjnego Kapitał Ludzki

4