Matematyka dyskretna, zadanie nr 1624

Autor	Zadanie / Rozwiązanie
ememensa postów: 7	2013-10-28 13:37:39 zadanie brzmi: niech a_n oznacza liczbe n-elementowych ciagow zlozonych z zer i jedynek, takich ze nie ma w nich trzech jednakowych elementow kolo siebie. trzeba pokazac, ze a_n = a_n-1 + a_n-2 dla n>=5 (podpowiedz: mozna rozpatrzyc 4 przypadki ciagi konczace sie na 00, 01, 10, 11) i trzeba dla nich znalezc rekurencje - jak? pomóżcie, błagam.

tumor postów: 8070	2013-10-28 17:06:10 $ a_1=2$ $a_2=4$ Zauważ, że ciągi 00 i 11 (czyli 2 ciągi) można przedłużyć na jeden sposób (do 001 i do 110), natomiast ciągi 01 i 10 można przedłużyć na dwa sposoby. Zatem $a_3=6=a_2+a^3$ Podobnie gdy już mamy ciągi 001, 010, 011, 100, 101, 110, to każdy z nich można przedłużyć o cyfrę różną od ostatniej (otrzymamy zatem $a_3$ nowych ciągów 4-wyrazowych), a dodatkowo niektóre (te zakończone dwiema różnymi cyframi) można przedłużyć także o kopię ostatniej cyfry. Tych zakończonych dwiema różnymi cyframi jest $a_2$ (gdyż powstają one z ciągów dwuwyrazowych przez dodanie na trzecim miejscu cyfry różnej od cyfry na miejscu drugim). Indukcyjnie to samo mamy założone dla $n-1$ i robimy dla $n$. Mając $a_{n-1}$ ciągów n-1-wyrazowych i tworząc ciągi n-wyrazowe, możemy każdy z $a_{n-1}$ ciągów przedłużyć o cyfrę różną niż stała na miejscu ostatnim, natomiast mamy $a_{n-2}$ ciągi o wyrazach, w których na dwóch ostatnich miejscach są różne cyfry, te możemy przedłużyć także powtarzając ostatnią cyfrę. Więc $a_n=a_{n-1}+a_{n-2}$ ---- Tu pominąłem założenie $n\ge 5$, bo nie jest istotne, wystarczy $n\ge 3$. Idea rozumowania przy zmianie punktu startowego zupełnie się nie zmieni, ja robiłem dla krótszych ciągów, żeby było ich mniej i można je było pisać w całości. :)

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj