1. Indukcja matematyczna

Z. 1. Udowodnić, że dla n ­ 2 każda liczba postaci 2

2

n

ma zawsze cyfrę jedności równą 6.

Z. 2. Definiujemy n-tą liczbę harmoniczną następująco: H

n

=

1
1

+

1
2

+ · · · +

1

n

(przyjmujemy H

0

= 0).

Udowodnić, że

n+1

2

¬ H

2

n

¬ n + 1.

Z. 3. Pokazać indukcyjnie, że każdy n elementowy zbiór S posiada 2

n

podzbiorów (łącznie ze zbiorem

pustym i zbiorem S).

Z. 4. Wyznaczyć liczbę odcinków łączących n punktów na płaszczyźnie, z których żadne trzy nie są
współliniowe.

Z. 5. Udowodnić indukcyjnie, że każdą szachownicę wymiaru 2

n

× 2

n

, n ­ 1 z „dziurą” (tzn. jednym

polem usuniętym) można pokryć klockami w kształcie litery L (trzy kwadraty jednostkowe). Zakładamy,
że kwadraty nie mogą na siebie zachodzić.

Z. 6. (autor: George Pólya - matematyk węgierski)
Znaleźć błąd w rozumowaniu:
TW. Wszystkie konie są jednej maści.
DOWÓD:
Sprawdzamy pierwszy krok indukcyjny - zbiór złożony z jednego konia jest zbiorem koni jednej maści.
Zakładamy teraz, że (dla ustalonego n) wszystkie konie w każdym zbiorze n-elementowym koni są jednej
maści. Pokażemy, że w takim razie teza zachodzi także dla wszystkich zbiorów (n + 1)-elementowych
koni.
Dodajmy do dowolnego n-elementowego zbioru nowego konia. Mamy zbiór (n + 1)-elementowy. Teraz
odprowadźmy z tego zbioru któregoś konia, ale nie tego, którego właśnie dodaliśmy. Otrzymujemy więc
zbiór n-elementowy koni. Z założenia indukcyjnego wszystkie konie w tym zbiorze są jednej maści.
W takim razie nowododany koń jest tej samej maści, co pozostałe. Teraz możemy z powrotem przy-
prowadzić konia usuniętego z naszego zbioru (który jest oczywiście tej samej maści, co pozostałe) i
otrzymujemy zbiór (n + 1)-elementowy koni jednej maści.
A więc wszystkie konie są jednej maści.

Z. 7. Udowodnić, że suma kątów wewnętrznych w n-kącie wypukłym wynosi (n − 2)π.

Z. 8. Na płaszczyźnie poprowadzono n prostych, z których żadne dwie nie są równoległe i żadne trzy
nie przechodzą przez ten sam punkt. Wyznaczyć liczbę części, na które te n prosych dzieli płaszczyznę.

Z. 9. Udowodnić, że wśród obszarów na jakie dzieli płaszczyznę n prostych jest co najwyżej

(n−1)(n−2)

2

obszarów ograniczonych.

Z. 10. Połączono n punktów strzałkami w taki sposób, że każda para różnych punktów jest połączona
strzałką. Udowodnić, że istnieje „centrum”, czyli punkt, z którego można dojść do każdego innego w
co najwyżej dwóch krokach, idąc zgodnie z kierunkiem strzałek.

Z. 11. Uczniowie i uczennice pewnej klasy postanowili z okazji walentynek obdarować się prezentami.
Każdy miał wybrać dokładnie jedną osobę, której kupi skromny upominek. Okazało się, że wszyscy
dostali jakiś prezent. Pokaż, że każdy dostał prezent wyłącznie od jednej osoby.

Z. 12. Niech A ⊆ N będzie zbiorem wszystkich tych liczb naturalnych n , dla których liczba n

2

− 3n + 3

jest parzysta. Pokaż, że jeśli n ∈ A to i n + 1 ∈ A. Jakie liczby należą więc do A?

Z. 13. Ostatnią cyfrą liczby 3

3

n

jest:

(1) zawsze 3
(2) zawsze 3 lub 7
(3) zawsze 7
(4) jakakolwiek z cyfr 0,1,2,3,4,5,6,7,8,9

Z. 14. Grupa uczniów stojących przed klasą skłóciła się do tego stopnia, że nikt z nikim się nie lubił.
Jeden z nich, aby naprawić relacje, wymyślił, że jeżeli wszyscy znajdujący się wewnątrz klasy będą
pogodzeni, to nie powinno być problemu, aby któryś stojący na zewnątrz klasy wszedł do środka i
pogodził się ze wszystkimi, będącymi w klasie. Drugi z nich zauważył jednak, że nic z tego nie wyjdzie,
bo w środku nikogo nie ma. Czy klasa jest w stanie się pogodzić?

(1) grupa na pewno się nie pogodzi
(2) grupa się pogodzi, jeżeli każdy pójdzie za radą pierwszego ucznia

1

2

(3) jeżeli w klasie byłaby już jedna osoba, to reszta grupy miałaby szansę się pogodzić
(4) jeżeli w klasie byłyby już co najmniej dwie osoby, przy czym osoby w klasie byłyby ze sobą

pogodzone, to reszta grupy miałaby szansę się pogodzić

