FIBONACCI-Folge

Lösungsskizzen

Aufgabe 1:
Die erste Stufe einer Treppe ( insgesamt n Stufen ) ist auf jeden Fall zu betreten. Bei jedem weiteren Schritt kann optional jeweils eine Treppenstufe übersprungen werden.
Wie viele Möglichkeiten der Treppenbegehung sind denkbar ?

Sei F(n) die Anzahl der verschiedenen Wege auf die n-te Stufe. Zur n-ten Stufe gelangt man über die (n-2)-te, oder über die (n-1)-te Stufe. Somit ergibt sich :   F(n) = F(n-2) + F(n-1) *
Man sieht sofort, dass es auf die erste und zweite Stufe jeweils nur einen Weg gibt. D.h.: F(1) = F(2) = 1. &nbsP; Zusammen mit den Randwerten F(1) und F(2) ergibt * die rekursive Darstellung der Fibonacci-Folge !
Die Frage nach der Anzahl der verschiedenen Wege auf die n-te Stufe lässt sich somit durch Weiterentwicklung der Zahlenfolge 1 , 1 , 2 , 3 , 5 , 8 , 13 , ..... beantworten.
Bei größeren n empfiehlt sich die Erstellung eines geeigneten Computerprogramms, oder die Verwendung der expliziten Darstellung von F(n) nach Binet:
    Beispiel: F(40) = 102334155


5 Jahrhunderte lang bemühten sich fast alle renommierten Mathematiker um eine explizite Darstellung der Fibonacci-Rekursion. Die heute als Binet-Formel bekannte Darstellung wurde ursprünglich im Jahre 1745 von Euler gefunden.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------





Aufgabe 2:
Bei einer Treppe mit insgesamt n Stufen, ist die erste Stufe auf jeden Fall zu betreten. Bei jedem weiteren Schritt können optional jeweils bis zu k Treppenstufen auf einmal genommen werden.
Wie viele Möglichkeiten der Treppenbegehung sind denkbar ?

Sei F(n) die Anzahl der verschiedenen Wege zur n-ten Stufe.
Gemäß Aufgabenstellung gelangt man zur n-ten Stufe entweder über die (n-1)-te Stufe, oder über die (n-2)-te Stufe, ...... oder über die (n-k)-te Stufe. Somit gilt:    F(n) = F(n-1) + F(n-2) + F(n-3) + ... + F(n-k).
Offensichtlich gelten die Randbedingungen:   F(1) = 1   und   F(2) = 1.
Mit Hilfe der Randbedingungen lässt sich F(n) somit rekursiv ermitteln!
In der Aufgabenstellung ist n = 25 und k = 4. Die ersten 15 Glieder dieser Fibonaccifolge lauten:   1 ; 1 ; 2 ; 4 ; 8 ; 15 ; 29 ; 56 ; 108 ; 208 ; 401 ; 773 ; 1490 ; 2872 ; 5536 ; .........
Für die 25. Stufe ergeben sich - in Fortführung der Rekursion -  3919944  unterschiedliche Möglichkeiten.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------



Aufgabe 3:
Chairs in a row: The teacher's version
Imagine we have n chairs in a row and a roomful of people. If you've ever been to a gathering where there are teachers present, you will know they always talk about their school/college (boring!). So we will insist that no two teachers should sit next to each other along a row of 26 seats and count how many ways we can seat people, if some are teachers (who cannot be next to each other) and some are not.

Im Folgenden steht "L" für Lehrer und "K" für 'kein Lehrer'.
Für einen Stuhl gibt es zwei Möglichkeiten:   K oder L Somit:   F(1) = 2
Für zwei Stühle gibt es drei Möglichkeiten:   KK, KL oder LK Somit:   F(2) = 3
Für drei Stühle gibt es drei Möglichkeiten:   KKK , KKL , KLK , LKK oder LKL Somit:   F(3) = 5
Für vier Stühle gibt es acht Möglichkeiten:   ........................... Somit:   F(4) = 8


Allgemein:   Die Aufgabenstellung ist logisch äquivalent zur Frage nach der Anzahl der verschiedenen Strings der Länge n ( Anzahl der Stühle ) , bei denen niemals zwei Leher nebeneinander sitzen. ( D.h.: Der String S(n) darf den Substring "LL" nicht enthalten ! )
'LKLKKKL'    ist somit ein zulässiger String.
'KKLKLLK'    ist ein unzulässiger String.

