Vorherige Aufgabe 
Übersicht 2003 
Nächste Aufgabe | Vorherige Aufgabe | Übersicht 2003 | Nächste Aufgabe |
|---|
gestellt am 28. April 2003 in der
Knobelecke von
Abenteuer Mathematik - die Welt des Knobelns
Sportlich die Treppe hinauf
 Aufgabe | Lösung | Antwort |
|---|
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)
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
Stufenn |
Möglichkeitenan |
|---|---|
| 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
Es gibt 2.555.757 verschiedene Möglichkeiten, 25 Stufen in Schritten von einer, zwei oder drei Stufen hinauf zu gehen.
Jörg Wiegels