Malowanie płotu

piotrek20008 · Post autor: **piotrek20008** » 14 wrz 2009, o 16:29

Malujemy płot. Każdą sztachetę możemy pomalować jednym z pięciu kolorów : białym czerwonym, zielonym, niebieskim lub żółtym. Biała sztacheta może wystąpić obok dowolnej sztachety, ale kolorowa sztacheta nie może wystąpić obok innej kolorowej sztachety innego koloru.
Na ile sposobów możemy pomalować płot składający się z n sztachet?

abc666 · Post autor: **abc666** » 14 wrz 2009, o 23:00

Rekurencyjnie. Stawiamy pierwszą sztachetę na 5 sposobów. Dwie możemy postawić na 9 sposobów. Dostawiamy kolejną. Jeśli ostatnia jest białą to możemy dostawić jedną z 5. Jeśli jest kolorowa to tylko białą. Oznaczmy przez \(\displaystyle{ a_n}\) liczbę możliwości przy \(\displaystyle{ n}\) sztachetach. Przez \(\displaystyle{ b_n}\) liczbę możliwości zakończonych białymi sztachetami, a przez \(\displaystyle{ c_n}\) zakończonych kolorowymi. Oczywiście \(\displaystyle{ a_n=b_n+c_n}\). Łatwo też zauważyć, że \(\displaystyle{ b_n=a_{n-1}}\) oraz że \(\displaystyle{ c_n=4 b_{n-1}=4 a_{n-2}}\). Czyli \(\displaystyle{ a_n=a_{n-1}+4a_{n-2}}\) Wystarczy rozwiązać tą prostą rekurencję przy założeniach początkowych
\(\displaystyle{ a_1=5 \\ a_2=9}\)

Niech ktoś sprawdzi jeszcze .

Dumel · Post autor: **Dumel** » 15 wrz 2009, o 11:31

też podobnie próbowałem, ale to trudniejsze niż sie wydaje, bo
\(\displaystyle{ c_n=4(b_{n-1}+b_{n-2}+...+b_1)+4}\)

abc666 · Post autor: **abc666** » 15 wrz 2009, o 16:58

Raczej nie, sprawdziłem do 5 sztachet i to co napisałem się zgadza.

EDIT
Już widzę gdzie mam błąd w rozumowaniu. Nie zauważyłem że czerwona może stać koło czerwonej na przykład. Zaraz coś pomyśle.

edit2
jakby ktoś chciał sprawdzać to

\(\displaystyle{ a_1=5 \\
a_2=13\\
a_3=41\\
a_4=121\\
a_5=365}\)

edit3
po przemyśleniach
\(\displaystyle{ b_n=a_{n-1}\\
c_n=4b_{n-1}+c_{n-1}}\)

Dumel · Post autor: **Dumel** » 16 wrz 2009, o 11:18

rozwine swój pierwotny sposób (bylo blisko):
rozpatrujemy położenie pierwszej białej sztachety
w ogóle nie ma białej- 4 możliwości
jest na pierwszym miejscu- \(\displaystyle{ a_n}\) możliwości
na drugim - \(\displaystyle{ 4a_{n-1}}\) itd...
na ostatnim - 4 możliwości

więc
\(\displaystyle{ a_{n+1}=4+a_n+4(a_{n-1}+a_{n-2}+...+a_1)+4}\)
oraz
\(\displaystyle{ a_{n}=4+a_{n-1}+4(a_{n-2}+a_{n-3}+...+a_1)+4}\)
odejmujemy stronami, upraszczmy i mamy
\(\displaystyle{ a_{n+1}=2a_n+3a_{n-1}}\)

później równanie charakterystyczne i:
\(\displaystyle{ a_n= \frac{1}{2}(3^{n+1}+(-1)^{n+1})}\)