Rekurencja
KANGUR Online
na lekcjach
Strona tytułowa
matematyki
Andrzej Sendlewski
Wydział Matematyki i Informatyki UMK w Toruniu
Poprzedni slaid
Konferencja Wiosenna Organizatorów
Pełny ekran
Konkursu  Kangur Matematyczny
Zamknij plik
Toruń 2010
Koniec pokazu
KANGUR Online
Strona tytułowa
c& Liczby figuralne jako
jeden z najprostszych
sposobów wprowadzenia w
Poprzedni slaid
myślenie rekurencyjne
Pełny ekran
Zamknij plik
Koniec pokazu
PROBLEM 1. Rysujemy kolejne kwadraty
o bokach długości całkowitej i dzielimy je na
kwadraty jednostkowe.
KANGUR Online
Strona tytułowa
Poprzedni slaid
1 2 3 4
Z ilu kwadratów jednostkowych składa się
Pełny ekran
kwadrat o boku długości n?
Zamknij plik
Ile jest wszystkich kwadratów na n-tym ry-
sunku?
Koniec pokazu
KANGUR Online
Strona tytułowa
Poprzedni slaid
3 4
Pełny ekran
ńł
�ł
�ł
�ł
�ł
�ł 1, jeżeli n = 1;
k(n) =
�ł
�ł
�ł
Zamknij plik
�ł
ół k(n - 1) + 2n - 1, jeżeli n > 0.
Koniec pokazu
KANGUR Online
Strona tytułowa
2 3 4
Poprzedni slaid
ńł
�ł
�ł
�ł
�ł
�ł 1, jeżeli n = 1;
�ł
�ł
�ł
�ł
�ł
Pełny ekran
k(n) = 4, jeżeli n = 2;
�ł
�ł
�ł
�ł
�ł
�ł
�ł
�ł
�ł
ół k(n - 2) + 4n - 4, jeżeli n > 0.
Zamknij plik
Koniec pokazu
PROBLEM 2. Rysujemy kolejne trójkąty
o bokach długości całkowitej i dzielimy je na
przystające trójkąty o boku 1.
KANGUR Online
Strona tytułowa
Poprzedni slaid
2 3 4
1
Z ilu małych trójkątów składa się trójkąt
Pełny ekran
o boku długości n?
Zamknij plik
Ile jest wszystkich trójkątów równobocz-
nych na n-tym rysunku?
Koniec pokazu
KANGUR Online
Strona tytułowa
3 4
Poprzedni slaid
ńł
�ł Pełny ekran
�ł
�ł
�ł
�ł 1, jeżeli n = 1;
k(n) =
�ł
�ł
�ł
�ł
ół k(n - 1) + n + (n - 1), jeżeli n > 0.
Zamknij plik
Koniec pokazu
PROBLEM 3. Z jednakowych monet ukła-
KANGUR Online
damy kolejne  trójkąty równoboczne , tak
jak na rysunku.
Strona tytułowa
Poprzedni slaid
1 2 3 4
Pełny ekran
Jaka jest wartość monet tworzących n ty
trójkąt?
Zamknij plik
Koniec pokazu
KANGUR Online
Strona tytułowa
Poprzedni slaid
3 4
Pełny ekran
ńł
�ł
�ł
�ł
�ł
�ł 1, jeżeli n = 1;
Zamknij plik
t(n) =
�ł
�ł
�ł
�ł
ół t(n - 1) + n, jeżeli n > 1.
Koniec pokazu
KANGUR Online
1 2 3 4
Strona tytułowa
Poprzedni slaid
Pełny ekran
1 2 3 4
Zamknij plik
k(n) = t(n) + t(n - 1)
Koniec pokazu
KANGUR Online
Strona tytułowa
1 2 3 4
Z równości
Poprzedni slaid
(n + 1)2 = k(n + 1) = 2t(n) + (n + 1)
mamy
Pełny ekran
n(n + 1)
t(n) =
Zamknij plik
2
Koniec pokazu
PROBLEM 4. Z jednakowych sześcien-
KANGUR Online
nych klocków budujemy kolejne piramidy
trójkątne, jak na rysunku.
Strona tytułowa
Poprzedni slaid
1
2
3
4
Pełny ekran
Z ilu sześciennych klocków zbudowana jest
n ta piramida trójkątna?
Zamknij plik
Koniec pokazu
KANGUR Online
Strona tytułowa
4
3
Poprzedni slaid
Żółta ściana zbudowana jest z t(n) sześcien-
nych klocków, a więc
Pełny ekran
ńł
�ł
�ł
�ł
�ł
1, jeżeli n = 1;
�ł
�ł
�ł
Zamknij plik
�ł
pt(n) =
n(n + 1)
�ł
�ł
�ł
�ł
�ł
�ł pt(n - 1) + , jeżeli n > 1.
�ł
ół
2
Koniec pokazu
PROBLEM 5. Z jednakowych sześcien-
nych klocków budujemy kolejne piramidy
KANGUR Online
 kwadratowe , jak na rysunku
