Fibonacci

Pfade und Muster

In der Einführung haben wir zwei Probleme über die Anlage eines Pfades betrachtet:
Hier nenne ich noch drei vergleichbare Probleme:


Problem 1: Ich will einen steinernen Pfad anlegen. Dazu verfüge ich über rote und grüne Steine. Der Pfad und die Steine sind gleich breit. Wie viel verschiedende Pfade (Muster) der Länge n kann ich anlegen wenn nirgendwo zwei rote Steine nebeneinander liegen dürfen?

Problem 2: Wenn in Problem 1 der Pfad einen Kreis rund um einen Teich bildet. Wie viel verschiedende Pfade der Länge n kann ich dann anlegen?

Problem 3: Ich will einen steinernen Pfad anlegen. Dazu verfüge ich über rote und grüne Steine. Der Pfad und die Steine sind gleich breit. Wie viel verschiedende Pfade (Muster) der Länge n kann ich anlegen wenn nirgendwo drei gleichfarbige Steine nebeneinander liegen dürfen?

Problem 4: Ich will einen steinernen Pfad anlegen. Dazu verfüge ich über Steine von beliebiger Läge, mit Ausnahme von quadratischen (=1x1) Steinen. Der Pfad und die Steine sind gleich breit. Wie viel verschiedende Pfade (Muster) der Länge n kann ich anlegen?

Problem 5: Ich will einen steinernen Pfad anlegen. Dazu verfüge ich über rote und grüne Steine. Der Pfad und die Steine sind gleich breit. Wie viel verschiedende Pfade (Muster) der Länge n kann ich anlegen wenn jeder Stein neben einem gleichfarbigen Stein liegt?

Lösung Problem 1:
Die Anzahl Pfade der Länge n nennen wir a_n, und die Anzahl mit einem roten letzten Stein r_n und die Anzahl mit einem grünen letzten Stein g_n. Füge nun einen Stein an alle Pfade der Länge n zu. Auf den r_n Steinen mit einem roten letzten Stein folgt einem grünen, und auf den g_n Steinen folgt einem willkürlichen Stein. Also, r_n+1 = g_n und g_n+1 = g_n + r_n (= a_n). Substitution liefert g_n+1 = g_n + g_n-1 (= a_n), sodass a_n = a_n-1 + a_n-2.    a₁ = 2, a₂ = 3, also a_n = F_n+2.

Lösung Problem 2:
Von den F_n+2 Lösungen des ersten Problems genügen nicht die Lösungen mit einem roten Stein an beiden Enden, also die Lösungen die mit rot grün anfangen und mit grün rot enden.
Dazwischen gibt es F_(n-4)+2 Lösungen, also gibt es
F_n+2 - F_n-2 = F_n+1 + F_n - F_n-2 = F_n+1 + F_n-1 = L_n mögliche Pfade.

Lösung Problem 3:
Die Anzahl Pfade der Länge n ist wieder a_n. Wenn wir an die a_n Pfade der Länge n ohne Vorbehalt einen willkürlichen Stein zufügen dürften, so bekämen wir 2a_n Pfade der Länge n+1. Leider, davon müssen die Pfade die mit grün, rot, rot, rot oder rot, grün, grün, grün enden abgezogen werden. Davon gibt es a_n-2. Also a_n+1 = 2a_n - a_n-2 = a_n + a_n-1.    a₁ = 2, a₂ = 4, also a_n = 2F_n+1.

Lösung Problem 4:
Wir zeigen (mit Verlaufsinduktion) dass die Anzahl Pfade der Läge n, F_n-1 ist.
Dit Behauptung stimmt für n=1, denn die Anzahl erdenklichen Pfade der Länge 1 ist 0 = F₀.
Nehmen wir mal an, wir hätten schon gezeigt, dass die Behauptung für alle n<N stimme (wobei N eine positive ganze Zahl ist größer als 1). Ich werde nun zeigen dass die Behauptung auch für n=M stimmt.
Betrachte dazu einen Pfad der Länge N. Wenn der letzte Stein Länge k(>1) hat, dann kann der Teil des Pfades dass vor dem letzten Stein liegt auf F_N-k-1 Weisen angelegt sein (nach der Induktionshypothese). Der letzte Stein kan Länge N,N-1,N-2,...3 oder 2 haben. Die damit übereinstimmenden Teile vor dem letzten Stein können also auf 1,F₀,F₁,...,F_N-4 oder F_N-3 Weisen angelegt sein.
Im Ganzen sind das 1 + F₀ + F₁ + ... + F_N-4 + F_N-3 = F_N-1 {Diese Formel wird hier bewiesen} Weisen. ALso, die Behauptung stimmt auch für n=N, und die Anzahl Pfade der Länge n is F_n-1

Lösung Problem 5:
Farbe in Problem 4 die angelegten Steine abwechselnd rot und grün. Das kann man in zweierlei Weisen machen, denn der erste Stein kann rot oder grün gefärbt sein. Also ist dann die Anzahl gefärbten Pfade der Länge n gleich 2F_n-1. Wenn wir darauf die Steine brechen sodass nur quadratischen Steine übrigbleiben, dann entstehen Pfade wie im vorigen Problem. Also ist die Anzahl Pfade 2F_n-1.