Inne, zadanie nr 167
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
mat12 post贸w: 221 |  2011-10-18 19:18:20Ile 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