Sei F(n) die Menge aller zulässigen Strings der Länge n.
a)  Beginnt ein String der Länge n mit 'L', so muss das nächste Zeichen ein 'K' sein ! D.h.: Es gibt F(n-2) zulässige Strings der Länge n, die mit 'L' beginnen !
b)  Beginnt ein String der Länge n mit 'K', so kann des nächste Zeichen 'K' oder 'L' sein und es gibt F(n-1) zulässige Strings der Länge n, die mit 'K' beginnen !
Da es nur die Möglichkeite a) und b) gibt, folgt :    F(n) = F(n-2) + F(n-1)
Die ersten Glieder der zugehörigen Folge lauten :   2 ; 3 ; 5 ; 8 ; 13 ; 21 ; 34 ; 55 ; 89 ; 144 ; 233 ; 377 ; ....
Beispiel: 26 Stühle ermöglichen 317811 verschiedenen Sitzordnungen.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------




Aufgabe 4:
Chairs in a row: The antisocial version
English people can be very reserved sometimes and like not to bother people by sitting next to them if they can possibly help it.
So this time we consider a row of n = 26 chairs, but this time insist that no one can sit next to anyone else. There may be no one in the row, or just one person, but whenever there are two people or more, they must always be seperated by at least one empty seat, so that no one sits next to anyone else. How many ways can people be seated ?

Im Folgenden steht "B" für 'besetzt' und "L" für 'lehr'.
Für einen Stuhl gibt es zwei Möglichkeiten:   B oder L Somit:   F(1) = 2
Für zwei Stühle gibt es drei Möglichkeiten:   LL, BL oder LB Somit:   F(2) = 3
Für drei Stühle gibt es drei Möglichkeiten:   LLL , BLL , LBL , LLB oder BLB Somit:   F(3) = 5
Für vier Stühle gibt es acht Möglichkeiten:   ........................... Somit:   F(4) = 8

In der logischen Konsequenz ist Aufgabe 4 absolut identisch zu Aufgabe 3!

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------



Aufgabe 5:
Eine Münze wird n-mal geworfen. Berechne die Wahrscheinlichkeit, dass 'Kopf' höchstens r-mal hintereinander erscheint !

Für eine vereinfachte Betrachtung sei r zunächst gleich 1. ( D.h.: Der String   KZZKZKZZK ...... darf den Substring "KK" nicht enthalten ! )
Sei k(n) die Anzahl der Möglichkeiten, eine Münze n-mal so zu werfen, dass 'Kopf' niemals zweimal hintereinander auftritt und der letzte Wurf 'Kopf ' ist. < Für n = 7 z.B.:  KZZZKZK >
z(n) sei die Anzahl der Möglichkeiten, eine Münze n-mal so zu werfen, dass 'Kopf' niemals zweimal hintereinander auftritt und der letzte Wurf 'Zahl' ist.   < Für n = 7 z.B.:  ZZKZKZZ>
Schließlich sei sei p(n) die Wahrscheinlichkeit, eine Münze n-mal zu wefen, ohne dass 'Kopf' zweimal hintereinander auftritt.

Offensichtlich gilt:   p(n) = ( k(n) + z(n) ) / 2n   *.            ( 2n   gibt die Anzahl aller denkbaren Strings der Länge n an ! )

Man erkennt unschwer, dass gilt:            z( n + 1 ) = k(n) + z(n)   ** ( Man fügt jedem zulässigen String der Länge n ein 'Z' hinzu. Das führt sowohl bei den k(n) Strings die auf 'K' endeten,
als auch bei den z(n) Strings die auf 'Z' endeten zu einem wiederum zulässigen String ! )
Andererseits gilt :                                   k( n + 1 ) = z(n)           ***.
 ;( Man fügt jedem zulässigen String der Länge n ein 'K' hinzu. Das gelingt aber nur bei den z(n) Strings, die mit 'Z' enden !
Bei allen anderen Strings - diese enden alle mit 'K' - führt das Anhängen von 'K' zu dem unzulässigen Substring 'KK'. )

Setzt man *** in * ein, so folg:    p(n) = ( k(n) + k(n+1) ) / 2n

Aus *** folgt: k(n) = z(n-1). Eingesetzt in ** liefert: z(n+1) = z(n) + z(n-1).
Mit z(1) = 1 { Z }  und   z(2) = 2 { ZZ ; KZ }  ,  und  k(1) = 1 {K}    sind die Folgen Z und K rekursiv eindeutig definiert:

