ALL EN FR ES IT

Logo

≡ ► ◄ ▲

Der Königsweg

Mathematik Nr. 34

Auf einem Schachbrett steht der König in der linken unteren Ecke. Er kann sich von Feld zu Feld bewegen, aber aufgrund einer Wette nur nach folgenden Regeln:

Wie viele unterschiedliche Wege gibt es in die rechte obere Ecke?

Lösung anzeigen

Es gibt 48639 Wege.

Von Ortwin Gasper

Beschränken wir uns auf Züge nach rechts und oben, so erhält man von der linken unteren zur rechten oberen Ecke einem m*n-Schachbrettes

  [Mathematische Formel]

Wege. Ein Weg mit k diagonalen Zügen von der linken unteren zur rechten oberen Ecke eines n*n-Schachbrettes läßt sich zusammensetzen aus einem Weg ohne Diagonalzüge auf einem (n-k)*(n-k)-Schachbrett, und einer Aufteilung der k Diagonalzüge auf die 2(n-k)+1 'Zwischenräume' zwischen den 2(n-k) rechts- bzw. oben Zügen, dabei gilt vor dem ersten wie nach dem letzten dieser Züge auch als Zwischenraum. Geordnete Partitionen von k auf s Summanden gibt es

  [Mathematische Formel]

Also erhalten wir für ein n*n-Brett

  [Mathematische Formel]

Wege. Für die Anzahl der Wege erhält man:

 n   Wege
 2      3
 3     13
 4     63
 5    321
 6   1683
 7   8989
 8  48639,

Von Wolf W. Radzinski:

Ausgehend von linken unteren Feld führt ein Weg auf das Feld rechts daneben, ein Weg auf das Feld darüber und drei Wege auf das Feld Diagonal rechts oben (diagonal, erst nach rechts dann nach oben, erst nach oben dann nach rechts).

  1 3
  1 1

Weitere Überlegungen dieser Art ergeben, dass zu allen Randfeldern nur ein einziger Weg führt und zu alle anderen Feldern so viele Wege, wie zu den Feldern links, darunter und links darunter führen (weil das jeweilige Feld von jedem dieser Felder in genau einem Schritt erreicht werden kann):

  .  .  .  .  .
  1  7 25 68  .
  1  5 13 25  .
  1  3  5  7  .
  1  1  1  1  .