logowanie


matematyka » zadania » zbiór zadań » rozwiązanie zadania

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 >>





© 2023 math.edu.pl      kontakt