Matematyka dyskretna, zadanie nr 1624
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
ememensa post贸w: 7 |  2013-10-28 13:37:39zadanie 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