Wie viele Möglichkeiten gibt es für eine auf a1 stehende Figur, nach h8 zu gelangen, wenn sie ausschließlich Schritte nach rechts oder nach oben, aber von beliebiger Weite gehen dürfen?
Ich habe das Problem für die jeweilige Schrittlänge eins in einer vorherigen Aufgabe bereits so gelöst, dass man 14 Züge braucht, 7 rechts, 7 hoch und sich da die Anzahl über den Binomialkoeffizient berechnen lässt. Also 14 über 7, also 3432.
Wie aber mache ich den Spaß mit beliebigen Schrittlängen?
Einzeln aufschlüsseln für 2,3,4,…13,14 Züge?
deine Lösungsstrategie liesse sich doch auf andere Schrittlängen ausweiten. Allerdings kannst mit fixen Schrittlängen, die kein Teiler von 7 sind, das Feld gar nicht erreichen, da du sieben Felder von a bis h überwinden musst.
Wenn du aber pro Zug variable Schrittweite hast, sind das alle Kombinationen von a_i und b_i (wenn die a_i die Schritte nach oben und die b_i die Schritte nach rechts sind) wobei Summe(a_i) = 7 und Summe(b_i)=7 gelten muss. Und dann noch alle Permutationen davon.
von a1 nach a2 gibt es einen weg.
von a1 nach b1 gilt selbiges.
von a1 nach b2 gibt es zwei wege (über a2 oder b1).
von a1 nach a3 gibt es ebenfalls zwei wege (direkt von a1 oder über a2). für c1 gilt analog das gleiche.
von a1 nach b3 (und analog auch nach c2) gibt es 5 wege: über a3, b2 oder b1. hier addiert man die jeweiligen möglichkeiten der vorausgegangenen felder.
für 3x3 felder sieht die sache also folgendermaßen aus (a1 im linken unteren eck):
- - -
|2|5| |
- - -
|1|2|5|
- - -
|1|1|2|
- - -
es ist leicht ersichtlich, daß die zahl in jedem feld die summe aller zahlen links von ihr und unter ihr ist. c3 hätte demnach den wert 14, und das läßt sich mit wenig aufwand auch verifizieren.
mit dieser bildungsregel läßt sich eine einfache excel-tabelle bauen, die dann für h8 den wert 470010 ausgibt. ich werde mir aber nicht die mühe machen, diese zahl auch durch ausprobieren zu bestätigen.