Wege durch eine Stadt

Wissenschaft Mathematik
#1

Eine Aufgabe, bei der ich die Lösung habe, aber Formulierungs- bzw Beweisprobleme habe…

In einem amerikanischen Stadtplan mit n Avenues und m Streets, die ein Gitter aus gleich großen Quadraten bilden, wollen Sie von einem Eckpunkt A aus zum gegenüberliegenden Eckpunkt B gehen. Wieviele kürzeste Wege gibt es?

Meine Lösung dazu…wenn man da alle Möglichkeiten durchspielt, merkt man, dass es sich um ein Pascal’sches Dreieck handelt und damit wäre die Lösung n+m über n bzw. m kürzeste Wege.
Aber wie soll man das beweisen?

#2

Hallo,

die Anzahl der Schritte, die man auf dem kürzesten Weg gehen muss ist die Blockdistanz der beiden Punkte (auch Manhattandistanz oder 1-norm des Differenzvektors). Diese ist (n-1)+(m-1).
Auf diesem Weg musst du (n-1) mal horizontal und (m-1) mal vertikal wandern (oder anders rum, je nachdem, wie rum man es zeichnet).
Die Anzahl der Möglichkeiten, aus den benötigten Schritten die entsprechende Anzahl an vertikalen bzw. horizontalen Schritten zu wählen entspricht dann genau dem Binomialkoeffizienten.
Achte aber auf die Subtraktion der 1. Denn bei einer Avenue und einer Street gibt es nur einen Kreuzungspunkt und du brauchst dich gar nicht bewegen.

Nico

#3

Also stimmt meine Lösung doch nicht? Irgendwie ist mir das jetzt nicht so klar :confused: Hoffe es bringt etwas, ne Nacht drüber zu schlafen :wink: Vielen Dank schonmal!

#4

Das kommt ganz darauf an, ob man mit m und n die Anzahl der Sprünge oder die Anzahl der Straßen meint.