Vorherige Aufgabe   Übersicht 2003   Nächste Aufgabe 

Lösungen der DENKmal-Knobelaufgaben

8. Aufgabe 2003

gestellt am 28. April 2003 in der Knobelecke von
Abenteuer Mathematik - die Welt des Knobelns

Sportlich die Treppe hinauf

  Aufgabe   Lösung   Antwort 

Aufgabe

Jemand hat eine Treppe mit 25 Stufen, die er täglich hinauf zu gehen hat.
Je nach Laune und sportlicher Ambition geht er mal Stufe für Stufe, mal nimmt er zwischendurch 2 Stufen auf einmal, mal auch 3 Stufen - in beliebiger Reihenfolge und beliebig oft, bis er oben angekommen ist.

Wie viele verschiedene Möglichkeiten gibt es, diese 25 Stufen auf die beschriebene Weise hinauf zu gehen?

(eingesandt von Johann Moll)

Lösung

Die gesuchte Anzahl lässt sich rekursiv bestimmen. Bei jeder möglichen Schrittweite für den ersten Schritt (1 bis 3) gibt es so viele Möglichkeiten wie für die jeweils restlichen Stufen. Die Summe dieser Anzahlen ergibt die Gesamtzahl der Möglichkeiten.
(1) a1 = 1
(2) a2 = a1+1 = 1+1 = 2
(3) a3 = a2+a1+1 = 2+1+1 = 4
(4) an = an-1+an-2+an-3 für n>3
oder kürzer
(5) a0 = 1 und
(6) an = ∑(ak; k=max(n-3,0)..max(n-1,0)) für n>0

Stufen
n
Möglichkeiten
an
1 1
2 2
3 4
4 7
5 13
6 24
7 44
8 81
9 149
10 274
11 504
12 927
13 1.705
14 3.136
15 5.768
16 10.609
17 19.513
18 35.890
19 66.012
20 121.415
21 223.317
22 410.744
23 755.476
24 1.389.537
25 2.555.757

Siehe auch Tribonacci Number -- from MathWorld

Antwort

Es gibt 2.555.757 verschiedene Möglichkeiten, 25 Stufen in Schritten von einer, zwei oder drei Stufen hinauf zu gehen.