Ciągi zerojedynkowe

Majorkan · Post autor: **Majorkan** » 28 paź 2009, o 15:56

Ile jest ciągów długości n o wyrazach 0 i 1 oraz tej własności, że żadne 3 kolejne wyrazy ciągu nie są takie same?

andrew2303 · Post autor: **andrew2303** » 28 paź 2009, o 16:13

0,0,1,...
0,1,0,...
0,1,1,... \(\displaystyle{ 2^{3}}\)-2= 8-2 =6
1,0,0,... wszystkich było by 8 ale 2 ostatnie były by złożone z takich samych składników
1,0,1,... albo z samych 0, albo z samych 1,co by było niezgodne z treścią zadania
1,1,0,...

Majorkan · Post autor: **Majorkan** » 28 paź 2009, o 18:35

Jak napisałem, chodzi o ciągi długości n, gdzie n jest dowolnie ustaloną liczbą naturalną dodatnią (myślałem, że to oczywiste).

Swoją drogą, chyba udało mi się to już rozwiązać; w każdym razie dostałem w miarę sensowny wynik. Zadanie z pewnością jest ciekawe, dlatego chętnie zobaczyłbym jeszcze czyjeś rozwiązanie.

abc666 · Post autor: **abc666** » 28 paź 2009, o 20:12

Najłatwiej to zrobić rekurencyjnie, poprze doklejanie 0 lub jedynki z danej strony, zaczynamy od ciągów trójelementowych i doklejamy 0 lub 1 (ciągi krótsze rozpatrujemy osobno). Jak na końcu są dwa zera to możemy dokleić jedynkę, a jak dwie jedynki to zero, w pozostałych przypadkach możemy co chcemy ale z znowu patrzymy co jest na końca, czy zero czy jedynka. Po zapisaniu tych wszystkich zależności dostajemy prostą ale zapewne żmudną przy rozwiązywaniu rekurencję liniową, która daje wynik.