Vorherige Aufgabe   Übersicht 2002   Nächste Aufgabe 

Lösungen der DENKmal-Knobelaufgaben

7. Aufgabe 2002

gestellt am 29. April 2002 in der Knobelecke von
Abenteuer Mathematik - die Welt des Knobelns

Die Wege des Turms

  Aufgabe   Lösung   Antwort 

Aufgabe

Bekanntlich bewegt sich ein Turm auf dem 8x8-Schachbrett pro Zug entweder horizontal oder vertikal.

Ein Weg des Turms von einem Feld auf ein anderes sei die Folge aller Züge, die er dabei macht. Die zu überquerenden 'Zeilen' bzw. 'Spalten' des Brettes überquert er nur einmal! Es gibt also entweder eine oder maximal zwei Richtungen, in die der Turm sich bewegt. (Eine Zugfolge ist ein Weg, wenn es keine kürzere gibt, wobei wir unter ihrer Länge die Anzahl der durchlaufenen Felder bis zum Zielfeld verstehen.)

Auf wie vielen Wegen kann sich der Turm - auf dem sonst leeren Schachbrett - von einem Eckfeld in das diagonal gegenüber liegende Eckfeld bewegen, also etwa von a1 nach h8?

Die Lösung muss ausreichend begründet werden (Tabelle, Formel, Programm etc.).

(eingesandt von Johann Moll)

Lösung

Zum besseren Verständnis möchte ich die verwendeten Begriffe neu definieren.
Die Felder eines Schachbretts seien wie üblich bezeichnet, also die Spalten von links nach rechts mit a bis h und die Reihen von unten nach oben mit 1 bis 8, z.B. a1 oder h8.
Ein Zug sei hier ein kürzester gültiger Turmzug (auf einem sonst leeren Brett) und kann als ein geordnetes Paar von zwei horizontal oder vertikal benachbarten Feldern aufgefasst werden.
Eine Zugfolge (von A nach B) sei eine Folge von hintereinander durchführbaren Zügen (, wobei der erste bei A anfängt und der letzte bei B aufhört). Mit ihrer Länge ist die Anzahl ihrer Folgenglieder gemeint.
Ein Weg von A nach B sei eine kürzeste Zugfolge von A nach B.

In Wegen vorkommende Züge besitzen höchstens zwei verschiedene zueinander orthogonale Richtungen, denn enthält eine Zugfolge zwischen zwei Feldern Züge mit mehr als zwei Richtungen, dann sind zwei der Richtungen einander entgegen gesetzt und es kann eine kürzere Zugfolge zwischen den beiden Feldern konstruiert werden, indem die beiden entgegen gesetzten Züge weg gelassen und die dazwischen liegenden Züge geeignet transformiert werden.

Wenn ein Turm sich von A nach B bewegt, kann er dies tun, indem er sich erst horizontal auf B zu bewegt und anschließend die vertikalen Schritte nach B ausführt. Weil er die Spalten und Reihen zwischen Start- und Zielfeld in einzelnen Schritten überbrücken muss, gibt es keine kürzeren Zugfolgen. Aus diesen Aussagen über Existenz und Minimalität folgt, dass die Länge der Wege zwischen zwei Feldern die Summe der absoluten Spaltendifferenz x und der absoluten Reihendifferenz y ist.

Die vorkommenden Richtungen ergeben sich aus der Lage von Start- und Zielfeld zueinander. Weil das Startfeld jedes Zugs einer Zugfolge entweder das Startfeld der Zugfolge oder das Zielfeld des jeweils vorher gehenden Zugs ist, wird eine Zugfolge auch schon durch die Angaben von Start- und Zielfeld sowie der Folge von Richtungen der einzelnen Züge festgelegt. Bei einem bestimmten Startfeld entsprechen verschiedenen Richtungsfolgen auch verschiedene Zugfolgen.
Zum Zählen der Wege zwischen zwei Feldern reicht es also, die möglichen Anordnungen von aufeinander folgenden Richtungen zu zählen. Dabei können x horizontale und y vertikale Richtungen miteinander kombiniert werden, wobei alle so konstruierten Wege das Spielbrett nicht verlassen.
Die Anzahl dieser Kombinationen beträgt
(1) C(x,y) = (x+y)!/x!/y!

Ein Turms führt auf seinem Weg von einem Eckfeld zum diagonal gegenüber liegenden Eckfeld 7 Spalten- und 7 Reihenwechsel durch.
Die Anzahl der Wege berechnet sich also als
(2) C(7,7) = 14!/7!/7! = 3432

Antwort

Ein Turm kann sich auf 3432 verschiedenen Wegen von einem Eckfeld zum diagonal gegenüber liegenden Eckfeld eines Schachbretts bewegen.