Zbiór zadań, (zadania różne)
Zadanie 288
Ile jest $13$-elementowych ciągów zerojedynkowych, w których żadne dwa kolejne wyrazy nie są zerami?
Rozwiązanie
Niech $a_n$ i $b_n$ oznaczają liczby ciągów spełniających warunki zadania, kończących się odpowiednio zerem i jedynką. Rozwiązaniem będzie $a_n + b_n$. Dla $n=1$ mamy $a_1$ = $b_1 = 1$. Każdy ciąg $(n+1)$-elementowy kończący się zerem, spełniający warunki zadania, powstaje przez dopisanie zera na końcu z pewnego dobrego ciągu $n$-elementowego zakończonego jedynką, więc $a_{n+1}$ = $b_n$. Każdy ciąg $(n+1)$-elementowy kończący się jedynką, spełniający warunki zadania, powstaje przez dopisanie jedynki na końcu z pewnego dobrego ciągu $n$-elementowego kończącego się zerem lub jedynką, więc $b_{n+1} = a_n + b_n$.
Ciąg $(a_n)$ spełnia rekurencję $a_1 = 1$, $a_2 = 1$, $a_{n+2} = a_{n+1} + a_n$, dla $n = 1, 2, \ldots $. Jest więc ciągiem Fibonacciego, a szukana wartość to $f_n + f_{n+1} = f_{n+2}$.
Dla $n = 13$, $f_{13+2} = 610$.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>