Inne, zadanie nr 167

Autor	Zadanie / Rozwiązanie
mat12 postów: 221	2011-10-18 19:18:20 Ile jest ciągów o wyrazach równych 0 lub 1 w których żadne 3 kolejne wyrazy nie są takie same? Jak rozwiązać takie zadanie???

tumor postów: 8070	2012-09-20 15:52:02 O jakiej długości te ciągi? $n$? Dla $n=1$ sa $2$. Dla $n=2$ są $4$. Dla $n=3$ mamy $001,010,011,100,101,110$ Jest ich $6$. Popatrzmy, co dziać się będzie, gdy zechcemy te ciągi przedłużyć do $4$ wyrazów. Te ciągi, które kończą się podwójną $1$ lub podwójnym $0$ da się przedłużyć na jeden sposób (by nie otrzymać trzykrotnie tej samej cyfry). Natomiast pozostałe da się uzupełnić albo tą samą cyfrą, którą mają na końcu (wtedy stanie się podwójna), albo inną. Załóżmy, że dla pewnego $n$ mamy $x$ ciągów, z tego $0<p<x$ kończy się podwójną cyfrą, a $x-p$ kończy się dwiema różnymi cyframi. Wówczas $p$ ciągów przedłużamy zmieniając cyfrę, a $x-p$ ciągów przedłużamy na dwa sposoby. Mamy teraz $x-p+p=x$ ciągów z różnymi dwiema ostatnimi cyframi i $x-p$ ciągów z identycznymi dwiema ostatnimi cyframi. Dla $n+1$ mamy zatem $x+(x-p)$ ustawień I zróbmy jeszcze jeden krok, dla $n+2$ dostaniemy $x+(x-p)$ ciągów z dwiema ostatnimi cyframi różnymi i $x$ ciągów z dwiema identycznymi ostatnimi cyframi. Widzimy (mam nadzieję), że dla $n+2$ ilość ciągów jest taka, jak w sumie dla $n$ i dla $n+1$. Ciąg Fibonacciego! A dokładniej pewien wariant tego ciągu. Możemy dopisać do początkowych wyrazów kolejne: $2,4,6,10,16,26,42$ Obecnie przyjmuje się dla ciągu Fibonacciego $F_1=F_2=1$, potem $2,3,5,8,13...$ Przy takim oznaczeniu nasza ilość ciągów spełniających warunek z zadania faje się zapisać jako: $f(n)=2F_{n+1}$ ----- I znów dopisek dydaktyczny. Cały proces przedłużania ciągów można sobie zobrazować drzewem. Czasem z węzła wychodzą dwie gałęzie, czasem jedna (potem z takiej pojedynczej dwie, a w parze z jednej dwie, z drugiej jedna). Pomysł Fibonacciego dotyczył rozmnażania królików. Jedna para królików wydaje co miesiąc na świat parę młodych, ale rozmnażają się dopiero króliki mające już miesiąc. Zatem nowo narodzone króliki po zobrazowaniu na drzewie dadzą jedną gałąź - same siebie. Natomiast płodne króliki rozmnożą się, same stanowić będą jedną gałąź, a para ich potomstwa - drugą (płodną dopiero po miesiącu).

strony: 1

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