Z :   1 ; 2 ; 3 ; 5 ; 8 ; 13 ; 21 ; 34 ; 55 ; 89 ; .......
K :   1 ; 1 ; 2 ; 3 ; 5 ; 8 ; 13 ; 21 ; 34 ; 55 ; 89 ; .......
Für die Summe  k(n)+k(n+1)   ergibt sich somit :    2 ; 3 ; 5 ; 8 ; 13 ; 21 ; 34 ; 55 ; 89 ; 144 ; 233 ; ....
 Die Elemente dieser Folge entsprechen den Elementen F(n+2) der Fibonacci-Folge !
Die Wahrscheinlichkeit   p(n) = (k(n)+k(n+1))/2n    berechnet sich somit über die Formel:     p(n) = F(n+2)/2n
Beachte: Mit Hilfe der Formel wird die Wahrscheinlichkeit berechnet, dass bei n Münzwürfen 'Kopf' niemals 2-mal hintereinander geworfen wird!

Nun sei r = 2 . ( D.h.: Der String   KZZKZKKZZK ...... darf den Substring "KKK" nicht enthalten ! )
Sei k2(n) die Anzahl der Möglichkeiten, eine Münze n-mal so zu werfen, dass 'Kopf' niemals dreimal hintereinander auftritt und die beiden letzten Würfe jeweils 'Kopf ' zeigen. < Z.B.:  KZZZKKZKK >
Sei k1(n) die Anzahl der Möglichkeiten, eine Münze n-mal so zu werfen, dass 'Kopf' niemals dreimal hintereinander auftritt und die Wurfserie mit 'ZK' endet. < Z.B.:  KZZKKZKZK >
Sei z(n) die Anzahl der Möglichkeiten, eine Münze n-mal so zu werfen, dass 'Kopf' niemals dreimal hintereinander auftritt und der letzte Wurf 'Zahl' ist. < Z.B.:  KKZZZKZZ >
Die gesuchte Wahrscheinlichkeit p(n,k=2) ergibt sich dann zu    p(n,2) = ( k2(n) + k1(n) + z(n) ) / 2n  (*)

Es gilt offensichtlich:    a)  k1(n+1) = z(n)   →  k1(n) = z(n-1)
                                  b)  k2(n+1) = k1(n)   →  k2(n) = k1(n-1)          Eingesetzt in (*)   folgt :       p(n,2) = ( k1(n-1) + k1(n) + k1(n+1) ) / 2n   (**)

Durch Abzählen erkennt man:
k1(0) = 0   { };        k1(1) = 1   { K };        k1(2) = 1   { ZK };        k1(3) = 2   { ZZK ; KZK };        k1(4) = 4   { ZZZK ; ZKZK ; KZZK ; KKZK };       
k1(5) = 7   { ZZZZK ; ZZKZK ; ZKZZK ; KZZZK ; KKZZK ; KZKZK ; ZKKZK };        .......       k1(n) = F3(n)       .........

Für den Zähler der Formel (**) ergibt sich somit die Folge :       2 ; 4 ; 7 ; 13 ; 24 ; 44 ; 81 ; 149 ; 274 ; 504 ; 927 ; ......... F3( n+2 ) ; .............
Die Wahrscheinlichkeit, dass bei n-maligem Werfen einer Münze 'Kopf' höchstens zweimal hintereinander auftritt berechnet sich somit zu    p(n,r=2) = F3( n+2 ) / 2n

Durch Vollständige Induktion lässt sich allgemein zeigen :       p(n,r) = Fr+1( n+2 ) / 2n

Mit   n = 40 Münzwürfen und r = 4 ( Siehe Aufgabenstellung! ) berechnet sich die gesuchte Wahrscheinlichkeit somit zu   p(40,4) = F5(42) / 240 = 0,1377 !

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------



Aufgabe 6:
Wie viele verschiedenen Wege kann eine Biene nehmen, wenn sie durch zwei Reihen sechseckiger Zellen kriecht. Die Reihen setzen sich nach rechts beliebig weit fort. Die Biene bewegt sich zu einer benachbarten Zelle immer nur nach rechts , rechts-oben oder rechts-unten, und will von ihrem derzeitigen Standort ( Siehe Skizze! ) in Zelle 36 gelangen.

Wabe Nr.: 0 1 2 3 4 ......... 36
Möglichkeiten: 1 2 3 5 8 ......... 39088169


Zurück zu den Aufgabenstellungen