Z. 15. Udowodnić indukcyjnie, że każdą kwotę n ­ 4 zł można rozmienić na dwuzłotówki i pięciozło-
tówki.

Z. 16. Jakie opłaty skarbowe możemy uiścić mając tylko znaczki skarbowe o nominałach 3 zł i 5 zł
(znaczków mamy dowolnie dużo). Odpowiedź poprzeć argumentem indukcyjnym.

Z. 17. Czekolada jest prostokątem złożonym z jednostkowych kwadracików. Zakładamy, że możemy
je łamać wzdłuż poziomych lub pionowych rowków, podobnie powstałe z przełamania kawałki (które
też są prostokątami). Zakładamy, że w jednym ruchu dokonujemy jednego łamania tylko jednego z
kawałków czekolady. Ilu ruchów potrzebujemy, aby podzielić czekoladę na kwadraciki jednostkowe?
Trenując na prawdziwej czekoladzie, dojść do odpowiedzi, a otrzymany wynik udowodnić indukcyjnie.

Z. 18. * Oto prosta wersja gry NIM. Jest stos n monet i 2 graczy. Kolejno zabierają ze stosu monety. W
każdym ruchu można zabrać 1, 2 lub 3 monety. Przegrywa ten, kto zabierze ostatnią monetę (ostatnie
monety). Dla jakich n grę wygrywa gracz pierwszy, a dla jakich drugi? „Wygrywa grę” oznacza, że
gracz ma strategię gwarantującą wygraną, nawet przy bardzo dobrej grze przeciwnika.
Uwaga: w bardziej skomplikowanych wersjach tej gry stosów jest kilka.

Z. 19. Oto rekurencyjna definicja pewnego zbioru S.
1) ∅ ∈ S, {1} ∈ S, {2} ∈ S, {3} ∈ S.
2) Jeżli A ∈ S i B ∈ S, to A ∪ B ∈ S.
Jaki to zbiór ? Proszę wypisać wszystkie jego elementy.

Z. 20. Podać definicję indukcyjną zbioru A

13

wszystkich liczb naturalnych podzielnych przez 13.

Następnie udowodnić poprawność tej definicji, tzn.
a) pokazać indukcją strukturalną, że wszystkie elementy Państwa zbioru są podzielne przez 13,
b) pokazać indukcyjnie, że każda liczba podzielna przez 13 należy do Państwa zbioru.

Z. 21. Podać definicję indukcyjną zbioru liczb niepodzielnych przez 13.

Z. 22. Oto definicja indukcyjna pewnego zbioru liczbowego A:
1) 9 ∈ A, 6 ∈ A.
2) Jeśli x ∈ A i y ∈ A, to x + y ∈ A.
Udowodnić, stosując indukcję strukturalną, że każdy element A jest wielokrotnością 3.

Z. 23. Palindrom, to ciąg, który czytany w obu kierunkach wygląda tak samo. Chcemy zdefiniować
zbiór P ciągów binarnych (złożonych tylko z zer i jedynek), które są palindromami. Czy poniższa
definicja jest poprawna ? Jeżeli nie – popraw ją.
1) (0) ∈ P, (1) ∈ P .
2) Jeżeli a ∈ P , to (0a0) ∈ P i (1a1) ∈ P .
(0a0) oznacza ciąg a z doklejonymi zerami, analogicznie (1a1).

Z. 24. Chcemy zdefiniować rekurencyjnie zbiór A wszystkich punktów kratowych płaszczyzny (tzn.
punktów o współrzędnych całkowitych), dla których przynajmniej jedna współrzędna jest parzysta.
Czy poniższa definicja jest poprawna ? Jeżeli nie – podaj poprawną.
1) (0, 0), (0, 1), (1, 0) ∈ A.
2) Jeżeli (x, y) ∈ A, to (x + 2, y + 2) ∈ A i (x − 2, y − 2) ∈ A.

Z. 25. Oto indukcyjna definicja ścieżki:
1) pojedynczy punkt (nieleżący na innej ścieżce) jest ścieżką (P

0

);

2) jeżeli P

1

i P

2

są ścieżkami, to ścieżkę P = P

1

P

2

otrzymujemy przez dodanie jednego odcinka łączącego

punkty końcowe różnych ścieżek. (Punkt końcowy ścieżki, to taki punkt, z którego nie wychodzi więcej
niż jeden odcinek.)
Długością ścieżki d(P ) nazywamy liczbę jej odcinków. Udowodnić za pomocą indukcji strukturalnej,
że d(P ) = n − 1, gdzie n jest liczbą punktów na ścieżce.

Z. 26. Oto indukcyjna definicja pewnego zbioru wielomianów W :
1) w

0

(x) = x

2

∈ W i w

0

0

(x) = −x

2

∈ W ;

2) jeżeli w

1

(x) ∈ W i w

2

(x) ∈ W , to p

1

(x) = w

1

(x) (w

2

(x))

3

∈ W oraz p

2

(x) = (w

1

(x))

3

w

2

(x) ∈ W .

Niech s(w) oznacza stopień wielomianu w(x). Udowodnić za pomocą indukcji strukturalnej, że s(w)
jest liczbą parzystą dla każdego wielomianu w ∈ W .