Not logged inCSS-Forum
Forum CSS-Online Help Search Login
CSS-Shop Impressum Datenschutz
Up Topic Hauptforen / CSS-Forum / Herbsträtsel September
- By Frank Brenner Date 2016-09-27 13:21
Heute startet das erste Herbsträtsel.

Wer die Lösung bereits kennt oder blitzschnell findet, bitte nicht sofort die Lösung öffentlich posten :=)
Ich denke es macht mehr Spass, wenn kein Zeitdruck vorliegt.
In ca 1 Woche  kommt dann die Lösung sofern jemand hier mitmacht und an der Lösung interessiert ist.
Es gibt mehrere Lösungswege

Dieses Rätsel lässt sich auch durch bloßes Nachdenken ohne Papier und Bleistift lösen (teil a&b), wobei es ohne Hilfsmittel allerdings ganz schön schwer ist.
An Vorkenntnissen sind eigentlich nur die 4 Grundrechenarten erforderlich und natürlich die Rechengesetze, also klasse 9 oder 10 der Schule.

Eine Spur einer Liste von Zahlen der Form (1,2,3,...n) ist eine Menge von paarweise nicht überlappenden Teillisten der Form (i,i+1,i+2,i+3,...i+k)

Beispiele für Spuren für die Liste (1,2,3,4,5,6,7):

{ (1), (3 4 5), (7) }  
{ (2 3), (6) } ,
{}  ,
{ (1 2 3 4 ) (6 7) }  und
{ (2), (4), (5) }
{ (1) }  
...

Insgesamt gibt es aber noch mehr. Die leere Menge ist stets dabei.

Fragen:

a) Wieviele Spuren gibt es für (1,2,3,4,5) ?

b) Gib eine rekursive Formel für die Anzahl der Spuren S(n) der Startsequenz (1,2,...n) an.
Das wäre dann eine Formel der Form: S(n) = c1 * S(n-1) + c2 * S(n-2)   , wobei c2 und c2 konstante Zahlen sind.
Wichtig hier:  Beweise (oder Begründe sehr genau in Worten) daß S(n) tatsächlich in dieser rekursiven Form berechenbar ist und leite c1 und c2 her.

c) Was hat die Folge S(n) mit der Fibonaccifolge gemeinsam ?
Hinweis: Die Fibonacci Folge ist wie folgt definiert: F(0) = 0, F(1) = 1, F(n) = 1* F(n-1) + 1* F(n-2)
Up Topic Hauptforen / CSS-Forum / Herbsträtsel September

Powered by mwForum 2.29.3 © 1999-2014 Markus Wichitill