Strona tytułowa
Poprzedni slaid
1
2
3
4
Pełny ekran
Z ilu sześciennych klocków zbudowana jest
n ta piramida?
Zamknij plik
Koniec pokazu
KANGUR Online
Strona tytułowa
3
4
Poprzedni slaid
Żółta podstawa zbudowana jest z k(n) sze-
Pełny ekran
ściennych klocków, a więc
ńł
�ł
�ł
�ł
�ł Zamknij plik
1, jeżeli n = 1;
�ł
p(n) =
�ł
�ł
�ł
�ł
ół
p(n - 1) + n2, jeżeli n > 1.
Koniec pokazu
f& Co wspólnego z ciągiem
KANGUR Online
Fibonacci ego ma:
Strona tytułowa
bieganie po schodach,
układanie kafelków,
Poprzedni slaid
gra w koszykówkę,
Pełny ekran
liczenie kodów kreskowych?
Zamknij plik
Koniec pokazu
PROBLEM 6. Na taras wieży widokowej
prowadzą schody o n stopniach.
KANGUR Online
n
n-1
Strona tytułowa
n-2
3
2
Poprzedni slaid
1
0
Pełny ekran
Turysta wchodzi na taras wykonując lo-
sowo kroki co 1 albo co 2 stopnie. Na ile spo-
Zamknij plik
sobów turysta może przejść schody?
Koniec pokazu
n
KANGUR Online
n-1
n-2
Strona tytułowa
3
2
1
Poprzedni slaid
0
ńł
�ł Pełny ekran
�ł
�ł
�ł
�ł 1, jeżeli n = 1;
�ł
�ł
�ł
�ł
�ł
s(n) = 2, jeżeli n = 2;
�ł
�ł
�ł
Zamknij plik
�ł
�ł
�ł
�ł
�ł
�ł
ół s(n - 2) + s(n - 1), jeżeli n > 2.
Koniec pokazu
KANGUR Online
Strona tytułowa
PROBLEM 7. Mamy pokryć prostokątny
pas podłogi o wymiarach n�2 prostokątnymi
kafelkami o wymiarach 2 � 1. (kafelków nie
wolno łamać.) Na ile sposobów możemy to
zrobić?
Poprzedni slaid
Pełny ekran
Zamknij plik
Koniec pokazu
1 2 2
KANGUR Online
Strona tytułowa
3 3
3
Poprzedni slaid
n-1 1 n-2 2
ńł
�ł
�ł Pełny ekran
�ł
�ł
�ł 1, jeżeli n = 1;
�ł
�ł
�ł
�ł
�ł
s(n) = 2, jeżeli n = 2;
�ł
�ł
�ł
�ł
Zamknij plik
�ł
�ł
�ł
�ł
�ł
ół s(n - 2) + s(n - 1), jeżeli n > 2.
Koniec pokazu
KANGUR Online
Strona tytułowa
PROBLEM 8. Ile jest sposobów zdobycia
n punktów w meczu koszykówki przez jedną
z drużyn?
Poprzedni slaid
Pełny ekran
Zamknij plik
Koniec pokazu
+3
KANGUR Online
+2
Strona tytułowa
+1 +1
+1
0 1 2 3
+2
Poprzedni slaid
Pełny ekran
l(1) = 1, l(2) = 2, l(3) = 4.
Zamknij plik
Koniec pokazu
+3
KANGUR Online
+2
Strona tytułowa
+1
n-3 n-2 n-1 n
ńł Poprzedni slaid
�ł
�ł
1, jeżeli n = 1;
�ł
�ł
�ł
�ł
�ł
�ł
�ł
2, jeżeli n = 2;
l(n) =
�ł
Pełny ekran
�ł
�ł 4, jeżeli n = 3;
�ł
�ł
�ł
�ł
�ł
ół
l(n - 3) + l(n - 2) + l(n - 1), jeżeli n > 3.
Zamknij plik
Koniec pokazu
KANGUR Online
Strona tytułowa
n 1 2 3 4 5 6 7 8 9 10 11 12
l(n) 1 2 4 7 13 24 44 81 149 274 504 927
Poprzedni slaid
Pełny ekran
Zamknij plik
Koniec pokazu
PROBLEM 9.(porównaj Junior 2010, py-
tanie 30)
Pasek kodu kreskowego tworzą na przemian
KANGUR Online
kreski czarne i białe. Kod ten zawsze zaczyna
się i kończy czarną kreską. Każda z kresek
Strona tytułowa
(czy to czarna, czy biała) ma grubość 1 albo
2 (przykładowy kod na rysunku).
Poprzedni slaid
n
Pełny ekran
Ile jest pasków długości n o różnych ko-
dach (kody zawsze czytamy od lewej do pra- Zamknij plik
wej strony)?
Koniec pokazu
KANGUR Online
Strona tytułowa
2 3
1
Poprzedni slaid
4 4 4
Pełny ekran
L(1) = 1, L(2) = 1, L(3) = 1, L(4) = 3.
Zamknij plik
Koniec pokazu
KANGUR Online
n-2 n-3
Strona tytułowa
n n
n-3 n-4
Poprzedni slaid
n n
Pełny ekran
L(n) = L(n - 2) + 2 � L(n - 3) + L(n - 4)
Zamknij plik
Koniec pokazu
KANGUR Online
Strona tytułowa
n 1 2 3 4 5 6 7 8 9 10 11 12 13
L(n) 1 1 1 3 4 6 11 17 27 45 72 116 189
Poprzedni slaid
Pełny ekran
Zamknij plik
Koniec pokazu
KANGUR Online
Strona tytułowa
e& Zbiór skończony i jego
podzbiory, rozkłady zbioru
w rodziny podzbiorów
Poprzedni slaid
Pełny ekran
Zamknij plik
Koniec pokazu
PROBLEM 10. Zbiór X ma n elementów.
Ile jest różnych podzbiorów zbioru X o k ele-
mentach?
KANGUR Online
Jeśli k > n, to nie istnieje żaden podzbiór
Strona tytułowa
zbioru X o k elementach. Załóżmy więc, że
0 k n.
Poprzedni slaid
Niech
Pełny ekran
C(n, k)
oznacza liczbę wszystkich k elementowych
Zamknij plik
podzbiorów zbioru X.
Koniec pokazu
Oczywiście
C(n, 0) = 1, C(n, n) = 1.
KANGUR Online
Ustalmy element x " X. Niech Y będzie do-
wolnym k elementowym podzbiorem zbioru
X. Mamy dwa przypadki: x " Y albo x " Y
/
Strona tytułowa
x
x
Y
Poprzedni slaid
Y
X
X
Pełny ekran
Zamknij plik
C(n, k) = C(n - 1, k - 1) + C(n - 1, k)
Koniec pokazu
Trójkąt Pascala
KANGUR Online
n k 0 1 2 3 4 5 6 7 8 9
0 1
Strona tytułowa
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
Poprzedni slaid
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
Pełny ekran
7 1 7 21 35 35 21 7 1
8 1 8 28 56 70 56 28 8 1
Zamknij plik
9 1 9 36 84 126 126 84 36 9 1
Koniec pokazu
PROBLEM 11. Danych jest n różnoko-
lorowych kredek. Kredki te rozkładamy do
k jednakowych (nierozróżnialnych) pudełek
KANGUR Online
tak, że w każdym z tych pudełek znajdzie się
przynajmniej jedna kredka. Na ile sposobów
Strona tytułowa
możemy to zrobić?
Niech X oznacza zbiór kredek. Każde roz-
łożenie kredek do k pudełek powoduje roz-
bicie zbioru X na k niepustych podzbiorów
X1, X2, . . . , Xk.
Poprzedni slaid
Pełny ekran
Oznaczmy poszukiwaną liczbę przez
S(n, k).
Zamknij plik
Koniec pokazu
Jeśli k > n, to żądany rozkład jest niemoż-
KANGUR Online
liwy. Załóżmy więc, że 1 k n. Gdy k = 1,
to jedyną klasą musi być cały zbiór X, więc:
Strona tytułowa
S(n, 1) = 1 .
Podobnie, gdy k = n, to jedynym roz-
kładem jest rodzina zbiorów jednoelemento-
Poprzedni slaid
wych {{z}; z " X}, więc:
Pełny ekran
S(n, n) = 1 .
Zamknij plik
Koniec pokazu
Niech 1 < k < n. Ustalmy element x " X. Je-
żeli wez
miemy dowolny rozkład zbioru X na
k klas, to mamy dwa przypadki: albo {x} jest
klasą tego rozkładu, albo {x} nie jest klasą
KANGUR Online
tego rozkładu
Strona tytułowa
klasa {x}
x
x
k-1 klas
k klas
Poprzedni slaid
Pełny ekran
X-{x}
X
Zamknij plik
S(n, k) = S(n - 1, k - 1) + k � S(n - 1, k)
Koniec pokazu
Liczby Stirlinga
KANGUR Online
n k 1 2 3 4 5 6 7 8 9 10
Strona tytułowa
1 1
2 1 1
3 1 3 1
4 1 7 6 1
5 1 15 25 10 1
6 1 31 90 65 15 1 Poprzedni slaid
7 1 63 301 350 140 21 1
8 1 127 966 1701 1050 266 28 1
Pełny ekran
9 1 255 3025 7770 6951 2646 462 36 1
10 1 511 9330 34105 42525 22827 5880 750 45 1
Zamknij plik
Koniec pokazu
KANGUR Online
Strona tytułowa
`& O pewnym meczu
piłkarskim, czyli o zliczaniu
ścieżek w grafie
Poprzedni slaid
skierowanym
Pełny ekran
Zamknij plik
Koniec pokazu
PROBLEM 12. (porównaj Junior 2006,
pytanie 30)
W meczu piłki ręcznej drużyna gospodarzy
KANGUR Online
objęła prowadzenie i utrzymała je do stanu
n : k (oczywiście n > k). Na ile sposobów mo-
gły padać bramki w tym meczu do tego mo-
Strona tytułowa
mentu?
Zilustrujmy możliwy przebieg meczu do
stanu n : k, n > k, za pomocą grafu zorien-
towanego. Wynikowi x : y przyporządkujmy
Poprzedni slaid
punkt kratowy o współrzędnych (x, y), a
punkty (x, y) łączymy strzałkami z punktami
Pełny ekran
(u, v), gdy wynik u : v jest możliwym wyni-
kiem bezpośrednio po wyniku x : y. Graf taki
Zamknij plik
dla n = 6 i k = 5 przedstawia rysunek na na-
stępnym slajdzie.
Koniec pokazu
y
B
5
KANGUR Online
4
Strona tytułowa
3
2
Poprzedni slaid
1
Pełny ekran
x
Zamknij plik
O 1 2 3 4 5 6
Koniec pokazu
Oznaczmy przez w(n, k) liczbę wszystkich
ścieżek prowadzących od punktu (0, 0) do
punktu (n, k). Mamy:
KANGUR Online
a) jeżeli k = 0, to
Strona tytułowa
w(0, 0) = 0 oraz w(n, 0) = 1
dla n > 0;
b) jeżeli k = 1, to
Poprzedni slaid
w(2, 1) = 1
Pełny ekran
oraz
Zamknij plik
w(n, 1) = w(n, 0) + w(n - 1, 1)
Koniec pokazu
dla n > 2;
c) jeżeli 1 < k < n - 1, to
KANGUR Online
w(n, k) = w(n, k - 1) + w(n - 1, k)
Strona tytułowa
d) jeżeli k = n - 1, to
w(n, k) = w(n, k - 1) ,
Poprzedni slaid
czyli
Pełny ekran
w(n, n - 1) = w(n, n - 2) .
Zamknij plik
Koniec pokazu
Tabela wartości w(n, k)
KANGUR Online
n k 0 1 2 3 4 5 6 7 8 9
Strona tytułowa
0 0
1 1
2 1 1
3 1 2 2
4 1 3 5 5
5 1 4 9 14 14
Poprzedni slaid
6 1 5 14 28 42 42
7 1 6 20 48 90 132 132
Pełny ekran
8 1 7 27 75 165 297 429 429
9 1 8 35 110 275 572 1001 1430 1430
10 1 9 44 154 429 1001 2002 3432 4862 4862
Zamknij plik
Koniec pokazu