Logo
schülerzirkel
mathematik
Wer hat Spaß an kniffligen Problemen?



Problem des Monats Mai 2005 mit Lösung
Wege im Gitter

Wege im Gitter

Das Bild zeigt zwei Wege entlang den Linien eines Gitternetzes, die in S beginnen und an dem schwarzen Balken enden.

Wie viele solcher Wege gibt es, wenn nur Schritte nach unten oder nach rechts erlaubt sind?

Lösung

Wege im Gitter mit KoeffizientenWir legen das Gitternetz so in ein Koordinatensystem, dass zu den Schnittpunkten im Gitternetz ganzzahlige Koordinaten gehören. Wir können dann das Problem durch "Rückwärtsdenken" lösen. Da im Gitternetz nur Wege nach rechts und nach unten erlaubt sind, gibt es z. B. vom Punkt (11|1) nur einen Weg zum schwarzen Balken, nämlich nach unten zum Punkt (11|0). Ebenso gibt es von den Gitterpunkten (11|2) bis (11|6) nur jeweils eine Möglichkeit, zum schwarzen Balken zu gelangen. Wir notieren aus diesem Grunde an den Gitterpunkten (11|1) bis (11|6) jeweils eine 1. Vom Gitterpunkt (10|1) aus gibt es 2 Möglichkeiten, zum schwarzen Balken zu kommen, nämlich direkt von (10|1) nach (10|0) oder von (10|1) über den Gitterpunkt (11|1) nach (11|0). Vom Gitterpunkt (9|1) aus gibt es drei Möglichkeiten usw. Im Bild sind die Anzahlen der möglichen Wege an den entsprechenden Gitterpunkten notiert.

Nach diesem Prinzip lassen sich weitere Anzahlen von Wegen bestimmen. Von jedem Eckpunkt (x|y) mit 0 kleinergleichkleiner gleich 10 und 2 kleinergleichkleinergleich 6 im Gitternetz gibt es immer so viele Wege, wie es zusammen Wege vom darunter liegenden Eckpunkt (x|y – 1) und vom rechts liegenden Eckpunkt (x + 1|y) gibt. Notiert man weiterhin die Anzahlen der möglichen Wege an den Gitternetzeckpunkten, so erhält man gerade die Zahlen des Pascalschen Dreiecks, also die Binomialkoeffizienten n über k. Von S, d.h. dem Gitterpunkt (0|6), gibt es dann 17 über 6= 12376 mögliche Wege, um zum schwarzen Balken zu gelangen.

Zurück zum aktuellen Monatsproblem