Ile jest ciągów \(\displaystyle{ n}\)-elementowych składających się z \(\displaystyle{ 0}\) i \(\displaystyle{ 1}\), w których żadne 3 kolejne wyrazy nie są takie same?
Rozpisując sobie w 'drzewku' możliwości zaczynając od zera, mam wrażenie, że dla kolejnych \(\displaystyle{ n}\) są one liczbami Fibonacciego, plus drugie tyle (zaczynamy od jedynki) i wynik którego się spodziewam to \(\displaystyle{ 2F _{n+1}}\). Ale nie potrafię tego formalnie wykazać
hm... za każdym razem możliwości "dowolnego" ciągu będzie \(\displaystyle{ 2^n}\). Od tego odjąć trzeba wszystkie ciągi, które mają te trzy kolejne wyrazy takie same.
Wybieramy zatem trzy kolejne miejsca na \(\displaystyle{ n-2}\) sposobów. (bo dla \(\displaystyle{ n=3}\) jeden sposób \(\displaystyle{ (123)}\), dla \(\displaystyle{ n=4: 123,234}\) itd.) Zauważmy, że wystarczy nam jedna trójka, żeby "zdyskwalifikować" dany ciąg, ale nie "tylko" jedna trójka. Może być ich więcej - nam to wszystko jedno.
Każdy taki ciąg trzeba pomnożyć razy \(\displaystyle{ 2}\) (bo dla \(\displaystyle{ 0}\) i dla \(\displaystyle{ 1}\)) oraz przez \(\displaystyle{ 2^{n-3}}\), bo resztę (\(\displaystyle{ p=n-3}\)) mozna przecież dobrać na \(\displaystyle{ 2^p}\) sposobów.
Dalej trzeba byłoby poprzeliczać.
Ostatnio zmieniony 21 paź 2014, o 23:27 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód:Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Mają być ciągi zero-jedynkowe a tu widzę pojawiają się nagle ciągi
np: \(\displaystyle{ 1,2,3}\)
może ktoś mi wytłumaczy to!
A poza tym skoro ciągi są zero-jedynkowe to jak wytłumaczyć że kolejne trzy wyrazy nie są takie same.
Załóżmy, że pierwszy wyraz będzie jeden drugi musi być zero a trzeci musi być równy któremuś
z dwóch poprzednich.
Wynika to nawet z zasady szufladkowej!!!
No chodzilo im o to, zeby nie bylo trzech jedynek obok siebie lub trzech zer obok siebie.
"zadne trzy kolejne nie sa takie same". Moim zdaniem jest to sformułowane jasno
itd...
dalej możesz indukcyjnie tam gdzie kończy się dwoma jedynkami lub dwoma zerami masz tylko jedną możliwość a tam gdzie się kończy \(\displaystyle{ 0,1}\) lub
